排序算法小结

roger

　　网上关于排序算法的总结太多了，这篇文章就写得不错。
　　http://m.blog.csdn.net/blog/likaiwalkman/23713373
　　经典就是经典，个人觉得这些经典的算法被反复研究几十遍都不为过。同时也参考了很经典的书籍《数据结构与算法分析——C语言描述》，温故而知新，每次回头看这些算法的时候都为其中博大精深的思想所折服，呵呵，不扯了。这里只贴出一份用代码敲出来的各个排序算法，纯粹是想练一下手。主要关注快排和堆排序。

交换排序
快速排序　　快排的算法思想很精妙，经常在俩指针问题中用到。
　　假设待排序的元素个数为n，分别存放在数组a[1,…,n]中，令第一个元素为参考元素(称为枢纽元，pivot)，pivot=a[1]，初始时，i=1，j=n，按照以下方法操作：
　　(1)    从第j个元素开始向前依次将每个元素与枢纽元pivot比较。如果当前元素大于等于pivot，则比较前一个元素与pivot，即比较a[j-1]与pivot；否则，将当前元素移动到第i个位置，并转到步骤(2)。
　　(2)    从第i个元素开始向后依次将每个元素与枢纽元pivot比较。如果当前元素小于pivot，则比较后一个元素与pivot，即比较a[i+1]与pivot；否则，将当前元素移动到第j个位置，并转到步骤(3)。
　　(3)    重复执行(1)和(2)，直到出现i>=j，将元素移动到a中。此时，整个元素序列被划分成两个部分，第i个位置之前的元素都小于a，第i个位置后的元素都大于等于a。至此，完成一趟快速排序。
　　按照以上的方法，将每个部分都进行类似的划分操作，直到每个部分都只有一个元素为止，这样整个元素序列就构成了一个有序的序列。

#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void quicksort(int a[],int start,int end)//对a[start]到a[end]的元素进行排序 
{
int i=start,j=end;
int temp;
if(start<end)
{
temp=a[start];
while(i!=j)
{
while(j>i&&a[j]>=temp)
j--;
a[i]=a[j];
while(i<j&&a[i]<=temp)
i++;
a[j]=a[i];
}
a[i]=temp;
quicksort(a,start,i-1);
quicksort(a,i+1,end);
} 
}
int main()
{
int a[]={17,1,5,6,98,78,79,54,32,11,15,14,13,20,29};
int n=sizeof(a)/sizeof(a[0]);
quicksort(a,0,n-1);
print(a,n);
return 0;
}

冒泡排序

#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={1,5,78,94,48,34,32,47,55,96,19,5};
int n=sizeof(a)/sizeof(a[0]);
int i,j,temp,flag=1;
for(i=0;i<n&&flag;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp; 
flag=1;
}
}
print(a,n);
}
return 0;
}

选择排序　　选择排序的算法思想很简单，从待排序的元素中选择最小(最大)的元素放在已经排序的序列的最后，直到全部排完为止。

堆排序　　关于堆排序，C++的STL中已经提供了很成熟的函数，像入堆push_heap、创建堆make_heap、出堆pop_heap，判断是否为堆is_heap，堆排序sort_heap等，实际应用中可以直接调用。但是，算法的思想还是要掌握的。
　　假设一个大根堆中有n个元素，如果将堆中的根节点元素输出后，再将剩下的n-1个元素重新建立成一个新堆，并将根节点元素输出，然后将剩下的n-2元素重新建立成堆，重复执行以上过程，直到堆中没有元素为止。所以堆排序的关键就是创建堆和调整堆。
　　建立大根堆的算法思想大概过程是这样的。从位于元素序列中的最后一个一个非叶子结点，即第n/2向下取整个元素开始，逐层比较并调整元素的位置，使其满足a>=a[2*i]且a>=a[2*i+1]，直到根节点为止。假设当前结点的序号为i，则当前元素为a，其左右孩子结点分别为a[2*1]和a[2*i+1]。将a[2*1]和a[2*i+1]较大者与a比较，如果孩子结点元素值大于当前结点值，则交换两者；否则，不进行交换。逐层向上执行此操作，直到根节点为止，这样就建立了一个大根堆。建立小根堆的算法与此类似。
　　调整堆其实也是重新建立堆的过程。除了堆顶元素外，剩下的元素本身就具有a>=a[2*i]且a>=a[2*i+1]，(i=1,2,3,…,[n/2]向下取整)的性质，也就是说剩下的元素由大到小逐层排列。所以，将剩下的元素调整成大根堆只需要从上往下逐层比较，找出最大的元素将其放在根节点的位置上就可以构成新的大根堆了。
　　调整堆的大概过程是这样的。输出堆顶元素可以将堆顶元素放在堆的最后，也就是将第一个元素与最后一个元素交换，即a[1]与a[n]交换一下，那么，接下来需要调整的元素就是a[1,…,n-1]。从根节点开始，如果其左、右子树结点元素值大于根节点元素值，选择较大的一个与根节点进行交换，否则，不交换。逐层重复执行这个操作，直到叶子结点，就完成了堆的调整，构成了一个新的堆。

#include<iostream>
//#include<algorithm>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void adjustheap(int a[],int low,int high)//调整a[low,high]，使其成为堆
{
int i=low,j=2*i;//j指向i的左孩子结点 
int temp=a[i];//根节点暂存临时变量中
while(j<=high)
{
if(j<high&&a[j]<a[j+1])//右孩子较大
j++;
if(temp<a[j])
{
a[i]=a[j];
i=j;//修改i和j的值，以便继续向下筛选 
j=2*i;
} 
else
break; 
}
a[i]=temp;
}
/*void adjustheap(int a[],int s,int m)
{
int t,j;
t=a[s];
for(j=2*s+1;j<=m;j*=2+1)
{
if(j<m&&a[j]<a[j+1])
j++;
if(t>a[j])
break;
a[s]=a[j];
s=j;
}
a[s]=t;
} */

void heapsort(int a[],int n)
{
int i,temp;
for(i=n/2;i>=1;i--)//创建堆 
adjustheap(a,i,n);
for(i=n;i>1;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
adjustheap(a,1,i-1);
}
}

int main()
{
int a[]={0,11,12,54,47,86,87,98,75,34,70};
int n=sizeof(a)/sizeof(a[0]);
//make_heap(a,a+n);
//sort_heap(a,a+n);
heapsort(a,n-1);
print(a,n);
return 0;
}

　　注：细心的人，会发现上面的程序有个问题，在创建和调整堆的过程中，下标的对应容易出问题，即数据下标是从1开始的。调用C++ STL中的相关函数接口，就没这个问题。上面的程序是对着教材敲的，没仔细看这个问题，纠结了好久，呵呵。
　　这个版本就没问题。

#include <stdio.h>
void exch(int& a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

void fixdown(int a[], int k, int N)
{
    while(2*k <= N)
    {
        int j=k*2;
        if(j<N && a[j]<a[j+1]) j++;
        if(!(a[k]<a[j])) break;
        exch(a[k], a[j]);
        k = j;
    }
}
void heapsort(int a[], int l, int r)
{
    int k, N=r-l+1;
    int *pq = a+l-1; //notice!
    for(k = N/2; k>=1; k--)
        fixdown(pq, k, N);
    while(N>1)
    {
        exch(pq[1], pq[N]);
        fixdown(pq, 1, --N);
    }
}
int main()
{
    int a[10] = {11,12,54,47,86,87,98,75,34,70};
    heapsort(a, 0, 9);
    for(int i=0; i<10; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

　　注：参考了这篇文章
　　http://www.cnblogs.com/wouldguan/archive/2012/11/12/2766070.html
简单选择排序

#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void selectsort(int a[],int n)
{
int i,j,k;
int temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[k])
k=j;//k记录最小元素的位置 
}
if(k!=i)
{
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
int main()
{
int a[]={11,12,54,47,86,89,98,75,34,59};
int n=sizeof(a)/sizeof(a[0]);
selectsort(a,n);
print(a,n); 
return 0;
}

插入排序直接插入排序

//直接插入排序，属于稳定的排序算法
#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={17,46,32,15,1,10,6,7,9,18};
int n=sizeof(a)/sizeof(a[0]);
int temp,i,j;
for(i=1;i<n;i++)
{
temp=a[i];//取出待排元素放入临时变量 
for(j=i-1;j>=0&&temp<a[j];j--)//寻找插入位置 
{
a[j+1]=a[j];
}
a[j+1]=temp;
print(a,n);
}
return 0;
}

折半插入排序

#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={1,48,46,57,98,96,16,13,18,29,30,45,47};
int n=sizeof(a)/sizeof(a[0]);
int temp,i,j,low,high,mid;
for(i=1;i<n;i++)
{
temp=a[i];//待排元素放入临时变量 
for(low=0,high=i-1;high>=low;)//寻找插入位置 
{
mid=(low+high)/2;
if(temp<a[mid])
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=low;j--)//元素移动 
a[j+1]=a[j];
a[low]=temp;
print(a,n);
}
return 0;
}

希尔排序　　与直接插入排序、折半插入排序相比，希尔排序将待排序的元素划分为若干个子序列，在每个组内进行直接插入排序。

#include<iostream>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
int main()
{
int a[]={1,5,78,94,48,34,32,47,55,96,19,5};
int n=sizeof(a)/sizeof(a[0]);
int i,j,inc,temp;
for(inc=n/2;inc>0;inc/=2)
{
for(i=inc;i<n;i++)
{
temp=a[i];//取待排元素放入临时变量 
for(j=i;j>=inc;j-=inc)//组内进行插入排序，寻找插入位置 
{
if(temp<a[j-inc])
{
a[j]=a[j-inc];
}
else
    break;
}
a[j]=temp;
print(a,n);
}
}
return 0;
}

归并排序

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void copy(int source[],int dest[],int len,int start)
{
int i,j=start;
for(i=0;i<len;i++)
{
dest[j]=source[i];
j++;
}
}
void merge(int a[],int left,int right)
{
int begin1,begin2,mid,k=0,len,*b;
begin1=left;
mid=(left+right)/2;
begin2=mid+1;
len=right-left+1;
b=(int*)malloc(len*sizeof(int));
while(begin1<=mid&&begin2<=right)
{
if(a[begin1]<=a[begin2])
b[k++]=a[begin1++];
else
b[k++]=a[begin2++];
}
while(begin1<=mid)
b[k++]=a[begin1++];
while(begin2<=right)
b[k++]=a[begin2++];
copy(b,a,len,left);
}
void mergesort(int a[],int left,int right)
{
int i;
if(left<right)
{
i=(left+right)/2;
mergesort(a,left,i);
mergesort(a,i+1,right);
merge(a,left,right);
}
}
int main()
{
int a[]={11,12,54,47,86,89,98,75,34,59};
int n=sizeof(a)/sizeof(int);
mergesort(a,0,n-1);
print(a,n);
return 0;
}

　　除了以上几种算法以外，还有基数排序、桶排序、外部排序等等，不想写了，知道排序的思想就行。