C++面试基础知识：排序算法 C++实现

上周实习面试，手撕代码快排没写出来，非常丢人，把面试官都给逗笑了。
基础不牢，地动山摇，基础的算法还是要牢记于心的。

插入排序

分为有序区和无序区，每次从无序区中选出一个，放到有序区域中。
实现：

void InsertionSort(vector<int> &nums, int left, int right){for(int i=left+1; i<=right; i++){int key = nums[i];int j = i-1;while(j >= left && nums[j] > key){nums[j+1] = nums[j];j--;}nums[j+1] = key;}
}

快速排序

选择一个基准元素，小于基准的放前面，大于基准的放后面，一边下来基准的位置就已经确定了，然后再对递归对两边区域进行快排。

#include <iostream>
#include <vector>
#include <chrono>void QuickSort(vector<int> &nums,int left, int right){if(left >= right) return;int pivot = nums[left];int i = left, j = right;while( i < j){while(i < j && nums[j] >= pivot) j--;while(i < j && nums[i] < pivot) i++;if(i < j){swap(nums[i], nums[j]);}}QuickSort(nums, left, i);QuickSort(nums, i+1, right);
}

快速排序的思想是分治法，每次将待排序区域划分为两部分，平均划分$O(logn)$次，平均时间复杂度是$O(nlogn)$，且前面的常数比较小，大部分情况相比于时间复杂度恒等于$O(nlogn)$的归并排序更快。
最坏情况时间复杂度是$O(n^2)$，当每次选取的pivot恰好是最大值或最小值时，分完后两侧一边是0个，一边是n-1个，这种情况快排退化成冒泡排序。

优化

为了避免出现最差情况，可以从待排序区域中取多个数，从这其中取中间数。

void QuickSortV1(vector<int> &nums, int left, int right){if(left >= right) return;if(nums[right] < nums[left]){swap(nums[left], nums[right]);}if(nums[(left+right)/2] < nums[right]){swap(nums[right], nums[(left+right)/2]);}if(nums[left] < nums[(left+right)/2]){swap(nums[left], nums[(left+right)/2]);}int pivot = nums[left];int i = left, j = right;while(i < j){while(i < j && nums[j] >= pivot) j--;while(i < j && nums[i] < pivot) i++;if(i < j){swap(nums[i], nums[j]);}}QuickSortV1(nums, left, i);QuickSortV1(nums, i+1, right);
}

• 对于待排序区间小于10的时候，选择使用插入排序，这样可以避免由于快速排序的递归成本，插入排序反而比快速排序快。

void InsertionSort(vector<int> &nums, int left, int right){for(int i=left+1; i<=right; i++){int key = nums[i];int j = i-1;while(j >= left && nums[j] > key){nums[j+1] = nums[j];j--;}nums[j+1] = key;}
}void QuickSortV2(vector<int> &nums, int left, int right){if(right - left < 10){InsertionSort(nums, left, right);return;}if(nums[right] < nums[left]){swap(nums[left], nums[right]);}if(nums[(left+right)/2] < nums[right]){swap(nums[right], nums[(left+right)/2]);}if(nums[left] < nums[(left+right)/2]){swap(nums[left], nums[(left+right)/2]);}int pivot = nums[left];int i = left, j = right;while(i < j){while(i < j && nums[j] >= pivot) j--;while(i < j && nums[i] < pivot) i++;if(i < j){swap(nums[i], nums[j]);}}QuickSortV2(nums, left, i);QuickSortV2(nums, i+1, right);
}

• 如果待排序的数组中存在较多的重复数字，还可以确定好pivot的位置后，遍历一遍将所有与pivot相同的数字放到一起，然后再进入递归，这样在具有较多重复时可以很好的提速。

void QuickSortV3(vector<int> &nums, int left, int right){if(right - left < 10){InsertionSort(nums, left, right);return;}if(nums[right] < nums[left]){swap(nums[left], nums[right]);}if(nums[(left+right)/2] < nums[right]){swap(nums[right], nums[(left+right)/2]);}if(nums[left] < nums[(left+right)/2]){swap(nums[left], nums[(left+right)/2]);}int pivot = nums[left];int i = left, j = right;int equal_right = 0;while(i < j){while(i < j && nums[i] < pivot) i++;while(i < j && nums[j] >= pivot){if(nums[j] == pivot){swap(nums[j], nums[right-equal_right]);equal_right++;}j--;}if(i < j){swap(nums[i], nums[j]);}}for(int k=0; k<equal_right; k++){swap(nums[i+k], nums[right-k]);}QuickSortV3(nums, left, i-1);QuickSortV3(nums, i+equal_right, right);
}

对比：

void randInit(vector<int> &nums){for(int i=0; i<nums.size(); i++){nums[i] = rand()%10000;}
}int main(){vector<int> nums(10000);randInit(nums);auto start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSort(nums, 0, nums.size()-1);}auto end = chrono::steady_clock::now();auto diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSortV1(nums, 0, nums.size()-1);}end = chrono::steady_clock::now();diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSortV2(nums, 0, nums.size()-1);}end = chrono::steady_clock::now();diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSortV3(nums, 0, nums.size()-1);}end = chrono::steady_clock::now();diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;return 0;
}

在最差情况，每次都是选取到的最小值作为pivot，二者速度差了上百倍。

归并排序

也是分治思想，将待排序区域分为多个区域单独排序，再进行合并。不止可以分为两个区域，还可以分为多个区域，称为多路归并。
归并排序实现：

#include <iostream>
#include <vector>using namespace std;void merge_sort(vector<int> &num1, int left, int right){if(left >= right) return;int mid = left + (right - left) / 2;merge_sort(num1, left, mid);merge_sort(num1, mid + 1, right);int i = left, j = mid + 1, k = 0;vector<int> temp(right - left+1);while(i <= mid && j <= right){if(num1[i] <num1[j]){temp[k++] = num1[i++];}else{temp[k++] = num1[j++];}}while(i <= mid){temp[k++] = num1[i++];}while(j <= right){temp[k++] = num1[j++];}for(int i = 0; i < right - left+1; i++){num1[left + i] = temp[i];}
}int main(){vector<int> num1 = {3, 2, 1, 5, 4};vector<int> result;merge_sort(num1, 0, num1.size() - 1);for(auto i : num1){cout << i << " ";}cout << endl;return 0;
}

优化

• 可以使用多线程进行优化，每个线程负责一个待排序区域
• 通过改为非递归等方法，可以只需要一个temp就可以了，减小内存占用

堆排序

时间复杂度$O(nlogn)$，空间复杂度$O(1)$，不稳定算法。
维持一个大顶堆/小顶堆。一开始先进行建堆，建好堆后将堆的根和最后一个叶子节点进行交换，这时一个最大值的位置就已经固定了，接下来接着调整堆，调整好后再重复以上操作。

堆就是一棵完全二叉树，每一次都是满的，最后一层可以不是满的但是必须是从左往右紧密排列的：

堆分为大顶堆和小顶堆，大顶堆即父节点大于左右子节点，小顶堆即父节点小于左右子节点。
堆的存储方式最适合用数组存储，从左向右层序遍历的结果存在数组中。第i个数的父节点为$\lfloor \frac{i}{2}\rfloor$，
不过需要注意从0开始存储的和从1开始存储的情况，计算父节点方式不一样，从0开始存储的情况，计算方式为$\lfloor \frac{i}{2}\rfloor -1$
建堆的方式为从最后一个叶子节点开始，依次检查是不是大顶堆/小顶堆，如果是，接着向右排查，如果不是将该节点与子节点中较大的进行交换并判断交换后该节点是否为堆，如果不是，接着交换，直到该节点符合堆的要求为止。

实现：

#include <iostream>
#include <vector>using namespace std;void CreateHeap(vector<int> &nums, int i, int n){int left = 2*i+1;int right = 2*i+2;int max = i;if(left < n && nums[left] > nums[max]){max = left;}if(right < n && nums[right] > nums[max]){max = right;}if(max != i){swap(nums[i], nums[max]);CreateHeap(nums, max, n);}
}void HeapSort(vector<int> &nums){int n = nums.size();for(int i=n/2-1; i>=0; i--){CreateHeap(nums, i, n);}for(int i=n-1; i>=0; i--){swap(nums[0], nums[i]);CreateHeap(nums, 0, i);}
}int main()
{vector<int> nums = {3, 2, 1, 5, 4};HeapSort(nums);for(auto i : nums){cout << i << " ";}cout << endl;return 0;
}

扩展问题

• 复杂度越小，算法越好吗？
  并不一定，第一点，算法复杂度衡量的是操作次数的数量级，如果要完全评价一个算法复杂度，还应该考虑每次操作的时间，所以同等复杂度等级的代码，速度可能不一样快。第二点，对于问题规模较小时，复杂度大的算法不一定比复杂度小的算法慢，例如在问题规模小于10时，插入排序是比快速排序要快的。

• C++ 的STL库中的sort是怎么实现的？
  STL中的sort实现是内省排序，内省排序是快速排序和堆排序的结合，当递归深度大于$logn$时，会切换为堆排序。

• 什么是完全二叉树，什么是有序二叉树？
  完全二叉树就是类似于堆这种，简而言之就是从左向右层序遍历不存在缺口的二叉树。如果每一层都是满的，那就是满二叉树，所以完全二叉树也可以定义为顺序存储时，每个节点的位置都和满二叉树中节点的存储位置相同的树。
  有序二叉树指的是父子节点关系存在顺序管理，例如如果二叉树中父子节点满足：右子节点> 父节点> 左子节点，那这个树就是二叉查找树，可以用于快速查找数组中是否存在某个元素，查找时间复杂度为$O(logn)$，如果这个树是用链表存储的，那么插入复杂度也是$O(logn)$