C语言实现排序算法及详解

GuoYanjun2015-12-012015-12-01

文/一月筠 -- 转载请注明 --
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存…

相关概念
交换排序—冒泡排序 (Bubble Sort)
插入排序—直接插入 (Straight Insertion Sort)
插入排序—二分插入
选择排序—简单选择排序 (Simple Selection Sort)
插入排序—希尔排序 (Shell Sort)
归并排序 (Merge Sort)
交换排序—快速排序 (Quick Sort)
选择排序—堆排序 (Heap Sort)

交换排序—冒泡排序 (Bubble Sort)

如果序列是从小到大排列好的，那么任意两个相邻元素，都应该满足a[i-1] <= a[i]的关系。在冒泡排序时，我们从右向左遍历数组，比较相邻的两个元素。如果两个元素的顺序是错的，那么就交换这两个元素。如果两个元素的顺序是正确的，则不做交换。经过一次遍历，我们可以保证最小的元素(泡泡)处于最左边的位置。

经过一次遍历，冒泡排序并不能保证所有的元素已经按照从小到大的排列好。因此，我们需要重新从右向左遍历数组元素，并进行冒泡排序。这一次遍历，我们不用考虑最左端的元素。然后继续进行最多为n-1次的遍历。

如果某次遍历过程中，元素都没有发生交换，那么说明数组已经排序好，可以中止停止排序。最坏的情况是在起始数组中，最大的元素位于最左边，那么冒泡算法必须经过n-1次遍历才能将数组排列好，而不能提前完成排序。

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

冒泡排序示例

算法实现

//传统冒泡排序  
void maopao(int a[],int n)  
{  
    for(int i=0;i<n-1;i++)  
        for(int j=0;j<n-i-1;j++)  
            if(a[j]>a[j+1])  
            {  
                int t=a[j];  
                a[j]=a[j+1];  
                a[j+1]=t;  
            }  
}

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

方法一：设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

//冒泡排序改进1，添加标志位，如果某一次排序中出现没有交换位置，说明排序完成  
void maopao(int a[],int n)  
{  
    int flag=0;  
    for(int i=0;i<n-1;i++)  
    {  
        flag=0;  
        for(int j=0;j<n-i-1;j++)  
            if(a[j]>a[j+1])  
            {  
                int t=a[j];  
                a[j]=a[j+1];  
                a[j+1]=t;  
                flag=1;  
            }  
        if(flag==0)  
            break;  
    }  
}

方法二：传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
改进后的算法实现为:

//冒泡改进3，传统冒泡每趟排序遍历一次找到一个最大值或者最小值，如果每趟遍历两次就会找打一个最大值和一个最小值，减少了一半的排序趟数  
void maopao ( int r[], int n){    
    int low = 0;     
    int high= n -1; //设置变量的初始值    
    int tmp,j;    
    while (low < high) {    
        for (j= low; j< high; ++j) //正向冒泡,找到最大者    
            if (r[j]> r[j+1]) {    
                tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;    
            }     
        --high;                 //修改high值, 前移一位    
        for ( j=high; j>low; --j) //反向冒泡,找到最小者    
            if (r[j]<r[j-1]) {    
                tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;    
            }    
        ++low;                  //修改low值,后移一位    
    }     
}

插入排序—直接插入排序(Straight Insertion Sort)

假设在新生报到的时候，我们将新生按照身高排好队(也就是排序)。如果这时有一名学生加入，我们将该名学生加入到队尾。如果这名学生比前面的学生低，那么就让该学生和前面的学生交换位置。这名学生最终会换到应在的位置。这就是插入排序的基本原理。

对于起始数组来说，我们认为最初，有一名学生，也就是最左边的元素(i=0)，构成一个有序的队伍。

随后有第二个学生(i=1)加入队伍，第二名学生交换到应在的位置；随后第三个学生加入队伍，第三名学生交换到应在的位置…… 当n个学生都加入队伍时，我们的排序就完成了。

基本思想

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。
直接插入排序示例：

排序示例

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：

//直接插入排序：将第一个数据看做一个顺序表，将后面的数据一次插入表中  
void InsertSort(int a[], int n)    
{    
    for(int i= 1; i<n; i++){    
        if(a[i] < a[i-1]){  //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入    
            int j= i-1;   //表中最后一个数据  
            int x = a[i];  //复制为哨兵，即存储待排序元素    
            a[i] = a[i-1];  //先后移一个元素 (因为a[i]就是X，所以不怕丢失)   
            while(j>=0 && x < a[j]){  //查找在有序表的插入位置  (遍历表)  
                a[j+1] = a[j];    
                j--;  //元素后移    
            }    
            a[j+1] = x;  //插入到正确位置    
        }    
    }    
        
}

或者

void InsertSort ( int arr[],int count)
    {
            int i,j,temp;
        for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
        {
            temp = arr[i];//操作当前元素，先保存在其它变量中
            for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
            {
                arr[i] = arr[j];
                arr[j] = temp;
            }
    }
}

效率

时间复杂度：O(n^2)
其他的插入排序有二分插入排序，2-路插入排序。

插入排序—二分插入

将有序数列折半，看看插入到哪个序列中去

//折半插入  
void BInsertSort(int a[], int n)    
{    
    for(int i= 1; i<n; i++){    
        int low=0,high=i;  
        if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入    
            int x = a[i];        //复制为哨兵，即存储待排序元素    
            a[i] = a[i-1];           //先后移一个元素 (因为a[i]就是X，所以不怕丢失)   
            while(low<=high){  //查找在有序表的插入位置  (遍历表)  
                int m=(low+high)/2;  
                if(x<a[m])  high=m-1;  
                else low=m+1;  
            }    
            for(int j=i-1;j>=high+1;j--)  
                a[j+1]=a[j];  
            a[j+1] = x;      //插入到正确位置    
        }    
    }    
        
}

选择排序—简单选择排序 (Selection Sort)

排序的最终结果：任何一个元素都不大于位于它右边的元素 (a[i] <= a[j], if i <= j)。所以，在有序序列中，最小的元素排在最左的位置，第二小的元素排在i=1的位置…… 最大的元素排在最后。

选择排序是先找到起始数组中最小的元素，将它交换到i=0；然后寻找剩下元素中最小的元素，将它交换到i=1的位置…… 直到找到第二大的元素，将它交换到n-2的位置。这时，整个数组的排序完成。

基本思想

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

选择排序是不稳定的。算法复杂度O(n2)–[n的平方]

简单选择排序的示例：

简单选择排序示例

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推…..
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。

算法实现

//简单选择排序：遍历一次找到最小与第一个元素呼唤位置，再从第二个元素开始遍历找到最小与第二个元素呼唤位置...  
void SelectSort(int a[],int n)  
{  
    for(int i=0;i<n-1;i++)  
    {  
        int k=i;//记录最小的那个下标的  
        for(int j=i+1;j<n;j++)  
            if(a[j]<a[k])  
                k=j;  
        if(k!=i)  
        {  
            int t=a[i];  
            a[i]=a[k];  
            a[k]=t;  
        }  
  
    }  
}

插入排序—希尔排序 (Shell Sort)

我们在冒泡排序中提到，最坏的情况发生在大的元素位于数组的起始。这些位于数组起始的大元素需要多次遍历，才能交换到队尾。这样的元素被称为乌龟(turtle)。

乌龟元素的原因在于，冒泡排序总是相邻的两个元素比较并交换。所以每次从右向左遍历，大元素只能向右移动一位。(小的元素位于队尾，被称为兔子(rabbit)元素，它们可以很快的交换到队首。)

希尔排序是以更大的间隔来比较和交换元素，这样，大的元素在交换的时候，可以向右移动不止一个位置，从而更快的移动乌龟元素。比如，可以将数组分为4个子数组（i=4k, i=4k+1, i=4k+2, i=4k+3），对每个子数组进行冒泡排序。比如子数组i=0，4，8，12…。此时，每次交换的间隔为4。

完成对四个子数组的排序后，数组的顺序并不一定能排列好。希尔排序会不断减小间隔，重新形成子数组，并对子数组冒泡排序…… 当间隔减小为1时，就相当于对整个数组进行了一次冒泡排序。随后，数组的顺序就排列好了。

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序。

基本思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法

1、选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2、按增量序列个数k，对序列进行k 趟排序；
3、每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：
希尔排序示例

算法实现

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

//希尔排序：去增量为d1的分为一组，共分成d1组分别进行插入排序，然后每组对应元素放在一起，然后取d2...知道d=1  
void ShellSort(int a[],int n)  
{  
    int dk;  
    int tmp;  
    for(dk=n/2;dk>0;dk/=2)  
        for(int i=dk;i<n;i++)  
        {  
            tmp=a[i];  
            for(int j=i;j>=dk;j-=dk)  
                if(tmp<a[j-dk])  
                    a[j]=a[j-dk];  
                else break;  
            a[j]=tmp;  
        }  
}

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

归并排序 (Merge Sort)

如果我们要将一副扑克按照数字大小排序。此前已经有两个人分别将其中的一半排好顺序。那么我们可以将这两堆扑克向上放好，假设小的牌在上面。此时，我们将看到牌堆中最上的两张牌。

我们取两张牌中小的那张取出放在手中。两个牌堆中又是两张牌暴露在最上面，继续取小的那张放在手中…… 直到所有的牌都放入手中，那么整副牌就排好顺序了。这就是归并排序。

基本思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序示例：

归并排序示例

下面的实现中，使用递归：

//归并排序  
void copyArray(int source[], int dest[],int len,int first)    
{    
    int i;    
    int j=first;    
    for(i=0;i<len;i++)    
    {    
        dest[j] = source[i];    
        j++;    
    }    
            
}   
//相邻两个有序子序列的归并函数，将a[low...mid]和a[mid+1...high]归并到T[LOW..high]中   
void merge(int a[],int left,int right)    
{    
    int begin1 = left;    
    int mid = (left+right)/2 ;    
    int begin2 = mid+1;    
    int k=0;    
    int newArrayLen = right-left+1;    
    int *b = (int*)malloc(newArrayLen*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++];    
    copyArray(b,a,newArrayLen,left);    
    free(b);    
}    
//归并函数,将a[low...high]归并到T[low...high]中  
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);    
    }    
}   
void MergeSort(int a[],int n)  
{  
    mergeSort(a,0,n-1);  
}

交换排序—快速排序 (Quick Sort)

我们依然考虑按照身高给学生排序。在快速排序中，我们随便挑出一个学生，以该学生的身高为参考(pivot)。然后让比该学生低的站在该学生的右边，剩下的站在该学生的左边。

很明显，所有的学生被分成了两组。该学生右边的学生的身高都大于该学生左边的学生的身高。

我们继续，在低身高学生组随便挑出一个学生，将低身高组的学生分为两组(很低和不那么低)。同样，将高学生组也分为两组(不那么高和很高)。

如此继续细分，直到分组中只有一个学生。当所有的分组中都只有一个学生时，则排序完成。

基本思想

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。
3）此时基准元素在其排好序后的正确位置
4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
快速排序的示例：
（a）一趟排序的过程：

一趟排序的过程

（b）排序的全过程

排序的全过程

算法实现

在下面的实现中，使用递归:

//快速排序   
//第一个参数要排的数组，第二个参数第一个数，第三个参数数组成员个数  
void kuaipai(int array[],int low,int hight)  
{  
    int i,j,t,m;  
    if(low<hight)  
    {  
        i=low;  
        j=hight;  
        t=array[low];//第一个数为轴  
        while(i<j)  
        {  
            while(i<j && array[j]>t)//从右边找出小于轴的数  
                j--;  
            if(i<j)//将小于轴的数array[j]放到左边array[i]的位置  
            {  
                m=array[i];  
                array[i]=array[j];  
                array[j]=m;  
                i++;  
            }  
            while(i<j && array[i]<=t)//从左边找出大于轴的数  
                i++;  
            if(i<j)//将大于轴的数array[i]放在右边array[j]的位置  
            {  
                m=array[j];  
                array[j]=array[i];  
                array[i]=m;  
                j--;  
            }     
        }  
          
        array[i]=t;//轴放在中间,现在就有两个区域了分别是[0 i-1]和[i+1 hight],分别快排  
        kuaipai(array,0,i-1);  
        kuaipai(array,i+1,hight);  
    }  
}

分析

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

理想的pivot是采用分组元素中的中位数。然而寻找中位数的算法需要另行实现。也可以随机选取元素作为pivot，随机选取也需要另行实现。为了简便，我每次都采用中间位置的元素作为pivot。

选择排序—堆排序 (Heap Sort)

堆(heap)是常见的数据结构。它是一个有优先级的队列。最常见的堆的实现是一个有限定操作的Complete Binary Tree。这个Complete Binary Tree保持堆的特性，也就是父节点(parent)大于子节点(children)。因此，堆的根节点是所有堆元素中最小的。堆定义有插入节点和删除根节点操作，这两个操作都保持堆的特性。

我们可以将无序数组构成一个堆，然后不断取出根节点，最终构成一个有序数组。

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想

堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。

若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：
(a)大顶堆序列：（96, 83,27,38,11,09)
(b)小顶堆序列：（12，36，24，85，47，30，53，91）

堆顶元素

算法实现

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

//堆排序:树形选择排序，将带排序记录看成完整的二叉树，第一步：建立初堆，第二步：调整堆  
//第二步：调整堆  
void HeapAdjust(int a[],int s,int n)  
{  
    //调整为小根堆，从小到大  
    int rc=a[s];  
    for(int j=2*s;j<=n;j*=2)  
    {  
        if(j<n && a[j]>a[j+1])//判断左右子数大小  
            j++;  
        if(rc<=a[j])  
            break;  
        a[s]=a[j];  
        s=j;  
    }  
    a[s]=rc;  
}  
//第一步：建初堆  
void CreatHeap(int a[],int n)  
{  
    //小根堆  
    for(int i=n/2;i>0;i--)  
        HeapAdjust(a,i,n);  
}  
//整合  
void HeapSort(int a[],int n)  
{  
    CreatHeap(a,n);//第一步，建立初堆  
    for(int i=n;i>1;i--)  
    {  
        int x=a[1];//堆顶与最后一个元素互换  
        a[1]=a[i];  
        a[i]=x;  
        HeapAdjust(a,1,i-1);  
    }  
  
}

分析

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

总结

除了上面的算法，还有诸如Bucket Sorting, Radix Sorting涉及。我会在未来实现了相关算法之后，补充到这篇文章中。相关算法的时间复杂度分析可以参考书目中找到。我自己也做了粗糙的分析。如果博客园能支持数学公式的显示，我就把自己的分析过程贴出来，用于引玉。

上面的各个代码是我自己写的，只进行了很简单的测试。如果有错漏，先谢谢你的指正。

最后，上文中用到的交换函数为：

/* By Vamei */
/* exchange the values pointed by pa and pb*/
void swap(int *pa, int *pb)
{
  int tmp;
  tmp = *pa;
  *pa = *pb;
  *pb = tmp;
}

几种排序算法的比较和选择

时间复杂度和空间复杂度

选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
一些建议：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于”比较”的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。