1.插入排序
1.基本介绍
直接插入排序是最简单的排序方法，每次将一个待排序的记录，插入到已经排好序的数据序列中，得到一个新的长度增1的有序表。如图9-3所示。
2.算法步骤:
1)设待排序的记录 存储在数组r[1…n]中，可以把第一个记录r[1]看作-一个有序序列。 2)依次将[国] (i=2，… n)插入到已经排好序的序列r[1…i-1]中，并保持有序性。 例如,利用直接插入排序算法对序列 {12,2,16,30,28,10,16*,20,6,18}进行非递减排序。 初始状态，把r[1]看作-一个有序序列。如图9-4所示。 之后将待元素保存到arr数组中(1–n) 从第二个开始进行排序,先将元素放到arr[0]位置,之后元素和前面的每一个进行比较.当arr[0] < arr[i]则将arr[i]元素后移.直到arr[0]>=arr[i],将元素放入到i+1位置即可.本元素排序结束.其他元素也是这样…
3.算法复杂度
时间复杂度: O(n^2) 空间复杂度: O(1) 是否稳定:是
4.实现代码
#include
using namespace std;
#define Maxsize 100
void StraightInsertSort(int r[],int n) { //直接插入排序
int i,j;
for(i=2; i<=n; i++) //r[i]插入有序子表
if(r[i] r[0]=r[i]; //r[i]暂存到r[0]中，r[0]有监视哨的作用 r[i]=r[i-1]; //r[i-1]后移一位 for(j=i-2; r[j]>r[0]; j--) //从后向前寻找插入位置,逐个后移，直到找到插入位置 r[j+1]=r[j]; //r[j]后移一位 r[j+1]=r[0]; //将r[0]插入到r[j+1]位置 } } int main() { int i,n,r[Maxsize+1]; cout<<"请输入数列中的元素个数n为："< cin>>n; cout<<"请依次输入数列中的元素："< for(i=1; i<=n; i++) cin>>r[i]; StraightInsertSort(r,n); cout<<"直接插入排序结果："< for(i=1; i<=n; i++) cout< return 0; } 例题练习 POJ2388 参考代码 #include #include using namespace std; int arr[10000+5],n; void InsertSort(int r[],int n){//插入排序 int i,j; for(i = 2;i<=n;i++){//从第2个开始进行排序. //arr[0] = r[i+1]; if(r[i] arr[0]=r[i]; r[i]=r[i-1];//r[i-1]后移一位 for(j=i-2;r[0] r[j+1]=r[j];//当前元素后移 如果 r[0] } r[j+1]=r[0];//将r[0]存入r[j+1] } } } int main() { cin>>n; for(int i = 1;i<=n;i++){ cin>>arr[i]; } //sort(arr+1,arr+1+n); InsertSort(arr,n); cout< return 0; } 2.冒泡排序 1.算法介绍 冒泡排序是一种最简单的交换排序算法，通过两两比较关键字，如果逆序就交换，使关键字大的记录像泡泡一样冒出来放在尾部。重复执行若干次冒泡排序，最终得到有序序列。 2.算法步骤 1)设待排序的记录存 储在数组r[1…n]中， 首先第一个记录和第二个记录关键字比较,若逆序则交换;然后第一个记录和第二个记录关键字比较，.，以此类推，直到第n-1个记录和第n个记录关键字比较完毕为止。第–趟排序结束，关键字最大的记录在最后一个位置。 2)第二趟排序， 对前n-1个元素进行冒泡排序，关键字次大的记录在n-1位置。 3)重复 上述过程，直到某–趟排序中没有进 行交换记录为止，说明序列已经有序。 3.算法复杂度 时间复杂度: O(n^2) 空间复杂度: O(1) 是否稳定:是 4.实现代码 #include using namespace std; #define Maxsize 100 void BubbleSort(int r[],int n) //冒泡排序 { int i,j,temp; bool flag; i=n-1; flag=true; while(i>0&&flag)//当flag为false说明该轮排序已无交换,排序结束. { flag=false; for(j=0;j if(r[j]>r[j+1]) { flag=true; temp=r[j]; //交换两个记录 r[j]=r[j+1]; r[j+1]=temp; } for(j=0;j<=i;j++)//测试每趟排序结果 cout< cout< i--; } } int main() { int i,n,r[Maxsize]; cout<<"请输入数列中的元素个数n为："< cin>>n; cout<<"请依次输入数列中的元素："< for(i=0;i cin>>r[i]; BubbleSort(r,n); cout<<"冒泡排序结果："< for(i=0;i cout< return 0; } 3.快速排序 1.基本介绍 快速排序（Quicksort〉是比较快速的排序方法。快速排序由C.A.R.Hoare在 1962年提出。它的基本思想是通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行，以此使所有数据变成有序序列。 快速排序的基本思想是基于分治策略的，其算法思想如下。 1)分解:先从数列中取出一个元素作为基准元素。以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。2)治理:对两个子序列进行快速排序。3)合并:将排好序的两个子序列合并在一起，得到原问题的解。 2.快排的核心—如何分解 如何分解是–个难题，因为如果基准元素选取不当,有可能分解成规模为0和n-1的两个子序列，这样快速排序就退化为冒泡排序了。 例如，序列(30，24，5，58，18， 36，12， 42，39)， 第一-次选取5做基准元素，分解后，如图9-31所示。 第二次选取12做基准元素，分解后如图9-32所示。 是不是有点像冒泡了?这样做的效率是最差的,最理想的状态是把序列分解为两个规模相当的子序列，那么怎么选择基准元素呢?一般来说， 基准元素选取有以下几种方法: 取第一一个元素。取最后一个元素。取中间位置元素。取第一个、最后一个、中间位置元素三者之中位数。取第一个和最后一个之间位置的随机数k (low≤k≤high)， 选R[k]做基准元素。 3.算法步骤: 1)首 先取数组的第-个元素作为基准元素pivot=R[ow]。i=low, j=high。 2)从右向左扫描， 找小于等于pivot的数，如果找到，R[i]和R[j]交换，i++。 3)从左向右扫描， 找大于pivot的数，如果找到，R[j]和 R[i]交换, j- -。 4)重复步骤2~步骤3， 直到i和j指针重合，返回该位置mid=i,该位置的数正好是pivot元素。 5)至此完成- -趟排序。 此时以mid为界，将原数据分为两个子序列，左侧子序列元素都比pivot小，右侧子序列元素都比pivot大，然后再分别对这两个子序列进行快速排序。 4.算法图解 未改进快排图解: 快排改进后图解: 5.算法复杂度 时间复杂度: nlogn 空间复杂度: logn 是否稳定:否 6.实现代码 #include #include #include using namespace std; int Partition(int r[],int low,int high) { //划分函数 int i = low,j=high,pivot=r[low];//基准元素 while(i while(i j--;//向左扫描 if(i swap(r[i++],r[j]);//r[i]和r[j]交换后i+1后移一位 } while(i i++;//向右扫描 if(i swap(r[i],r[j--]);//r[i]和r[j]交换后 j-1左移一位 } } return i;//返回最终划分完成后基准元素所在的位置 } int Partition2(int r[],int low,int high) { //划分函数 k = (rand()%(high-low+1))+low;//产生一个随机基准元素.. swap(r[low],r[k]); // 将基准元素和第一个元素进行交换,就依旧可以使用之前的代码了.. int i = low,j=high,pivot=r[low];//基准元素 while(i while(i j--; while(i i++; } if(i swap(r[i++],r[j--]);//r[i]和r[j]交换 } } if(r[i]>pivot) { //r[i]如果比标准元素大 swap(r[i-1],r[low]);//r[i-1]和r[low]交换 return i-1;//返回最终划分完成后基准元素所在的位置. } swap(r[i],r[low]);//r[i]和r[low]交换 return i;// 返回最终划分完成后基准元素所在的位置. } void QuickSort(int R[],int low,int high) { //实现快排算法 int mid; if(low mid=Partition2(R,low,high);//基准位置 QuickSort(R,low,mid-1);//左区间递归快排 QuickSort(R,mid+1,high); //右区间递归快排 } } int main() { int a[100]; int i,n; cout<<"请先输入要排序的数据的个数:"; cin>>n; cout<<"请输入要排序的数据:"; for(int i = 0; i cin>>a[i]; } cout< QuickSort(a,0,n-1); cout<<"排序后的序列为:"< for(int i = 0; i cout< } cout< return 0; } 4.合并排序 1.基本介绍 合并排序就是采用分治的策略，将一个大的问题分成很多个小问题，先解决小问题，再通过小问题解决大问题。由于排序问题给定的是一个无序的序列，可以把待排序元素分解成两个规模大致相等的子序列。如果不易解决，再将得到的子序列继续分解，直到子序列中包含的元素个数为1。因为单个元素的序列本身是有序的，此时便可以进行合并，从而得到一个完整的有序序列。 2.合并排序的核心–如何划分 算法设计: 合并排序是采用分治策略实现对n个元素进行排序的算法，是分治法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略，过程大致分为: (1)分解一将待排序元素分成大小大致相同的两个子序列。(2)治理一 对两个子序列进行合并排序。(3)合并一将排好序的有序子序列进行合并，得到最终的有序序列。 合并操作: 3.算法复杂度 时间复杂度: nlogn 空间复杂度: O(n) 是否稳定:是 4.实现代码 #include using namespace std; void Merge(int A[], int low,int mid,int high){//合并函数 int *B = new int[high-low+1];//申请一个辅助数组 int i = low,j=mid+1,k=0; while(i<=mid && j<= high){//按从小到大存放辅助数组B[]中 if(A[i] <= A[j]){ B[k++]=A[i++];//如果i所指的元素小,将其放入B后,i,k后移. }else{ B[k++]=A[j++];//如果j所指的元素小,将其放入B后,j,k后移. } } while(i<=mid){//如果i所指的数组中元素未放完. B[k++]=A[i++];//将数组剩下的元素放到B中 } while(j<=high){ B[k++]=A[j++]; } for(i = low,k = 0;i<=high;i++){//将排好序的元素重新放回A 因为后序可能会和其他的进行合并排序.. A[i]=B[k++]; } delete []B; } void MergeSort(int A[],int low,int high){//合并排序 if(low int mid=(low+high)/2;//取中点 MergeSort(A,low,mid);//对A[low:mid]中的元素合并排序 MergeSort(A,mid+1,high);//对A[mid+1:high]中的元素合并排序 Merge(A,low,mid,high);//合并 } } int main() { int n,A[100]; cout<<"请输入队列中的元素个数n为:"< cin>>n; cout<<"请依次输入数列中的元素:"< for(int i = 0;i < n;i++){ cin>>A[i]; } MergeSort(A,0,n-1); cout<<"合并排序结果:"< for(int i = 0;i < n;i++){ cout< } cout< return 0; } 5.选择排序 6.堆排序 7.桶排序 8.基数排序