9个排序算法
1. 计数排序
int a[1005]={0};//数值范围的大小 int main(){ int i,n,j,x; scanf(\ for(i=0;i a[x]++;//统计每个数值出现的次数 } for(i=0;i<=1000;i++) for(j=1;j<=a[i];j++) printf(\ puts(\ return 0; } 复杂度最低的排序算法，稳定排序，O(n+m)，n为元素个数，m为数值范围。 2. 选择排序 int num[1005]; int main(){ int n,i,j,k,t; scanf(\ for(i=1;i<=n;i++) scanf(\ for(i=1;i<=n;i++){ k=i; for(j=i+1;j<=n;j++)//在[i+1,n]的范围找到最小值的下标 if(num[j] 复杂度为O(n^2)，是不稳定的排序算法，可用“5 5 2”模拟。 3. 冒泡排序 int a[20005]; int main(){ int n,i,j,t; scanf(\ for(i=1;i<=n;i++) scanf(\ for(i=1;i //第i次冒泡时，判断[1,n-i]内每个数与它后面的数 for(j=1;j<=n-i;j++) if(a[j]>a[j+1]){ t=a[j]; a[j]=a[j+1]; a[j+1]=t; f=0;//发生了冒泡 } if(f)break;//如果没有发生冒泡，说明已经有序，可结束。 } for(i=1;i<=n;i++) printf(\puts(\return 0; 稳定排序，复杂度O(n^2),最好情况下O(n),冒泡排序发生的交换次数等于逆序对数。 4. 插入排序 int a[20005]; int main(){ int n,i,j,x; scanf(\ for(i=1;i<=n;i++) scanf(\ for(i=1;i<=n;i++){ x=a[i]; //[1,i-1]已经有序，把x插入进去 for(j=i-1;j>0&&x 稳定的排序算法，平均为O(n^2)，最好O(n)。 5. 基数排序 int s[10][20005],A[20005]; int main(){ int n,i,j,k; scanf(\ for(i=0;i 稳定排序算法，复杂度(n*m)，m为最长数位长度，注意数值需要是非负的，如果数据中有负数可以都加上一个很大的值。 初始数组:105 46301 124 2 12 1125 2054 55505 100 按倒数第1位： 46301 2 12 124 2054 105 1125 55505 按倒数第2位: 46301 2 105 55505 12 124 1125 2054 按倒数第3位: 2 12 2054 105 124 1125 46301 55505 按倒数第4位: 2 12 105 124 1125 2054 55505 46301 按倒数第5位: 2 12 105 124 1125 2054 46301 55505 6. 归并排序 合并有序序列的复杂度可以做到O(a+b)，a和b表示两个有序序列的长度。可以将待排序的数组划分成两个序列，将这两个序列排序后，再进行合并。这是一个递归过程，一直递归的序列的长度为1，就可以返回了。合并，返回，直到最初那层。共logn层，每层向上合并的复杂度是O(n)，总的复杂度是O(nlogn)。 #define M 200005 int A[M],B[M]; long long cnt=0;//统计逆序对数 void Merge(int L,int R){//在main函数中调用Merge(1,n); if(L==R)return;//序列长度为1，叶子节点 int mid=(L+R)/2; Merge(L,mid); //递归排序左边 Merge(mid+1,R);//递归排序右变 int i=L,j=mid+1,k=L;//合并[L,mid]和[mid+1,R]这两个有序序列 //先把合并结果放到B数组的[L,R] while(i<=mid&&j<=R){ if(A[i]<=A[j])B[k++]=A[i++]; else{ B[k++]=A[j++]; cnt+=mid-i+1;//A[j]比左边[i,mid]这个区间的数都小，产生逆序对 } } while(i<=mid)B[k++]=A[i++]; while(j<=R)B[k++]=A[j++]; for(k=L;k<=R;k++)A[k]=B[k];//赋值回A数组 } 稳定的排序算法，可以用来统计逆序对数。 7. 快速排序 基本思想是：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。然后再递归对这两部分进行排序。 #define M 200005 int s[M]; void sort(int L,int R){//在main函数中调用sort(1,n) int low=L,high=R; int key=s[low]; while(low } while(low while(low s[low]=key;//此时low与high相同 if(L 不稳定的排序，平均复杂度是O(nlogn)，最坏情况O(n^2)（有序数组）。 扩展用法：求序列中第K大数。