排序

排序是基本的算法之一，也是在面试中被问的最多的问题。即将开始找工作，便趁此机会复习一下这些早已被忘却的知识（估计之后我还会忘记它）。

排序如果按照程序运行的地点，可将它分为内部排序和外部排序。内部排序即是数据都放在内存中，但是有时候我们的数据量很大内存无法容纳，就需要将数据放在磁盘中，然后分段放入内存中排序。

排序算法有稳定和不稳定之分。所谓稳定性即是当序列中有两个相同的数据时，排序前和排序后它俩的顺序不变，能实现这种情况的排序算法我们说他是稳定的。

插入排序

基本思想

插入排序的基本思想是将一个记录插入到已经排好序的序列中，它默认将第一个元素视为一个已经排好序的序列，后面的元素从后向前逐个扫描，插入到相应位置。时间复杂度O(n^2),空间复杂度O(1)。这种排序是稳定的。

操作步骤

• 从第一个元素开始，该元素可以认为已经被排序
• 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 将新元素插入到该位置后
• 重复步骤2~5

代码示例

public void sort(){
        int temp;
        for(int i = 1; i<arraytoSort.length; i++){
            for(int j = i-1; j>=0; j--){
                if( arraytoSort[j+1] < arraytoSort[j] ){
                    temp = arraytoSort[j+1];
                    arraytoSort[j+1] = arraytoSort[j];
                    arraytoSort[j] = temp;
                }   
            }   
        }
    }

希尔排序

希尔排序也是插入排序的一种，又叫缩小增量排序。这种排序会设置一个增量（这个增量决定排序效率的高低），然后根据这个增量将整个序列分为若干个子序列，我们可以将这些子序列排成一个增量长的表，分别对每列进行排序，这叫做一趟。然后增量递减，像上述这样进行多趟排序，直到增量为1，此时的最后一趟排序即为直接插入排序。

例如有这样的一组数[49,38,65,97,76,13,27,49,55,04],我们以初始增量为5来进行多趟排序，如下：

第一趟：（增量为5）

49 38 65 97 76
13 27 49 55 04

排序结果为:

13 27 49 55 04
49 38 65 97 76

合成一列为：[13,27,49,55,04,49,38,65,97,76]

第二趟：（增量为4）

13 27 49 55
04 49 38 65
97 76

排序结果：

04 27 38 55
13 49 49 65
97 76

合成一列为：[04,27,38,55,13，49，49，65，97，76]

第三趟：（增量为3）

04 27 38
55 13 49
49 65 97
76

排序结果：

04 13 38
49 27 49
55 65 97
76

合成一列为：[04,13,38,49,27,49,55,65,97,76]

第四趟：（增量为2）

04 13
38 49
27 49
55 65
97 76

排序结果：

04 13
27 49
38 49
55 65
97 76

合成一列为：[04,13,27,49,38,49,55,65,97,76]

最后一趟，增量为1，即为直接插入排序。此时序列已基本有序，排序效率大大提高。

结果：[04,13,27,38，49,49,55,65,76,97]

从结果能看到，希尔排序为不稳定排序。它的排序效率有所选择的增量决定。

代码示例

void print(int a[], int n ,int i){  
    cout<<i <<":";  
    for(int j= 0; j<8; j++){  
        cout<<a[j] <<" ";  
    }  
    cout<<endl;  
}  
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 缩小增量，如果是直接插入排序，dk=1
 *
 */  

void ShellInsertSort(int a[], int n, int dk)  
{  
    for(int i= dk; i<n; ++i){  
        if(a[i] < a[i-dk]){          //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  
            int j = i-dk;     
            int x = a[i];           //复制为哨兵，即存储待排序元素  
            a[i] = a[i-dk];         //首先后移一个元素  
            while(x < a[j]){     //查找在有序表的插入位置  
                a[j+dk] = a[j];  
                j -= dk;             //元素后移  
            }  
            a[j+dk] = x;            //插入到正确位置  
        }  
        print(a, n,i );  
    }  

}  

/**
 * 先按增量d（n/2,n为要排序数的个数进行希尔排序
 *
 */  
void shellSort(int a[], int n){  

    int dk = n/2;  
    while( dk >= 1  ){  
        ShellInsertSort(a, n, dk);  
        dk = dk/2;  
    }  
}  
int main(){  
    int a[8] = {3,1,5,7,2,4,9,6};  
    //ShellInsertSort(a,8,1); //直接插入排序  
    shellSort(a,8);           //希尔插入排序  
    print(a,8,8);  
}

简单选择排序

选择排序的思路很简单，即是扫描未排序的序列，然后将序列中最大（或者最小）的元素放在前面已经排好序的序列的末尾。时间复杂度O(n^2),空间复杂度O(1)。

代码示例

public void sort(){
        for(int i = 0; i<arraytoSort.length-1; i++){
            int min = i;
            int temp;
            //find min
            for(int j = i+1; j<arraytoSort.length ;j++){
                if(arraytoSort[j] <arraytoSort[min]){
                    min = j;
                    }
            }
            //swap the min with the ith element
            temp = arraytoSort[min];
            arraytoSort[min] = arraytoSort[i];
            arraytoSort[i] = temp;
        }
    }

简单选择排序的改进–二元选择排序

简单选择排序每趟循环只能确定一个元素的位置，我们可以考虑每趟循环确定两个元素的位置（当前趟最大和最小），从而减少排序所需的循环次数，来提升效率。

代码示例

void SelectSort(int r[],int n) {  
    int i ,j , min ,max, tmp;  
    for (i=1 ;i <= n/2;i++) {    
        // 做不超过n/2趟选择排序   
        min = i; max = i ; //分别记录最大和最小关键字记录位置  
        for (j= i+1; j<= n-i; j++) {  
            if (r[j] > r[max]) {   
                max = j ; continue ;   
            }    
            if (r[j]< r[min]) {   
                min = j ;   
            }     
      }    
      //该交换操作还可分情况讨论以提高效率  
      tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
      tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   

    }   
}

堆排序

堆排序也是选择排序的一种，但是其底层数据结构为树，效率比简单选择排序要高。其时间复杂度为O(nlog(n))。

堆是一棵完全二叉树，分为大顶堆和小顶堆。大顶堆即为根节点大于叶子节点的二叉树，小顶堆相反。堆排序即是每次将堆顶元素输出，剩余元素再建立一个堆，如此循环直到序列有序。

代码示例

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  



/**
 * 已知H[s…m]除了H[s] 外均满足堆的定义
 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
 *
 * @param H是待调整的堆数组
 * @param s是待调整的数组元素的位置
 * @param length是数组的长度
 *
 */  
void HeapAdjust(int H[],int s, int length)  
{  
    int tmp  = H[s];  
    int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
    while (child < length) {  
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
            ++child ;  
        }  
        if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点  
            s = child;       // 重新设置s ,即待调整的下一个结点的位置  
            child = 2*s+1;  
        }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
             break;  
        }  
        H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
    }  
    print(H,length);  
}  


/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */  
void BuildingHeap(int H[], int length)  
{   
    //最后一个有孩子的节点的位置 i=  (length -1) / 2  
    for (int i = (length -1) / 2 ; i >= 0; --i)  
        HeapAdjust(H,i,length);  
}  
/**
 * 堆排序算法
 */  
void HeapSort(int H[],int length)  
{  
    //初始堆  
    BuildingHeap(H, length);  
    //从最后一个元素开始对序列进行调整  
    for (int i = length - 1; i > 0; --i)  
    {  
        //交换堆顶元素H[0]和堆中最后一个元素  
        int temp = H[i]; H[i] = H[0]; H[0] = temp;  
        //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
        HeapAdjust(H,0,i);  
  }  
}   

int main(){  
    int H[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(H,10);  
    HeapSort(H,10);  
    //selectSort(a, 8);  
    cout<<"结果：";  
    print(H,10);  

}

冒泡排序

冒泡排序是交换排序的一种，和简单选择排序一样是最经典的排序算法，这两个也是笔者最先接触的两种排序算法。冒泡排序是依次比较相邻两个元素，大的下沉，小的上浮，就像气泡一样，因此叫做冒泡排序。它的时间复杂度和直接选择排序一样，都是O(n^2)。

代码示例

void bubbleSort(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 tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
            }  
        }  
    }  
}

冒泡算法的改进

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

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

改进后算法如下:

void Bubble_1 ( int r[], int n) {  
    int i= n -1;  //初始时,最后位置保持不变  
    while ( i> 0) {   
        int pos= 0; //每趟开始时,无记录交换  
        for (int j= 0; j< i; j++)  
            if (r[j]> r[j+1]) {  
                pos= j; //记录交换的位置   
                int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
            }   
        i= pos; //为下一趟排序作准备  
     }   
}

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

改进后的算法实现为:

void Bubble_2 ( 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值,后移一位  
    }   
}

快速排序

快速排序也是一种交换排序，它被称为最快的排序算法。

基本思想

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

代码示例

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  

void swap(int *a, int *b)  
{  
    int tmp = *a;  
    *a = *b;  
    *b = tmp;  
}  

int partition(int a[], int low, int high)  
{  
    int privotKey = a[low];                             //基准元素  
    while(low < high){                                   //从表的两端交替地向中间扫描  
        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
        swap(&a[low], &a[high]);  
        while(low < high  && a[low] <= privotKey ) ++low;  
        swap(&a[low], &a[high]);  
    }  
    print(a,10);  
    return low;  
}  


void quickSort(int a[], int low, int high){  
    if(low < high){  
        int privotLoc = partition(a,  low,  high);  //将表一分为二  
        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
    }  
}  

int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    cout<<"初始值：";  
    print(a,10);  
    quickSort(a,0,9);  
    cout<<"结果：";  
    print(a,10);  

}

归并排序

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

排序步骤：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

• j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
• 若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
  //选取r[i]和r[j]较小的存入辅助数组rf
• 如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵，否则，rf[k]=r[j]； j++； k++； 转⑵
  //将尚未处理完的子表中元素存入rf
• 如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空，如果j<=n , 将r[j…n] 存入rf[k…n] //后一子表非空
• 合并结束。

代码示例

void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
}

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

代码示例

void print(int a[], int n){  
    for(int j= 0; j<n; j++){  
        cout<<a[j] <<"  ";  
    }  
    cout<<endl;  
}  

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
{  
    int j,k;  
    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
        if(r[j] < r[i]) rf[k] = r[j++];  
        else rf[k] = r[i++];  
    }  
    while(i <= m)  rf[k++] = r[i++];  
    while(j <= n)  rf[k++] = r[j++];  
    print(rf,n+1);  
}  

void MergeSort(ElemType *r, ElemType *rf, int lenght)  
    int len = 1;  
    ElemType *q = r ;  
    ElemType *tmp ;  
    while(len < lenght) {  
        int s = len;  
        len = 2 * s ;  
        int i = 0;  
        while(i+ len <lenght){  
            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
            i = i+ len;  
        }  
        if(i + s < lenght){  
            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
        }  
        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
    }  
}  


int main(){  
    int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    int b[10];  
    MergeSort(a, b, 10);  
    print(b,10);  
    cout<<"结果：";  
    print(a,10);  

}

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)  
{   
    ElemType *rf2;  
    if(s==t) r[s] = rf[s];  
    else  
    {   
        int m=(s+t)/2;          /*平分*p 表*/  
        {   
        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
        MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
        Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
    }  
}  
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
{   /*对顺序表*p 作归并排序*/  
    MSort(r, rf,0, n-1);  
}

基数排序

说基数排序之前，我们先说桶排序：

基本思想

桶排序是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序 首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储 (10..20]的整数，……集合B[i]存储( (i-1)10, i10]的整数，i = 1,2,..100。总共有 100个桶。然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任 何排序法都可以。
最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这 样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序，那么整个算法的复杂度是:
O(n + m n/mlog(n/m)) = O(n + nlogn - nlogm)
从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：

• 首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

• 其次待排序的元素都要在一定的范围内等等。

桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。分配排序的基本思想：说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)

基于LSD方法的链式基数排序的基本思想

“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。

基数排序

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法实现

Void RadixSort(Node L[],length,maxradix)  
{  
   int m,n,k,lsp;  
   k=1;m=1;  
   int temp[10][length-1];  
   Empty(temp); //清空临时空间  
   while(k<maxradix) //遍历所有关键字  
   {  
     for(int i=0;i<length;i++) //分配过程  
    {  
       if(L[i]<m)  
          Temp[0][n]=L[i];  
       else  
          Lsp=(L[i]/m)%10; //确定关键字  
       Temp[lsp][n]=L[i];  
       n++;  
   }  
   CollectElement(L,Temp); //收集  
   n=0;  
   m=m*10;  
  k++;  
 }  
}

计数排序

我们希望能线性的时间复杂度排序，如果一个一个比较，显然是不实际的，书上也在决策树模型中论证了，比较排序的情况为nlogn 的复杂度。既然不能一个一个比较，我们想到一个办法，就是如果在排序的时候就知道他的位置，那不就是扫描一遍，把他放入他应该的位置不就可以了。 要知道他的位置，我们只需要知道有多少不大于他不就可以了吗？

算法实现

public int[] countsort(int A[]){
        int[] B = new int[A.length]; //to store result after sorting
        int k = max(A);
        int [] C = new int[k+1]; // to store temp
        for(int i=0;i<A.length;i++){    
            C[A[i]] = C[A[i]] + 1;
        }
        // 小于等于A[i]的数的有多少个, 存入数组C
        for(int i=1;i<C.length;i++){
            C[i] = C[i] + C[i-1];
        }
        //逆序输出确保稳定-相同元素相对顺序不变
        for(int i=A.length-1;i>=0;i--){

            B[C[A[i]]-1] = A[i];
            C[A[i]] = C[A[i]]-1;
        }
        return B;
    }

总结