数组排序算法整理（不定期更新）

数组排序算法可以从代码形式上分为五大类：交换排序、选择排序、插入排序、归并排序、和基数排序，其中每一类又可以分为一些不同的小类（这就要靠我们自己总结）；而从物理存储上，数组排序说到底是对CPU的合理调度——只分为内部排序、外部排序两类——其中不借助磁盘IO，所有的操作都在内存中完成的叫内部排序，而对于那些不便于一次性读入的数据进行排序，就要用到外部排序的技巧；通常不做说明默认就是内部排序

---

目录

• 交换排序（Swap Sort）
• 选择排序（Selection Sort）
• 插入排序（Insertion Sort）
• 归并排序（Merge Sort）

---

在正式开始前，先看图有一个整体的印象

---

交换排序（Swap Sort）

说起交换排序，条件反射的会立即想到swap函数——交换排序需要swap，并且总是发生在两两一组之间；交换排序大致分为冒泡和快排

冒泡排序（Bubble Sort）

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，所以叫『冒泡』

它重复地走访过要排序的数列一次比较两个元素，从开始第一对到结尾的最后一对（一共n-1趟比较，每趟比较又分为若干比较），如果顺序错误就把他们交换过来；在这一点，每趟比较后靠最后的元素是最大的数——所以每次都可以减少一些元素不用参与比较

相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法

冒泡排序的优点是简单（也是我接触的第一个排序算法），缺点是要进行大量的比较和交换

冒泡排序的时间复杂度是O（N^2），在最好情况下，可以达到O（N-1）

如果非要细究的话，冒泡排序也有两种写法（两个名字是我瞎编的）

[cpp]
/*函数功能：实现冒泡排序（写法一，冒泡法）
 *请参说明：a[]：待排序数组，n：数组中的元素个数
 */
void bubblesort(int a[], int n)
{
    int i, j, tmp;
    for(i=0; i<n-1; i++)
    {
        for(j=0; j<n-i-1; j++)
        {
            if(a[j] > a[j+1])
            {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
}

[cpp]
/*函数功能：实现冒泡排序（写法二，也叫沉底法）
 *请参说明：a[]：待排序数组，n：数组中的元素个数
 */
 void bubblesort(int a[], int n)
 {
     int i, j, tmp;
     for(i=0; i<n-1; i++)
     {
         for(j=n-2; i>=0; j--)
         {
             if(a[j] > a[j+1])
             {
                 tmp = a[j];
                 a[j] = a[j+1];
                 a[j+1] = tmp;
             }
          }

    }
}

快速排序（Quick Sort）

快排是已知最快的数组排序算法（务必熟练掌握）

由C. A. R. Hoare在1962年提出，不妨看成是冒泡排序的改进算法

它的思路是，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列——眼尖的同学肯定看出来快排可以使用递归实现

[cpp]
/*函数功能：实现快速排序
 *请参说明：a[]：待排序数组，low：组的左边界，high：组的右边界
void quicksort(int a[], int low, int high)
{
    if(low >= high) return;//如果左边索引大于或等于右边索引，就代表已经完成一个分组
    int i = low, j = high;
    int key = a[low];//去小端作为每次判断的关键值，即中间数

    while(i < j)//在当前[i..j]组内找一遍
    {
        while(key <= a[j])//寻找结束的条件是，1）找到一个大于key的值，2）没有找到符合1条件的，并且i和j的大小没有交换
        {
            j--;//不断向前寻找
        }
        a[i] = a[j];//找到一个这样的数就把它赋值给前面被拿走的i的值
        while(key >= a[i])//i在当前组内向前寻找，不过key的大小关系通知循环和上面的完全相反，因为排序思想是把数往两边扔，所以左右两边的数的大小与key的关系相反
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;//在当前组内找完一遍后就以把中间数key回归
    quicksort(a, low, i-1);//用同样的方式对分出来的左边的小组进行上述操作
    quicksort(a, i+1, high);//用同样的方式对分出来的右边的小组进行上述操作
    /*直到每一组的i==j为止*/
}

---

选择排序（Selection Sort）

有三种不同的选择排序：分别是：直接选择排序（Straight Select Sort）、树状选择排序（锦标赛排序，Tournament Sort）、堆排序（Heap Sort）

直接选择排序（Straight Select Sort）

也叫简单选择排序（Simple Select Sort），就是不管是写起来还是理解起来都十分简单的排序算法

和Bubble Sort一样，它也要n-1趟遍历；第i一趟遍历从A[i-1]～A[n-1]中选出最小的元素，并把最小的元素放到排头，这样在n-1趟后数组就有序了

直接选择排序的时间复杂度是O（N^2）

由于在直接选择排序中存在着不相邻元素之间的互换，因此直接选择排序是一种不稳定的排序方法

[cpp]
/*函数功能：实现直接选择排序
 *请参说明：a[]:待排序数组，n：数组中的元素个数
 */
void simpleselectsort(int a[], int n)
{
    int i,j,min,tmp;
    for(i=0; i<n-1; i++)
    {
        min = a[i];  //设置哨兵
        for(j=i+1; j<n; j++)
        {
            if(a[j] < min)
            {
                tmp = a[j];
                a[j] = min;
                min = tmp;
            }
        }
    }
}

树状选择排序（Tree Select Sort）

树状选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法

首先对n个记录的关键字进行两两比较，然后在n/2（向上取整）个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止

树形选择排序构成的树是满二叉树

其中，树叶结点包括所有的参赛者，两两比较，数值小的上升成为父亲结点，每一趟排序的产生一个新的树根

在下一趟遍历开始前，把这一趟的优胜者之兄弟结点上升到父亲结点的位置

树状选择排序的时间复杂度是O（N*logN）

树状选择排序的缺点是辅助存储空间较多，并且需要和最大值进行多余的比较（于是堆排序应运而生，详见后文）

[cpp]
/*函数功能：实现树状选择排序
 *请参说明：a[]：待排序数组，n：数组中的元素个数
 */
void treeselectsort(int a[], int n)
{
    /*相比树状排序我更推荐堆排序所以请先忽略树状排序，这里先占着以后补上
     *总体的思路很简单，就是自底向上构造一棵满二叉树——不过涉及到的细节还是容易出错
     */
}

堆排序（Heap Sort）

为了弥补树状选择排序的不足，堆排序应运而生（同样属于选择排序）

1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法

堆分为大根堆和小根堆，是完全二叉树

大根堆要求每个结点的值都不大于其父亲结点的值，小根堆要求每个结点的值都不小于其父亲结点的值（也就是说，大根堆=>树根最大值，小根堆=>树根最小值）

堆排序的时间复杂度是O（N*logN）

易知，大根堆=>升序，小根堆=>降序

下面以大根堆讲解升序排序

[cpp]
void heapsort(int a[], int n)
{
    int i,j,root_index;
    int length = sizeof(a)/sizeof(int);
    for(i=length; i>=0; i--)
    {
        //从最后一个元素开始想堆的上层查找
        for(j=i-1; j>0; j--)
        {
            if(j%2==0)//右子结点的根结点
                root_index = (j-2)/2;
            else//左子结点的根结点
                root_index = (j-1)/2;

            if(a[root_index] < a[j])//如果根结点比当前结点小，不满足堆的性质，交换二者
            swap(&a[root_index], &a[j]);
        }
        swap(&a[j], &a[i-1]);//将最大值向后移动
    }   
}       

---

插入排序（Insertion Sort）

插入排序分为直接插入排序、二分插入排序和希尔排序，如果不做说明默认就是直接插入排序

直接插入排序（Straight Insert Sort）

看到名字就想到了『直接选择排序』，二者的共同点是它们的复杂度都是O（N^2），但是直接插入排序相比直接选择排序更稳定（所谓稳定，是指原来相等的两个数不会交换位置）

直接插入排序在最好情况下（所有元素都基本有序），时间复杂度为O（N）

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止

第一趟：对下标1的元素排序，保证[0..1]上的元素有序
第二趟：对下标2的元素排序，保证[0..2]上的元素有序
……
第n-1趟：对下标n-1的元素排序，保证[0..n-1]的元素有序

[cpp]
/*函数功能：实现直接选择排序（方案一）
 *请参说明：a[]：待排序数组，n：数组中的元素个数
 */
void simpleinsertsort(int a[], int n)
{
    int i,end,tmp;
    for(i=1; i<n; i++)//因为第一个元素默认是有序的，所以不需要排序
    {
        tmp = a[i];
        end = i-1;
        while(end>=0 && arr[end] >tmp)
        {
            arr[end+1] = arr[end];
            --end;
        }
        arr[end+1] = tmp;
    }
}

[cpp]
/*函数说明：直接插入排序的优化版
 *请参说明：a[]：待排序数组，n：数组中的元素个数
 */
 void simpleinsertsort(int a[], int n)
 {
     int i,end, tmp;
     for(i=1; i<n; i++)
     {
         for(end=i-1; end>=0; end--)
         {
             if(a[end] > a[end+1])//end+1就是i，发现前一个数比当前的数还大
             swap(&arr[end], &arr[end+1]);//交换之
             else//否则说明i之前的序列都已经有序了
                 break;
        }
    }
}

二分插入排序（Binary Insert Sort）

也叫折半插入排序，基于直接插入，把寻找a[i]位置的方法改为折半比较

所谓折半，就是指插入a[i]时，取a[（low+high）/2]的值和a[i]比较，而不是（a[i-1]和a[i]进行比较）

二分插入排序算法在最好的情况下的时间复杂度为O（N*logN），最坏情况和知己插入一样，是O（N^2）

[cpp]
/*函数功能：实现二分插入排序
 *请参说明：a[]：待排序数组，n：数组中元素的个数
 */
void binaryinsertsort(int a[], int n)
{
    int i,j,low,high,mid,tmp;
    for(i = 1; i<n; i++)
    {
        low = 0, high = i-1;
        mid = -1;
        tmp = a[i];
        while(low <= high)
        {
            mid = low + (low+high)/2;
            if(a[mid] > tmp)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        for(j=i-1; j>=low; j--)
        {
            a[j+1] = a[j];
        }
        a[low] = tmp;
    }
}

希尔排序（Shell Sort）

希尔排序也叫『缩小增量排序』，由DL．Shell于1959年提出而得名

希尔排序可以看成是分组的直接插入排序

希尔排序的时间复杂度为O（N^1.3）

其基本思想是：先将整个待排序数组分割成若干个子序列（由相隔某个增量的元素组成）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序，因为直接插入排序在元素基本有序的情况下效率时很高的，所以希尔排序在时间上较之前的插入排序有较大提升

[cpp]
/*函数功能：希尔插入，封装待希尔排序中
 *请参说明：a[]：待排序数组，n：数组中的元素个数，dk：当前增量
 */
void shellinsert(int a[], int n, int dk)
{
    int i,j,tmp;
    for(i=dk; i<n; i++)//分别向每组的有序区域插入
    {
        tmp = a[i];
        for(j=i-dk; j>i%dk && a[j] > tmp; j-=dk)
        {
            a[j+dk] = a[j];
        }
        if(j != i-dk)
        {
            a[j+dk] = tmp;
        }
    }
}

/*函数功能：计算Hibbard增量
 *请参说明：t、k：就是一个值
 */
int dkHibber(int t, int k)
{
    return (int)(pow(2, t-k+1)-1);
}

/*函数功能：实现希尔排序（插入排序的重组改进版本）
 *请参说明：a[]：待排序数组，n：数组中元素的个数，t：就是t
 */
void shellsort(int a[], int n, int t)
{
    shellinsert(a, n, dk);
    int i;
    for(i=1; i<t; i++)
    {
        shellsort(a, n, dkHibber(t, i));
    }
}

---

归并排序（Merge Sort）

发明者是大名鼎鼎的John von Neumann，现代计算机之父

从名字可以看出来这是一种先局部后整体的排序方式（类似的如quicksort，体现了分而治之，Divide and Conquer的算法思想），即『先划分，后合并』；可想而知，这要用到递归实现

归并排序是相当稳定的，不想别的算法存在最好和最坏情况，它的时间复杂度稳定为O（N*logN）

它的核心操作就是『归并』，即Merge操作

归并 = 递归 + 合并

归并排序不是原地排序，在排序过程中要申请新的内存空间用来存放临时数组元素，相对应的我们说归并排序（包括后面讲的基数排序）都是复制排序

[cpp]
/*函数功能：合并a[first..mid]和a[mid..last]，合并结果存放到tmp中去
 *请参说明：a[]：待排序数组，first：合并区间的首个下标，last：合并区间的最后一个下标，tmp[]：用来存放合并结果的临时数组
 */
 void mergearray(int a[], int first, int last, int last, int emp[])
 {
    int i = first, j = mid + 1;
    int m = mid, n = last;
    in k = 0;

    while(i <= m && j <= n)
    {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }

    while(i <= m)
        tmp[K++] = a[i++];
    while(j <= n)
        tmp[k++] = a[j++];
    for(i=0; i<k; i++)
        a[first+i] = tmp[i];
}

/*函数功能：实现归并排序
 *请参说明：a[]：待排序数组，first：待排序数组的左边界，待排序数组的右边界，tmp：临时数组
 */
 void mergesort(int a[], int first, int last, int tmp[])
 {
     if(first < last)
     {
         int mid = (first+last)/2;
         mergesort(a, first, mid);//左边有序
         mergesort(a, mid+1, last);//右边有序
         mergearray(a, first, mid, last);//将两个有序序列合并
     }
}