排序算法[c++版]

计数排序

是将所要排序的数据作为数组下标，将数组出现的次数作为数组元素值，然后按次数输出数组，即排序结果。并没有做到最后真正排序，只是可以输出排序的结果。 时间复杂度O(m + n)，空间复杂度O(n)。对于数据范围较小可以使用，不需要进行比较的排序算法。 参考题目： P1271 【深基9.例1】选举学生会

// 计数排序 #include<iostream> using namespace std; int main(){ int n,m; cin >> n >> m; int list[n + 1] = {0}; for(int i = 0;i < m;i++){ int temp; cin >> temp; list[temp]++; } for(int i = 1;i <= n;i++){ for(int j = 0;j < list[i];j++){ cout << i <<' '; } } return 0; }

漫画：什么是计数排序？

选择排序

顾名思义就是每次在剩下的数组元素中选择最大或最小的元素放在数组前面。做到了将数组元素真正排序。 时间复杂度O(n^2)，空间复杂度O(n)。 参考题目： 输入n个数字，从小排到大后输出。

//选择排序 #include<iostream> using namespace std; int main(){ int n,m; cin >> n; int list[n]; for(int i = 0;i < n;i++){ cin >> list[i]; } for(int i = 0;i < n - 1;i++){ for(int j = i + 1;j < n;j++){ if(list[j] < list[i]){ int temp = list[i]; list[i] = list[j]; list[j] = temp; } } } for(int i = 0;i < n;i++){ cout << list[i] <<' '; } return 0; }

冒泡排序

每次比较相邻的2个数组元素值，将较大的放到右边，在一轮中，最大的元素就会移到右边。本质上和选择排序没有区别。 参考题目： 输入n个数字，从小排到大后输出。

//冒泡排序 #include<iostream> using namespace std; int main(){ int n,m; cin >> n; int list[n]; for(int i = 0;i < n;i++){ cin >> list[i]; } for(int i = 0;i < n - 1;i++){ for(int j = 0;j < n - i- 1;j++){ if(list[j] > list[j + 1]){ int temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; } } } for(int i = 0;i < n;i++){ cout << list[i] <<' '; } return 0; }

插入排序

将数据分为有序区和无序区2部分，然后将无序区的待插数据与有序区的数据进行比较，直到遇到第一个不大于自己或者成为list[0]时插入。时间复杂度考虑最坏的情况O(n^2)，空间复杂度还是O(n)。 时间复杂度与空间复杂度基本和选择排序，冒泡排序几乎一样。 参考题目： 输入n个数字，从小排到大后输出。

//冒泡排序 #include<iostream> using namespace std; int main(){ int n; cin >> n; int list[n]; for(int i = 0;i < n;i++){ cin >> list[i]; } for(int i = 1;i < n;i++){ int now = list[i],j; for(j = i - 1;j >= 0;j--){ if(now < list[j]){ list[j + 1] = list[j]; } else break; list[j] = now; } } for(int i = 0;i < n;i++){ cout << list[i] <<' '; } return 0; }

由于这三种排序算法的时间复杂度并不佳，如果数据规模较大（比如需要排序几万个以上的数字），使用这些算法可能会耗时很久，所以一般不会再程序设计竞赛中使用这些算法。学习和掌握这些算法的目的就是为了理解算法的原理，并且知道如何分析算法复杂度，这也是对思维的训练。

快速排序

寻找一个中间数，然后将序列中所有比中间数小的放左边，大的放右边，然后对左右两部分继续分割，直到无法分割为止。 对于极端情况，比如数列已经有序，快速排序时间复杂度为O(n^2)，但如果随机选择哨兵，则很难出现这种情况。实际上随机快速排序的时间复杂度是O(n lg n),空间复杂度是O（n）,而且不需要额外的辅助空间，是一种比较实用的排序算法，利用到了"分而治之"思想。 参考题目： 输入n个数字，从小排到大后输出

#include<iostream> #include<cstdlib> #include<ctime> using namespace std; void quickSort(int list[],int start,int end); int random(int a,int b); int main(){ int n; cin >> n; int list[n]; for(int i = 0;i < n;i++){ cin >> list[i]; } quickSort(list,0,n - 1); for(int i = 0;i < n;i++){ cout << list[i]; if(i < n - 1) cout << ' '; } return 0; } void quickSort(int list[],int start,int end){ int i = start,j = end; if(i < j){ int temp = list[random(i,j)]; list[random(i,j)] = list[i]; list[i] = temp; int now = list[i]; while(i < j){ while(i < j && list[j] > now) j--; list[i] = list[j]; while(i <j && list[i] < now) i++; list[j] = list[i]; } list[i] = now; quickSort(list,start,i - 1); quickSort(list,i + 1,end); } } int random(int a,int b){ srand((int)time(NULL)); int x = rand() % (b - a + 1) + a; return x; }

归并排序

采取分而治之的策略，将数据划分为小块进行排序，再合并。 具体描述 参考题目： 输入n个数字，从小排到大后输出

#include<iostream> using namespace std; void merge(int temp[],int L,int R,int Rend,int list[]); void mergeSort(int temp[],int L,int R,int list[]); int main(){ int n; cin >> n; int list[n],temp[n]; for(int i = 0;i < n;i++){ cin >> list[i]; } mergeSort(temp,0,n - 1,list); for(int i = 0;i < n;i++){ cout << list[i] << ' '; } return 0; } void merge(int temp[],int L,int R,int R_end,int list[]){ int center = R - 1; int count = R_end - L + 1; int index = L; while(L <= center && R <= R_end){ if(list[L] < list[R]) temp[index++] = list[L++]; else temp[index++] = list[R++]; } while(L <= center) temp[index++] = list[L++]; while(R <= R_end) temp[index++] = list[R++]; for(;count > 0;count--){ list[R_end] = temp[R_end--]; } } void mergeSort(int temp[],int L,int R,int list[]){ if(R > L){ int L_end = (L + R) / 2; int R_start = L_end + 1; mergeSort(temp,L,L_end,list); mergeSort(temp,R_start,R,list); merge(temp,L,R_start,R,list); } }

STL - sort函数

在c++中可以直接使用sort函数进行排序。 sort(start,end,排序方法)，start为起始地址，end为排序的下一位地址，不传入第三个参数默认从小到大排序。如果需要从小到大，则需要借助第三个参数。 代码

#include<iostream> #include<cstdlib> #include<ctime> #include<algorithm> using namespace std; bool com(int a,int b){ return a > b; } void quick_kSort(int list[],int start,int end,int k); int main(){ int n = 10; int list[n] = {9,5,2,8,7,4,1,6,3,0}; sort(list,list + n);//从小到大 for(int i = 0;i < 10;i++){ cout << list[i] << ' '; } cout << endl; sort(list,list + n,com);//从大到小，com不需要传入参数 for(int i = 0;i < 10;i++){ cout << list[i] << ' '; } return 0; }

输出结果

0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0

头文件是 #include<algorithm> 时间复杂度为 O(n lg n)。 STL中的sort并非只是普通的快速排序，除了对普通的快速排序进行优化，它还结合了插入排序和堆排序。根据不同的数量级别以及不同情况，能自动选用合适的排序方法。当数据量较大时采用快速排序，分段递归。一旦分段后的数据量小于某个阀值，为避免递归调用带来过大的额外负荷，便会改用插入排序。而如果递归层次过深，有出现最坏情况的倾向，还会改用堆排序。

stable_sort()

稳定排序，例如，“apples” 和 “winter” 就是相等的，如果在"apples" 出现在"winter"前面，用带stable的函数排序后，他们的次序一定不变，如果你使用的是不带"stable"的函数排序，那么排序完 后，"winter"有可能在"apples"的前面。