[C++知识库]面试官：我们写一道排序 —— 八大排序C++实现，详解

排序作为算法的基础，是很多面试官喜欢考察的重点之一，排序的种类繁多，但是有规可循，本文分析了常见的八大排序。

术语解释:
1、稳定排序： 如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2、非稳定排序： 如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3、原地排序： 原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序： 需要利用额外的数组来辅助排序。
5、时间复杂度： 一个算法执行所消耗的时间。
6、空间复杂度： 运行完一个算法所需的内存大小。

一、 基础的排序

1、选择排序

过程简单描述：
首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法我们称之为选择排序。

代码如下：

void selectSort(vector<int>& vec) {
    if(vec.size() < 2)  return ;

    int n = vec.size();
    for(int i=0; i<n-1; i++) {
        int min = i;
        for(int j=i+1; j<n; j++) {
            if(vec[j] < vec[min])
                min = j;
        }
        swap(vec[i], vec[min]);
    }
}

2、插入排序

过程简单描述：
1、从数组第2个元素开始抽取元素
2、把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。
3、继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。

void insertSort(vector<int>& vec) {
    if(vec.size() < 2)  return ;

    int n = vec.size();
    for(int i=1; i<n; i++) {
        int temp = vec[i];
        int k=i-1;
        while(k>=0 && vec[k]>temp) 
            k--;
        for(int j=i; j>k+1; j--)
            vec[j] = vec[j-1];
        vec[k+1] = temp;
    }
}

3、冒泡排序

1、把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置….
我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。
除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

void bubleSort(vector<int>& vec) {
    if(vec.size() < 2)  return ;

    int n = vec.size();
    for(int i=0; i<n-1; i++) {
        for(int j=0; j<n-i-1; j++) {
            if(vec[j] > vec[j+1])
                swap(vec[j], vec[j+1]);
        }
    }
}

优化一下的冒泡排序算法
假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了，我们无需再对剩余的元素重复比较下去了。

void bubleSort1(vector<int>& vec) {
    if(vec.size() < 2)  return ;

    int n = vec.size();
    bool flag = true;
    for(int i=0; i<n-1; i++) {
        for(int j=0; j<n-i-1; j++) {
            if(vec[j] > vec[j+1]) {
                swap(vec[j], vec[j+1]);
                flag = false;
            }   
        }
        if(flag)
            break;
    }
}

4、希尔排序：插入的变种

希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。
希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

void insert1(vector<int>& vec, int h, int i) {
    int temp = vec[i];
    int k;
    for(int k=i-h; k>0 && temp < vec[k]; k-=h) {
        vec[k+h] = vec[k];
    }
    vec[k+h] = temp;
}

void shellSort(vector<int>& vec) {
    if(vec.size() < 2)  return ;

    int n = vec.size();
    for(int h=n/2; h>0; h/=2) {
        for(int i=h; i<n; i++) {
            insert1(vec, h, i);
        }
    }
}

5、计数排序

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。
基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

void countSort(vector<int>& vec) {
    if(vec.size() < 2)  return ;
    
    int n = vec.size();
    int max = vec[0];
    // 寻找最大值
    for(int i=1; i<n; i++) {
        if(vec[i] >= max)
            max = vec[i];
    }
    // 创建大小为 max的临时数组
    vector<int> temp(max+1);
    // 统计元素 i出现的次数
    for(int i=0; i<n; i++) {
        temp[vec[i]]++;
    }
    int k=0;
    // 把临时数组统计好的数据汇总到原数组
    for(int i=0; i<=max; i++) {
        for(int j=temp[i]; j>0; j--) {
            vec[k++] = i;
        }
    }
}

二、常考需要递归和分治的排序

6、归并排序

将一个大的无序数组有序，我们可以把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。
通过递归的方式将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。
为方便理解我还准备了动图：

void merge(vector<int>& vec, int left, int mid, int right) {
    vector<int> temp(right-left+1);
    int i=left, j=mid+1, k=0;
    while(i<=mid && j<=right) {
        if(vec[i] <= vec[j]) {
            temp[k++] = vec[i++];
        } else {
            temp[k++] = vec[j++];
        }
    }
    while(i<=mid)   temp[k++] = vec[i++];
    while(j<=right) temp[k++] = vec[j++];

    for(i=left, k=0; i<=right;) 
        vec[i++] = temp[k++];
}

void mergeSort(vector<int>& vec, int left, int right) {
    if(left >= right)   return ;

    int mid = (left+right)/2;
    mergeSort(vec, left, mid);      // 注意区间的开闭
    mergeSort(vec, mid+1, right);

    merge(vec, left, mid, right);
}

7、快速排序

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

int partition(vector<int>& vec, int left, int right) {
    // 取最后一个元素为标杆
    int index = left;
    while(left < right) {
        if(vec[left] < vec[right]) {
            swap(vec[left], vec[index]);
            index ++;
        }
        left++;
    }
    swap(vec[index], vec[right]);   
    return index;
}

void quicksort(vector<int>& vec, int left, int right) {
    if(left > right)    return ;

    int patitionIndex = partition(vec, left, right);
    quicksort(vec, left, patitionIndex-1);
    quicksort(vec, patitionIndex+1, right);
}

8、堆排序

堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。
堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

void heapify(vector<int>& vec, int n, int i) {
    // 堆化
    int maxn = i, l = 2*i+1, r = 2*i+2;

    if(l<n && vec[l]>vec[maxn])
        maxn = l;
    if(r<n && vec[r]>vec[maxn])
        maxn = r;
    if(maxn != i) {
        swap(vec[maxn], vec[i]);
        heapify(vec, n, maxn);
    }
}

void heapSort(vector<int>& vec, int n) {
    // 堆化
    for(int i=n/2-1; i>=0; i--) 
        heapify(vec, n, i);
    // 堆排序，从后往前缩小区间, 从大到小排序
    for(int j=n-1; j>=0; j--) {
        swap(vec[0], vec[j]);
        heapify(vec, j, 0);
    }
}

三、时间复杂度和空间复杂度分析