插入排序(Insert Sort)将待排序的元素按照关键字的大小插入到前面已有序列中const int N 1e6 10;int n;int a[N];void insert_sort(){//依此枚举待排序的元素for(int i 2; i n; i) //第一个位置默认是有序的{int key a[i];//前面比key大的统一右移int j i - 1;while(j 1 a[j] key){a[j 1] a[j];j--;}a[j 1] key;}}int main(){cin n;for(int i 1; i n; i)cin a[i];insert_sort();for(int i 1; i n; i)cout a[i] ;return 0;}选择排序(selection_sort)每次找出未排序列中最小的元素然后放进有序序列的后面第一步找最小第二步交换const int N 1e6 10;int n;int a[N];void selection_sort(){for(int i 1; i n; i) //待排序列区间的首位置{//[i,n] 区间就是待排序列的区间int pos i;for(int j 1 1; j n; j) // 查找待排序区间最小元素的下标{if(a[j] a[pos]){pos j;}}swap(a[i],a[pos]);}}int main(){cin n;for(int i 1; i n; i){cin a[i];}selection_sort();for(int i 1; i n; i){cout a[i] ;}return 0;}冒泡排序Bubble Sort相邻的元素在满足条件的情况下进行交换直到没有相邻的元素需要交换为止const int N 1e6 10;int n;int a[N];void bubble_sort(){//依此枚举待排序区间的最后一个元素for(int i n; i 1; i--){//[1,i] 就是待排序区间for(int j 1; j i; j){if(a[j] a[j 1]){swap(a[j],a[j 1]);}}}}int main(){cin n;for(int i 1; i n; i){cin a[i];}bubble_sort();for(int i 1; i n; i){cout a[i] ;}return 0;}当某一趟冒泡排序中没有执行元素的交换操作时整个序列就是有序的了所以没有必要再继续执行冒泡排序算法了下面为优化后的方案代码//优化后的冒泡排序void bubble_sort(){//依此枚举待排序区间的最后一个元素for(int i n; i 1; i--){//[1,i] 就是待排序区间for(int j 1; j i; j){if(a[j] a[j 1]){swap(a[j],a[j 1]);flag true;}}if(flag false)return ;}}堆排序(heap_sort)是指利用堆这种数据结构所设计的一种排序算法。本质上是优化了选择排序算法如果将数据放在堆中能够快速找到待排序元素中的最小值或最大值创建步骤为1、先建堆。升序建大堆降序建小堆。建堆过程从倒数第一个非叶子节点开始倒着一直到根结点位置每个结点进行向下调整。2、排序。每次将堆顶元素与堆最后一个元素交换堆的大小减一然后将堆顶元素向下调整。重复上述过程直到堆中剩下一个元素。const int N 1e6 10;int n;int a[N];void dowm(int parent,int len){int child parent * 2;while(child len){if(child 1 len a[child 1] a[child])child;if(a[parent],a[child])return ;swap(a[parent],a[child]);parent child;child parent * 2;}}void heap_sort(){//1、建堆for(int i n / 2; i 1; i--)//到数第一个非叶结点的序号是 n / 2{down(1,n); //使用down函数 进行向下调整}//2、排序for(int i n; i 1; i--)// 枚举堆里面最后一个元素的位置{swap(a[i],a[i]);down(1i- 1);}}int main(){cin n;for(int i 1; i n; i){cin a[i];}heap_sort();for(int i 1; i n; i){cout a[i] ;}return 0;}快速排序quick sort快速排序是一种效率较高的算法算法原理分为两步从待排区间中选择一个基准元素按照该元素的大小将区间分成左右两部分。然后递归处理左区间和右区间直到区间长度为1在快排序中随机选择一个基准元素函数srand(time(0)):种下一个随机数种子rand获得一个随机数rand %(right - left 1) left: 在[left , right]区间内随机选择一个数数组分两块的排序int n;int a[N];int get_random(int left,it right){return a[rand() % (right - left 1) left];}int main(){srand(time(0));return 0;}数组分三块的快排左边全部小于基准元素中间全部等于基准元素右边全部大于基准元素const int N 1e6 10;int n;int a[N];int get_random(int left,it right){return a[rand() % (right - left 1) left];}void quick_sort(int left,int right){if(left right)return ;//1、选择一个基准元素int p getrandom(left,right);//2、将数组分为三块int l left - 1,i left, r right 1;while(i r){if(a[i] p)swap(a[l],a[i]);else if(a[i] p)i;elseswap(a[--r],a[i]);}//区间的划分// [left,l] [ l 1 , r - 1] [r, right]quick_sort(left,l);quick_sort(r,right);}int main(){srand(time(0));cin n;for(int i 1; i n; i)cin a[i];quick_sort();for(int i 1; i n; i)cout a[i];return 0;}归并排序merge sort无论数据有什么特性时间复杂度就能确定的排序算法分为两步1、只要能分就将区间一分为二分到不能再分为止然后将左右区间分别排序。2、然后将这两个区间进行合并。归并排序实际上使用递归来实现的const int N 1e6 10;int n;int a[N];int tmp[N]; //辅助归并排序时合并两个有序数组void merge_sort(int left,int right){if(left right)return ;else//先一分为二int mid (left right) 1;//区间为 [left,mid] [mid 1,right]//2、先让左右区间有序merge_sort(left,mid);merge_sort(mid 1,right);//3、合并两个有序数组int cur1 left,cur2 min 1,i left;while(cur1 mid cur2 right){if(a[cur1] a[cur2])tmp[i] a[cur1];elsetmp[i] a[cur2];}while(cur1 mid) tmp[i] a[cur1];while(cur2 right) tmp[i] a[cur2];for(int j left; j right; j){a[j] tmp[j];}}int main(){cin n;for(int i 1; i n; i)cin a[i];merge_sort();for(int i 1; i n; i )cout a[i] ;return 0;}