【预判一手面试问题：排序】

【知识预告】

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 希尔排序
5. 快速排序（hoare法，挖坑法，前后指针法）

1 排序的概念

• 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
• 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
• 内部排序：数据元素全部放在内存中的排序。
• 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

2 冒泡排序（稳定）

  假设一个数组为int arr[] = { 9,8,7,6,5,4,3,2,1,10 };要求把它按从小到大的顺序排序。初学者最容易想到的方式，就是“暴力比较法”：每次遍历数组，找出当前最小的，放到前面；然后再遍历剩下的部分，继续找最小的……如此反复。这其实是一种穷举法，它完全没有利用任何优化策略，纯粹依靠蛮力解决问题。
稍微了解一点排序知识的同学，可能会直接说出“冒泡排序”。冒泡排序可以说是最基础、最经典、也是最常被批评的排序算法之一，虽然效率不高，但它在教学和理解排序思想上有着不可替代的作用。下面是它的实现：

void Swap(int& x, int& y)
{int temp;temp = x;x = y;y = temp;
}void BubbleSort(int* a, int n)
{// i表示趟数：10个数字需要9趟// j表示每一趟需要比较的对数，第一趟要比较9对，第二趟要比较8对,依次类推int i = 0;     int j = 0;     for (i = 0; i < n; i++){for (j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(a[j], a[j + 1]);}}}
}

  冒泡排序的核心思想是：相邻元素两两比较，把大的值不断“冒泡”到后面。虽然也属于 $O(n^2)$ 级别的排序，但相较于“穷举找最小”的暴力方法，它在每一趟中会进行相邻元素的交换，操作更具局部性，代码逻辑也更清晰。

3 选择排序（不稳定）

  如果你在面试时侃侃而谈的是冒泡排序，面试官大概率就会开始和你聊起学校哪个食堂最好吃，学校老师好不好等等（因为面试官可能已经认定你没过线了，只是在走流程混 KPI 而已。）
因此，再介绍一个选择排序（比冒泡排序强10倍，后面有数据比较）
1. 遍历一遍数组，把最小的放左边，最大的放右边
2. 第二次遍历比第一次少两个，每次遍历就少两个

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin; i <= end; i++)  // 开始遍历数组{if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Swap(a[begin], a[min]);Swap(a[end], a[max]);begin++;end--;}
}

上面的代码有个大坑：

1. 比如数组{ 5, 3, 1, 4, 2 }：
2. 第一轮 begin = 0, end = 4，min = 2 (a[2] = 1)，max = 0 (a[0] = 5)。
3. Swap(a[0], a[2]) → { 1, 3, 5, 4, 2 }（此时 max 的值已经被换到 a[2] 了！）
4. Swap(a[4], a[0]) → 错误交换，因为 max 已经不是 a[0] 了。

所以上面代码有个细节要改：如果max是在begin的位置，第一轮Swap之后，要跟新max的位置到原来min的位置。

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin;int min = begin;for (int i = begin; i <= end; i++)  // 开始遍历数组{if (a[i] > a[max]){max = i;}if (a[i] < a[min]){min = i;}}Swap(a[begin], a[min]);if (max == begin)   // 修正max的位置，细节{max = min;}Swap(a[end], a[max]);begin++;end--;}
}

4 插入排序（稳定）

  选择排序虽然不用像冒泡那样频繁交换，但它的策略过于“死板”。每次都要从剩下的元素中找出最小的，哪怕数据已经有序了一大半，它也不管不顾地“全遍历”（还是太蠢了！！！）
我再介绍一个插入排序（比选择排序快6倍，后面有数据支撑）

void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int temp = a[i];while (end >= 0){if (a[end] > temp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = temp;}
}

  插入排序，能根据当前局势做出反应，数据越有序，它跑得越快，这和我们在打扑克牌时常用的策略是类似的。

5 希尔排序（不稳定）

  插入排序确实聪明了不少，数据越有序它跑得越快，最好的情况下（完全有序），时间复杂度甚至可以接近 $O(n)$，很讨喜。
但它也有硬伤：当数组长度非常大、数据分布完全混乱时，插入排序就像个“步兵”：一步一挪、前移后插，每走一步都得前前后后找位置，效率直接打回原形，退回 $O(n^2)$ 阶层。
所以，希尔排序来了，这是第一个跳出 $O(n^2)$ 阶层、初步追求效率的排序算法。它的最大特点是“分组预排序 + 插入优化”，尤其对大数据量和部分有序的数据表现优秀。

void ShellSort(int* a, int n)
{int i = 0;int gap = n;int end;// gap > 1 是预排序// gap = 1 就是插入排序while (gap > 1){gap = gap / 3 + 1;    // 加一很细节，保证最后一次一定是1，直接就算插入排序，一定有序for (int j = 0; j < gap; j++){for (i = j; i < n - gap; i += gap){end = i;int temp = a[end + gap];while (end >= 0){if (a[end] > temp){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = temp;}}}
}

6 快速排序（不稳定）

  主角登场，快速排序，它是大多数情况下最快的通用排序算法之一，平均时间复杂度 $O(n\log n)$，真正做到了又快又简单。其核心思想是分而治之，先把整个数组按一个基准值一分为二，小的放左边，大的放右边，再对左右两边递归处理，最终自然就有序了。
只要面试关问排序，必定有快速排序（很大概率现场手巧代码），快速排序分为三个版本：hoare，挖坑，前后指针法。

6.1 hoare法

// [left,right]
int PartSort1(int* a, int left, int right)
{int keyi = left;while (left < right){// 右边找小// a[right] >= a[keyi] 加等于号是防止死循环，防止有两个值和key相同// left < right 防止越界while (left < right && a[right] >= a[keyi]){right--;}// 左边找大while (left < right && a[left] <= a[keyi]){left++;}Swap(a[left], a[right]);}Swap(a[keyi], a[right]);   // left 和 right 相遇了return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort1(a, begin, end);// [begin, keyi-1]  keyi  [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

6.1 挖坑法

// [left,right]
int PartSort2(int* a, int left, int right)
{int key = a[left];int hole = left;while (left < right){// 右边找小，找到后去填左边的坑，右边形成新的坑while (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;// 左边找大while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return left;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort2(a, begin, end);// [begin, keyi-1]  keyi  [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

6.1 前后指针法

// 目的：cur找小   
// 如果：a[cur] < key   则：++prev  然后交换prev的位置和cur的位置int PartSort3(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){// 先判断prev能不能动，在让cur动if (a[cur] < a[keyi]){++prev;Swap(a[prev], a[cur]);}cur++;}Swap(a[prev], a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int keyi = PartSort3(a, begin, end);// [begin, keyi-1]  keyi  [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

7 测试效率

// 测试排序的性能对比
void TestOP()
{srand((unsigned int)time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];}int begin1 = clock();    // 单位是毫秒InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();BubbleSort(a3, N);int end3 = clock();int begin4 = clock();SelectSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end3 - begin3);printf("SelectSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);
}

输出结果：快速排序完胜！！！

InsertSort:598
ShellSort:9
BubbleSort:11822
SelectSort:3960
QuickSort:6
hello world

  还有其它的排序，堆排序，归并排序等等，这里就不说了，快速排序，应对面试官，我感觉足够了！！！