C/C++的8种排序算法及实现
首先说下稳定排序和非稳定排序，简单地说就是所有相等的数经过某种排序方法后，
仍能保持它们在排序之前的相对次序，我们就说这种排序方法是稳定的。反之，就是非稳定的。
几个基本常见的排序，插入排序（包括直接插入，希尔插入，折半插入等），交换排序（包括冒泡排序，快速排序），选择排序（简单选择，堆排序，树形排序等），归并排序，基数排序（多关键字，链式基数）。
1.直接插入排序（稳定排序）
简单的说就是将序列分为有序序列和无序序列。每一趟排序都是将无序序列的第一个元素插入有序序列中。R[1… i-1] <- R[i…n] , 每次取R[i]插入到R[1… i-1]中。
步骤如下：
1> 在R[1 … i-1]中找到R[i]的插入位置k （0
2> 将R[k … i-1]均后移一位，K位置上插入R[i]
改进版：
1>在R[1 … i-1]中将R[i]从右向左一一比较，R[j] >R[i],则R[j]后移一位（j = i-1开始）
2>如果R[j] <=R[i],则j+1 为R[i]的插入位置
实现如下(包括测试)：
#include
using namespace std;
void insert_sort(int a[],int len)
{
int i=0,j=0,temp=0;
for(i=1;i=0&&temp
2.希尔排序（不稳定排序）
希尔排序算法是先将要排序的一组数按照某个增量d分成若干组，对每组中的元素进行排序，然后在用更小的增量来进行再次分组，并给每个分组重新排序，直到增量为1时，整个要排序的数被分成一组，排序结束。
形象点说，例如[R1 ,R2 , R3, R4,R5,R6,R7,R8]，先增量d =len/2 =4 ,则先分成[R1 R5] ,[R2 R6] ,[R3 R7] ,[R4 R8]四组，进行组内排序；再d=d/2 =2,分成[R1 R3 R5R7] 和 [R2 R4 R6 R8]两组，组内排序；再d=d/2=1,整个数组只剩一个大的分组[R1 , R2 , R3, R4,R5,R6,R7,R8]，组内排序。全部结束。
实现如下(包括测试)：
#include
using namespace std;
void shell_sort(int a[],int len)
{
int d,i,j,temp;
for(d=len/2;d>0;d=d/2)
{
for(i=d;i=0&&temp<a[j];j-=d) {="" a[j+d]="a[j];" }="" void="" print_array(int="" a[],int="" len)="" for(int="" i="0;i
3.冒泡排序（稳定排序）
冒泡排序也叫起泡排序，顾名思义，就是每一趟，从左到右，两两比较，大的（小的）后移，最后最轻的气泡到最后的位置R[i]，为最大或最小值，然后下一趟，选出次大的到R[i-1]，以此，到最后R[1]，至此全部有序。（按照递增递减都可以）
实现如下：
/*a[0]..从a[0]最小开始 */
void bubble_sort(int a[],int len){
inti,j,temp;
for(i=0;i=i;j--){
if(a[j+1]=i;j--){
if(a[j+1]
4.快速排序（不稳定排序）
快速排序是一种划分交换排序，采用的是分治法的策略。该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
下面借助这篇文章的步骤描述，就会很好理解快速排序每一趟到底怎么走的：
来源：http://blog.csdn.net/liuchen1206/article/details/6954074
以一个数组作为示例，取区间第一个数为基准数(pivot)。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
72 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
初始时，i = 0; j =9; X = a[i] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8];i++;这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3];j--;
数组变为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
48 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
88 |
85 |
i = 3; j =7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
48 |
6 |
57 |
42 |
60 |
72 |
83 |
73 |
88 |
85 |
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。a[5]已经确定好位置。后面每一趟也是。
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
具体实现如下（测试不重复，在前面的代码上加个函数，都测试过）：
/*这里的low和high是数组的头和尾的下标*/
void quick_sort(int a[],int low,int high)
{
int i,j,pivot;
if(low=pivot)
j--;
if(i
5.直接选择排序（不稳定排序）
选择排序的基本思想：每一次从待排序的记录中选出关键字最小的记录，顺序的放在有序的序列的最后，直至全部记录排序完毕。
而直接选择排序就是n条记录经过n-1次后，直接得到有序记录。
实现如下：
void select_sort(int a[],int len)
{
inti,j,min,k; //min保存最小数，k记录最小数的位置
for(i=0;i
6.堆排序（不稳定排序）
堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将A[n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。
堆的定义如下：n个关键字序列A[n]成为堆，当且仅当该序列满足：
①L(i) <= L(2i)且L(i) <= L(2i+1) 或者 ②L(i) >=L(2i)且L(i) >= L(2i+1) 其中i属于[1, n/2]。
满足第①种情况的堆称为小根堆（小顶堆），满足第②种情况的堆称为大根堆（大顶堆）。
如上的小根堆或大根堆，输出堆顶的最小（大）值之后，使得剩下的n-1个元素的序列重新建成一个新的堆，则又得到n个数中的次小（大）值，如此反复，最后得到的有序序列，这个过程就是堆排序。
代码实现：
void swap(int *a ,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void HeapAdjust(int a[],int i)
{
int left = 2*i+1;//左孩子节点
int right = 2*i + 2;//右孩子节点
int max = 0;//暂存最大元素下标
if(left <=heapsize && a[left] >a[i])
max = left;
else
max = i;
if(right <= heapsize&& a[right] > a[max])
max = right;
if(max != i)//表明当前的父节点并不是最大的
{
swap(&a[i],&a[max]);
HeapAdjust(a,max);//有交换就要递归把子树也整成最大堆
}
}
void BuildHeap(int a[],int len)
{
int i = 0;
heapsize = len;
for( i = len/ 2;i >=0;i--)//非叶节点最大下标为/2
{
HeapAdjust(a,i);
}
}
//堆排序对要排序的序列有个要求就是下标是从1开始到size的，而并非常用的0~size-1
void heap_sort(int a[],int len)
{
int i;
BuildHeap(a,len-1);//先建立初始的最大堆
for( i = len-1;i >=1;i--)
{
swap(&a[0],&a[i]);//把最大的元素放到最后面
heapsize--;//不再包括最大的元素
HeapAdjust(a,0);
}
//至此数组就已经从小到大排好序了,
//如果要从大到小输出，则倒着输出就行了；
//而如果要将序列从大到小排序，则应建立最小堆。
}
7.归并排序（稳定排序）
归并是指将若干个已排序的子文件合并成一个有序的文件。常见的归并排序有两路归并排序。
归并操作的基本步骤如下：
1.申请两个与已经排序序列相同大小的空间，并将两个序列拷贝其中；
2.设定最初位置分别为两个已经拷贝排序序列的起始位置，比较两个序列元素的大小，依次选择相对小的元素放到原始序列；
3.重复2直到某一拷贝序列全部放入原始序列，将另一个序列剩下的所有元素直接复制到原始序列尾。
设归并排序的当前区间是R[low..high]，三个步骤分别是：
1.分解：将当前区间一分为二，即求分裂点
2.求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
3.组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
递归的终结条件：子区间长度为1（一个记录自然有序）。
代码实现：
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];
int i, j, k;
for (i=0; i
8. 基数排序（可靠排序）
http://blog.csdn.net/u012580566/article/details/47702955
实现如下：
int maxbit(int data[], int n)
{
int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int tmp[n];
int count[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
}