12种排序方法图解及C++实现
冒泡排序（bubble sort）
两两比较交换
代码：
void BubbleSort(int R[]){
int flag;
for(int i=0;i<9;++i){
flag=0;
for(int j=0;j<9;++j)
if(R[j]>R[j+1]){
swap(R[j],R[j+1]);
flag=1;
}
if(flag==0)break;
}
}
????优化
梳排序（comb sort）
梳排序（Comb sort）是一种不稳定排序算法，其改良于冒泡排序和快速排序。
在冒泡排序中，只比较阵列中相邻的两项，即比较的间距为1，梳排序提出此间距其实可以大于1，梳排序中，开始时的间距设定为阵列长度，并在循环中以固定的比率递减，通常递减率为1.3，该数字是原作者通过实验得到的最有效的递减率，因为编程中乘法比除法块，所以会取递减率的倒数与间距相乘，即0.8.其实当间距为1的时候，梳排序就是冒泡排序，而间距大于1的时候，梳排序的就是尽量把小的数字往前移动并保证此次间隔内的组是有序的。
例如：当间隔为6时，保证间隔为6的数字之间是有序的，
当间隔为4时，保证间隔为4的数字之间是有序的，
当间隔为3时，保证间隔为3的数字之间是有序的，
当间隔为2时，保证间隔为2的数字之间是有序的，
当间隔为1时，为冒泡排序，调整最后顺序使两两之间有序。
假设待数组[8 4 3 7 6 5 2 1]
待排数组长度为8,而8÷1.3=6,则比较8和2,4和1,并做交换
[8 4 3 7 6 5 2 1]
[2 4 3 7 6 5 8 1]
交换后的结果为
[2 1 3 7 6 5 8 4]
第二次循环,更新间距为6÷1.3=4,比较2和6,1和5,3和8,7和4
[2 1 3 7 6 5 8 4]
[2 1 3 7 6 5 8 4]
[2 1 3 7 6 5 8 4]
[2 1 3 7 6 5 8 4]
只有7和4需要交换,交换后的结果为
[2 1 3 4 6 5 8 7]
第三次循环,更新距离为3,没有交换
第四次循环,更新距离为2,没有交换
第五次循环,更新距离为1,三处交换
[2 1 3 4 6 5 8 7]
[1 2 3 4 5 6 8 7]
[1 2 3 4 5 6 7 8]
三处交换后的结果为[1 2 3 4 5 6 7 8]
交换后排序结束,顺序输出即可得到[1 2 3 4 5 6 7 8]
代码：
template <typename T>
void comb_sort(T arr[], int len) {
int step = int(len * 0.8); // 0.8 = 1 / 1.3
while (step >= 1) {
for (int i = 0; i < len; ++i) {
int des = i + step;
if ((des < len) && (arr[i] > arr[des])) {
swap(arr[i], arr[des]);
} else if (des >= len) {
break;
}
}
step *= 0.8;
}
}
3.插入排序（insert sort）
void InsertSort(int R[]){
for(int i=1;i<10;++i){
int t=R[i];
int a=i-1;
while(a>=0 && R[a]>=t){
R[a+1]=R[a];
a--;
}
R[a+1]=t;
display(R);
}
}
快速排序（quick sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
代码实现：
int Partition_QuickSort(int a[],int left,int right){ //分区操作
int i=left;
int j=right;
int temp=a[i];
while(i<j)
{
while(i<j && a[j]>=temp)
j--;
if(i<j)
a[i]=a[j];
while(i<j && a[i]<=temp)
i++;
if(i<j)
a[j]=a[i];
}
a[i]=temp;
return i;
}
void qSort_QuickSort(int a[],int left,int right){ //递归把序列不断分区
int dp;
if(left<right)
{
dp=Partition_QuickSort(a,left,right);
qSort_QuickSort(a,left,dp-1);
qSort_QuickSort(a,dp+1,right);
}
}
void QuickSort(int a[]){ // 封装到一个函数里可以直接调用
qSort_QuickSort(a,0,n-1);
}
基于冒泡排序和快速排序 改良出希尔排序
希尔排序（shell sort）
基本思想：一般的初次取序列的一半为增量（gap），以后每次减半，直到增量为1。排序时用插入排序（冒泡也可以）。
void ShellSort(int R[]){
for(int gap=10/2;gap>0;gap/=2){
for(int i=gap;i<10;i++){ //插入排序
int j=i;
int temp=R[j];
if(R[j]<R[j-gap]){
while(j-gap>=0&&temp<R[j-gap]){
R[j]=R[j-gap];
j-=gap;
}
R[j]=temp;
}
}
}
}
选择排序（choosing sort）
工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
void ChoosingSort(int R[]){
int minn,t,z;
for(int i=0;i<10;++i){
minn=R[i];
t=R[i];
z=i;
for(int j=i+1;j<10;j++){
if(R[j]<minn){minn=R[j];
z=j;}
}
R[i]=minn;
R[z]=t;
}
}
归并排序（merge sort）
工作原理：不断把数组二分直到不能再分，每个序列排序之后和旁边排序好的序列合并，直到整个序列有序
void Merge(int A[], int p, int q, int r){
int n1 =q - p + 1; //第一个合并数据的长度
int n2 = r -q; //第二个合并数据的长度
int *L = new int[n1 + 1]; //申请一个保存第一个数据的空间
int *R = new int[n2 + 1]; //申请二个保存第一个数据的空间
for (int i = 0; i < n1; ++i) //复制第一个数据到临时空间里面
{
L[i] = A[p + i];
}
L[n1] = INT_MAX; //将最后一个数据设置为最大值(哨兵)
for (int i = 0; i < n2; ++i) //复制第二个数据到临时空间里面
{
R[i] = A[q + i + 1];
}
R[n2] = INT_MAX; //将最后一个数据设置为最大值(哨兵)
n1 = n2 = 0;
while(p <= r)
{
A[p++] = L[n1] < R[n2] ? L[n1++] : R[n2++]; //取出当前最小值到指定位置
}
delete L;
delete R;
}
void MSort(int A[], int p, int r){
int q;
if(p<r)
{
q=(p+r)/2;
MSort(A,p,q);
MSort(A,q+1,r);
Merge(A,p,q,r);
}
}
void MergeSort(int A[]){
MSort(A,0,9);
}
堆排序（Heap Sort）
最大堆要求除了根以外所有结点i都要满足：A[PARENT(i)]>=A[i]
最小堆要求除了根以外所有结点i都要满足：A[PARENT(i)]<=A[i]
在堆排序算法中，我们使用的使最大堆，最小堆用于构造优先队列。
堆的建立：
堆的排序过程：将数组A[1…n]建立成最大堆后，因为数组中的最大元素总是在根结点A[1]中，通过它与A[n]的交换，我们可以让该元素放到正确的位置，这时候，如果我们从堆中去掉顶点n,剩余的结点中，原来根的孩子结点仍然使最大堆，而新的根结点可能会违背最大堆的性质。为了维护最大堆的性质，我们需要再次调用adjust()，从而在A[1…n-1]上重新建立最大堆。堆排序算法会不断的重复这个过程，直到排序完成。（图源算法导论）
代码如下：
#include <iostream>
using namespace std;
#define swap(a,b) a=a+b;b=a-b;a=a-b
//int R[]={0,23,56,33,66,44,88,63,11,7,88};
int R[]={25,64,34,15,16,7,2,9,23,3};
void adjust(int R[],int f,int n){
int i;
int temp=R[f];
for(i=2*f+1;i<n;i=i*2+1){
if( (i+1<n) && (R[i]<R[i+1]) )
i++;
if(temp<R[i]){
R[f]=R[i];
f=i;
}
else break;
}
R[f]=temp;
}
int main()
{
int i,j;
for(i=0;i<10;++i)cout<<R[i]<<" ";
cout<<endl;
for(j=10/2-1;j>=0;j--)adjust(R,j,10); //堆的建立
for(j=9;j>0;j--){ //排序
swap(R[0],R[j]);
adjust(R,0,j);
}
for(i=0;i<10;++i)cout<<R[i]<<" ";
cout<<endl;
return 0;
}
二叉排序树（binary sort tree）
二叉排序树(Binary Sort Tree)，又称二叉查找树。它是一颗空树，或者具有下列性质：
若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树分别为二叉排序树。
代码：
#include <iostream>
using namespace std;
int a[]={91,12,43,2,67,48,32,54,29,10};
typedef struct BinarySortTreeNode{
int data;
int bf;
struct BinarySortTreeNode *lchild,*rchild;
}BSTNode,*bitree;
bool Insertbst(BSTNode **T,int k){
BSTNode *p;
if( !(*T) ){
p= new BSTNode;
p->bf=0;
p->lchild=p->rchild=NULL;
p->data=k;
cout<<k<<" ";
*T=p;
}
else if( k==((*T)->data) ) return 0;
else if( k<((*T)->data) )Insertbst( &((*T)->lchild),k );
else Insertbst( &( (*T)->rchild ),k );
return 1;
}
void display(bitree T){
if(T){
display(T->lchild);
cout<<T->data<<" ";
display(T->rchild);
}
}
int bstSearch(bitree T,bitree *f,bitree *c,int key){
bitree ff,cc;
ff=T;
cc=ff;
while(cc){
if(key==cc->data)break;
else {
ff=cc;
if(key<cc->data)cc=cc->lchild;
else cc=cc->rchild;
}
}
*f=ff;
*c=cc;
if(cc)return 1;
else return 0;
}
bool deletenode(bitree *T,int key){
bitree f,c,p,*H;
if(bstSearch(*T,&f,&c,key)){
cout<<"f="<<f->data<<endl;
cout<<"c="<<c->data<<endl;
if(f==c)H=T;
else if(c->data<f->data)H=&(f->lchild);
else H=&(f->rchild);
if(c->lchild==NULL)*H=c->rchild;
else if(c->rchild==NULL)*H=c->lchild;
else {
p=c->rchild;
while(p->lchild)p=p->lchild;
p->lchild=c->lchild;
*H=c->rchild;
}
delete c;
}
}
int newinsert(bitree *T,int key){
bitree f,c,p;
if(!bstSearch(*T,&f,&c,key)){
p=new BSTNode;
p->bf=0;
p->rchild=NULL;
p->lchild=NULL;
p->data=key;
if(f==NULL)*T=p;
else if(key<f->data)f->lchild=p;
else f->rchild=p;
}
}
int main()
{
int i;
bitree T,father,son;
T=NULL;
for(i=0;i<10;i++)
Insertbst(&T,a[i]);
cout<<endl;
display(T);
cout<<endl;
bstSearch(T,&father,&son,67);
newinsert(&T,100);
newinsert(&T,8);
cout<<endl;
display(T);
cout<<endl;
cout<<"father="<<father->data<<endl;
cout<<"son="<<son->data<<endl;
deletenode(&T,54);
cout<<endl;
display(T);
cout<<endl;
return 0;
}
计数排序（Counting sort）
不解释直接上代码
参考 http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html
void CountingSort(int R[]){
int maxx=R[0],minn=R[0];
for(int i=1;i<10;i++){
if(R[i]>maxx)maxx=R[i];
if(R[i]<minn)minn=R[i];
}
int a=maxx-minn+1;
int B[a],C[10];
memset(B,0,a*sizeof(B[0]));// don't forget this
for(int i=0;i<10;++i){ //counting how many times R[i] showed on array R[]
B[R[i]-minn+1]++;
}
for(int i=0;i<a;++i) B[i+1]+=B[i]；
for(int i=0;i<10;++i) C[B[R[i]-minn]++]=R[i]; //对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
for(int i=0;i<10;++i) R[i]=C[i]； //对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
}
11.桶排序（Bucket sort）
参考：http://www.cnblogs.com/skywang12345/p/3602737.html
代码：
#include <iostream>
#include <cstring>
using namespace std;
/*
* 参数说明：
* a -- 待排序数组
* n -- 数组a的长度
* max -- 数组a中最大值的范围
*/
void bucketSort(int* a, int n, int max)
{
int i, j;
int *buckets;
if (a==NULL || n<1 || max<1)
return ;
// 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。
if ((buckets = new int[max])==NULL)
return ;
memset(buckets, 0, max*sizeof(int));
// 1. 计数
for(i = 0; i < n; i++)
buckets[a[i]]++;
// 2. 排序
for (i = 0, j = 0; i < max; i++)
while( (buckets[i]--) >0 )
a[j++] = i;
delete[] buckets;
}
int main()
{
int i;
int a[] = {8,2,3,4,3,6,6,3,9};
int ilen = (sizeof(a)) / (sizeof(a[0]));
cout << "before sort:";
for (i=0; i<ilen; i++)
cout << a[i] << " ";
cout << endl;
bucketSort(a, ilen, 10); // 桶排序
cout << "after sort:";
for (i=0; i<ilen; i++)
cout << a[i] << " ";
cout << endl;
return 0;
}
12.基数排序（radix sort）
注意一下从桶中还原到数组中时是从底部开始
代码：
#include <iostream>
using namespace std;
int R[] = {-1,134,565,698,322,461,577,678,343,657,244,899,910};//定义数组
int T[13];//用来表示链
struct T_node{//声明桶结构体
int h;//声明首指针
int r;//声明尾指针
};
struct T_node Ts[10];//10个桶
int get_ki(int x,int i){//x表示具体数字，i表示位置
int d,j,k;
for(d=1,j=0;j<=i;d=d*10,j++);//个、十、百位循环三次
k=(x%d)/(d/10);//取余数，得到个/十/百位上的那个数
return k;//返回该位置上的数
}
void print_data(){//输出函数
int h;
h = T[0];//把T[0]记录在h里
while(h!=0){//只要不空，表示有数字，就输出
cout<<R[h]<<' ';
h = T[h];
}
cout<<endl;
}
int main(int argc, char** argv) {
int i,j,h,hh,r,k;
for(i=0;i<13;i++)
T[i] = i+1;
T[12] =0;
print_data();
for(i=0;i<3;i++){
for(j=0;j<10;j++)
Ts[j].h = Ts[j].r = -1;//清桶
h = T[0];//抓住链的头部
while(h!=0){
hh = T[h]; T[h] = 0;//抓住h后面的尾巴,hh可以记录后面的数据，把T[h]孤立出来
k = get_ki(R[h],i);
if(Ts[k].h == -1) //放桶 如果是空桶
Ts[k].h = Ts[k].r = h;
else{//如果不是空桶，接在尾巴的后边，把h接在R的后面
T[Ts[k].r] = h;
Ts[k].r = h;
}
h = hh; //后面的弟兄又接上了
}
for(j=0;Ts[j].h == -1;j++); //求非空桶，做完后出现第一个非空的桶。
T[0] = Ts[j].h; //把非空桶作为链的头
r = Ts[j].r;//把r变成尾巴
for(j = j+1;j<10;j++)
if(Ts[j].h!=-1){
T[r] = Ts[j].h;
r = Ts[j].r;//r成为新的尾巴
}
T[r] = 0;//使尾巴为0
print_data();
}
return 0;
}
排序的稳定性
不稳定：
选择排序（selection sort）— O(n2)
快速排序（quicksort）— O(nlogn) 平均时间, O(n2) 最坏情况; 对于大的、乱序串列一般认为是最快的已知排序
堆排序 （heapsort）— O(nlogn)
希尔排序 （shell sort）— O(nlogn)
基数排序（radix sort）— O(n*k); 需要 O(n) 额外存储空间 （K为特征个数）
稳定：
插入排序（insertion sort）— O(n2)
冒泡排序（bubble sort） — O(n2)
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外存储空间
二叉树排序（Binary tree sort） — O(nlogn); 需要 O(n) 额外存储空间
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1
桶排序 （bucket sort）— O(n); 需要 O(k) 额外存储空间