c++9中排序算法解释及代码

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])low++;//滑动右边指针 if(low

s[low]=key;//此时low与high相同

if(L

不稳定的排序，平均复杂度是O(nlogn)，最坏情况O(n^2)（有序数组）。 扩展用法：求序列中第K大数。

8. 希尔排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

int A[200005]; int main(){

int n,i,j,k,step,tmp; scanf(\,&n); for(i=0;i

for(step=n/2;step>0;step/=2){//增量 for(i=step;itmp){ A[k+step]=A[k]; k-=step; } A[k+step]=tmp; } } }

for(i=0;i

}

不稳定的排序算法，复杂度存在争议，下限是O(nlogn)，平均O(n^1.5)

9. 堆排序

堆得定义：

一个长度为n的数组A，下标1,2,3,….,n-2,n-1,n。

如果对于在[1,n/2]范围内的i，有A[i]<=A[i*2]且A[i]<=A[i*2+1]，则称为小顶堆。 如果对于在[1,n/2]范围内的i，有A[i]>=A[i*2]且A[i]>=A[i*2+1]，则称为大顶堆。

如果要将数组从小到大排序，则需要维护小顶堆。每次取出堆顶元素，再删除，一直维护小顶堆。

向下调整过程，可以用一个down()函数来完成。 void swap(int &a,int &b){//交换两个数 int t=a;a=b;b=t; }

void down(int k){ while(2*k<=sz){ int a=2*k; if(a+1<=sz&&heap[a]>heap[a+1])a++;//找较小的儿子 if(heap[k]>heap[a])swap(heap[k],heap[a]);//交换 else break; }

}

k=a;//往下走

初始化堆得时候，可以把n/2到1的每个元素都down下。

int heap[200005],sz;//sz记录当前堆得大小，也是最后一个元素的下标 int main(){ int i,j,k,n; scanf(\ sz=n; for(i=1;i<=n;i++) scanf(\ for(i=n/2;i>=1;i--) down(i);//初始化堆 for(i=1;i<=n;i++){ printf(\ }

heap[1]=heap[sz--];//用最后一个元素覆盖堆顶，在删除最后一个元素 down(1);//调整堆 }

return 0;

堆也可以添加元素，原理down类似，用up，把数字添加在heap[++sz]的位置上。 如果父亲节点比当前元素小，就不断向上。 void up(int k){ while(k>1){ int a=k/2;//a是父亲节点 if(heap[a]>heap[k])swap(heap[k],heap[a]); else break; k=a; } }

每次向上和向下都是logn，通过堆实现排序，复杂度是O(nlogn)，不稳定，“1 2 2”可以说明，删除1后，第二个2被赋值到堆顶，下次出来。

因此堆可以添加元素，并维护最大值，删除最大值，在很多贪心问题上，可以用到。

本文来源：https://www.bwwdw.com/article/bhea.html