各种排序算法总结

排序方法的稳定性：

对于关键字相同的元素，在其排序完后领先关系保持不变，即原来是…x1…x2…（x1和x2相同），在排序完后依然是…x1…x2…的位置，说明该排序是稳定的，反之是不稳定的。

1.插入排序

算法思想：

实现将一组数从小到大排列，即从数的第二个开始往前比较，如果它比前面相邻的数小，将它拎出来，然后前面的数往前进一个位置，至于将这个拎出来的数放在哪个位置，当然是放在比前面的数大的前一个位置。（前面的数是已经排完有序的）

代码实现：

int s[100];//数组s[] int n;//长度为n，序号从1~n for(int i=2;i<=n;i++) { if(s[i]>=s[i-1]) continue;//如果前面的数比它后面相邻的数大，满足排列，跳过 s[0]=s[i];//s[0]为哨兵，用来记录要插入的数值 int j=i-1;//用j来记录前i-1个数的位置 for(;s[0]<s[j];j--) { s[j+1]=s[j];//如果该数比前面的数小，则前面的数就往前移一个位置 } s[j+1]=s[0];//结束循环的时候s[0]必定大于或者等于该位置的数，所以在j位置的前面插入s[0] }

算法分析：

时间复杂度：O(n^2) 空间复杂度：O(1) 算法稳定性：稳定

2.冒泡排序

算法思想：

实现将n个数从小到大排序，两两比较，将最大的数放右边，一趟比较完后最右边的数即为最大数，然后n-1个数继续两两比较，将最大的数放在最右边，这是第二趟，共需要进行n-1趟。

代码实现：

int s[100]; int n;//数组长度为n，序号0~n-1 for(int i=0;i<n-1;i++) //进行n-1趟排序 { bool flag=true;//设置标记的目的是如果数组间不需要交换，说明已经排序完成，可以提前结束 for(int j=0;j<n-i-1;j++) { if(s[j]>s[j+1]) //两两比较，将大的数放在右边 { swap(s[j],s[j+1]); flag=false; } } if(flag==true) break;//说明已经排序完，可以提前结束 }

算法分析：

时间复杂度：O(n^2) 空间复杂度：O(1) 算法稳定性：稳定

3.选择排序

算法思想：

将一组数从小到大排序，类似冒泡排序，只不过不是一个个交换，而是在一组数中找出最小的数位置，与第一个交换数值，然后从后面找出最小的数位置与第二个交换数值，依次内推。

代码实现：

int s[100]; int n;//数组长度，序号从0~n-1 for(int i=0;i<n-1;i++) //进行n-1趟，交换n-1次 { int k=i; //k代表最小值的位置 for(int j=i+1;j<n;j++) //在n-i-1个元素中找出最小值 { if(s[j]<s[k]) { k=j; } } swap(s[i],s[k]);//最小值的位置与首元素交换数值 }

算法分析：

时间复杂度：O(n^2) 空间复杂度：O(1) 算法稳定性：不稳定

4.快速排序

算法思想：

将一组数从小到大排序，将首元素设置为哨兵，将后面的每个数与哨兵比较，比它小，放左边，比它大放右边，再把哨兵放在中间的位置，其左边的数都比它小，其右边的数都比它大，这样就实现了一趟快速排序，再把哨兵的左边和右边看成一个新的数组进行快速排序，依次进行，直到只剩一个元素时停止。

代码实现：

int s[1000]; int n;//数组长度为n，序号0~n-1 int quicksort(int low,int high) { //快速排序，low代表前面元素的地址序号，high代表后面元素的地址序号，下面类似 int x=s[low];//将首元素设为哨兵，所以现在low位置可以看成空位置 while(low<high) //当low==high时结束，此时该位置放哨兵 { while(low<high&&s[high]>=x) high--;//从右往左搜索 s[low]=s[high];//此时空位在low上，将比x小的放在空位 while(low<high&&s[low]<=x) low++;//从左往右遍历 s[high]=s[low]; //此时空位在high上，将比x大的放在空位 } s[low]=x;//此时low==high，所以该位置放哨兵 return low;//返回哨兵的位置 } void mysort(int low,int high) { if(high<=low) return;//长度为1，返回 int k=quicksort(low,high);//记录分界点 mysort(low,k-1);//左半部分进行快速排序 mysort(k+1,high);//右半部分进行快速排序 } mysort(0,n-1)//初次调用

算法分析：

时间复杂度：O(nlogn) 空间复杂度：O(logn) (递归造成的栈空间） 算法稳定性：不稳定

5.堆排序

算法思想：

这个稍微复杂一些，首先需要了解什么是堆，堆是一棵完全二叉树，其每个节点都大于或者小于它的左孩子和右孩子，当每个节点的值都大于它的左孩子和右孩子时，这叫大顶堆，当每个节点的值都小于它的左孩子和右孩子时，这叫小顶堆。 实现一组数从小到大排序，首先需要建大顶堆，可以把这个数组看成一个完全二叉树，第 i 个数看成一个节点，那么它的左孩子为 2*i ，右孩子为 2*i+1。当建完后，不管顺序如何，大顶堆的第一个元素一定是最大值，所以将它与最后一个数交换位置，再重新建堆。类似冒泡排序，不断将最大值放在最后面。

代码实现：

int s[1000]; int n;//数组长度为n，序号1~n(必须从1开始，因为要对应两个孩子) void HeapAdjust(int x,int m) //对堆进行调整，自上而下 { //x是堆顶位置，m是数组长度 int rc=s[x]; //rc用来保存堆顶值，下面的堆是有序的，即每个节点都大于它的左孩子和右孩子 for(int i=2*x;i<=m;i=i*2) //从堆顶的左孩子开始找 { if(i+1<=m&&s[i]<s[i+1]) i++; //如果右孩子比左孩子大，那么下标转移到右孩子 if(rc>=s[i]) break; //表明rc大于左孩子也大于右孩子，满足堆，结束循环 s[x]=s[i]; //两个孩子中最大的值变成节点 x=i; //该点放rc } s[x]=rc; } void HeapSort(int n) { //建大顶堆，节点从n/2开始就能全部遍历长度为n的数组 for(int i=n/2;i>0;i--) { HeapAdjust(i,n); //建大顶堆自下而上建立 } for(int i=n;i>1;i--) { swap(s[1],s[i]);//将堆顶元素与末尾元素交换 HeapAdjust(1,i-1); //重新建堆，长度减1 } }

算法分析：

时间复杂度：O(nlogn) 空间复杂度：O(1) 算法稳定性：不稳定

6.归并排序

算法思想：

实现一组数从小到大排序，核心即拆合，先将这组数拆成两两一组，按从小到大排序好，即有序，再将各个数组两两合并。

核心代码：

int s[1000]; int fu[1000];//设置辅助数组 int n; //数组长度，序号从0~n-1 void combine(int low,int mid,int high) { //两个数组归并，low是起始位置，mid是中间点，high是末端位置 int k=low,i=low,j=mid+1; //k为辅助数组下标，i为第一段数组起始下标，j为第二段数组起始下标 while(i<=mid&&j<=high) { //将两段数组中小的放在辅助数组里 if(s[i]<s[j]) { fu[k++]=s[i++]; } else { fu[k++]=s[j++]; } } //将两段数组中多出来的部分放进辅助数组中 while(i<=mid) fu[k++]=s[i++]; while(j<=high) fu[k++]=s[j++]; k=low; //k恢复到起始下标 while(k<=high) { //将辅助数组值放进数组中实现二路归并 s[k]=fu[k];k++; } } void CombineSort(int low,int high) { //拆，将数组拆到只剩两个 if(low>=high) return; int mid=(low+high)/2; CombineSort(low,mid); CombineSort(mid+1,high); combine(low,mid,high); }

算法分析：

时间复杂度：O(nlogn) 空间复杂度：O(n) 算法稳定性：稳定