1、插入排序
来看看前面实现的插入排序的代码
void insertSort(int arr[], int len){
int t_i = 0;// 找到第一个不是升序的索引 如 3 6 7 4 找到4的索引
while (t_i < len && arr[t_i]<arr[t_i + 1])t_i++;
t_i ++;
if(t_i >= len) return;
for (int i = t_i; i < len; i++)
{
int t = i;
while (t > 0 && arr[t - 1] > arr[t])
{
swap(arr[t], arr[t - 1]);
t--;
}
}
}
可以看到每次找到前面的数大于当前数时，总会调用swap函数，而swap函数相当于三个赋值操作，改进的办法就是每次只调用一次赋值操作，用一个temp记录当前的值，然后如果当前数的前一个值比当前数大，那么当前的数直接赋值后面的数。改进代码如下：
// 插入排序
void insertSort(int arr[], int len){
int t_i = 0;// 找到第一个不是升序的索引 如 3 6 7 4 找到4的索引
while (t_i < len && arr[t_i]<arr[t_i + 1])t_i++;
t_i ++;
if(t_i >= len) return;
for (int i = t_i; i < len; i++)
{
int t = i, temp = arr[i];
while (t > 0 && arr[t - 1] > temp)arr[t] = arr[t - 1], t--;
arr[t] = temp;
}
} 别小看这个只是小小的优化，测试就可以看出明显差距，对随机生成的100000个数测试，结果如下：
2、归并排序
前面写的归并排序是这样的：
// 归并排序
// 合并两个有序数组
void merge(int arr[], int temp[], int l, int m, int r){
int i = l, j = m + 1, k = l;
while (i <= m && j <= r)
{
if(arr[i] < arr[j])
temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= m)
temp[k++] = arr[i++];
while (j <= r)
temp[k++] = arr[j++];
for (i = l; i <= r; i++)
arr[i] = temp[i];
}
void mergeSort(int arr[], int temp[], int l, int r){
if(l >= r)return;
int mid = l + (r - l) / 2;
mergeSort(arr, temp, l, mid);
mergeSort(arr, temp, mid + 1, r);
merge(arr, temp, l, mid, r);
}
可以看到，在递归后每次都merge操作，其实当前面部分的数都小于后半部分的数时，可以不必merge操作。
template<typename T>
void mergeSort2(T arr[], T temp[], int l, int r){
if(l >= r)return;
int mid = l + (r - l) / 2;
mergeSort2(arr, temp, l, mid);
mergeSort2(arr, temp, mid + 1, r);
if(arr[mid] > arr[mid + 1])
merge(arr, temp, l, mid, r);
} 同样来测试这个操作后的性能变化，对500000个随机数测试：
此外，我们可以像shell排序那样，当r - l < 某个数时调用插入排序，因为插入排序对有序列数组可以近乎达到O(n)级别，这也是一个优化的思路。以递归调用的方法多是自顶向下的思路，但归并排序也可以以自底向上的方法来做，也就是用迭代的方法，参考代码如下：
template<typename T>
void mergeSortBottomUp(T arr[], int n){
// 每次增大一倍步幅去自底向上归并
for(int size = 1; size <= n; size += size){
//关键点1： i + size < n是为了防止下面__merge的时候越界(因为i + size可能大于n了)
for( int i = 0; i + size < n; i += size + size){
// 对arr[i...i+size-1]和arr[i+size...i+size+size-1] 进行归并
// 关键点2：虽然前面保证了1 + size < n，但是1 + size + size 也可能超过最大下标n-1,
// 此处取它和n-1的更小值来保证merge的时候确实是两部分
int left = i, mid = i + size - 1, right = min(i + size + size -1, n - 1);
T temp[right - left + 1];
merge(arr, temp, left, mid, right);
}
}
} 3、快速排序
之前写的快速排序是这样的：
// 快速排序
template<typename T>
int partition(T arr[], int l, int r){
// 以右边为基准, index记录基准的索引，最后和l交换
T p = arr[r];
int index = r;
while (l < r)
{
while (l < r && arr[l] <= p)l++;
while (l < r && arr[r] >= p)r--;
swap(arr[l], arr[r]);
}
swap(arr[index], arr[l]);
return l;
}
template<typename T>
void quickSort(T arr[], int l, int r){
if(l >= r)return;
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}
template<typename T>
void quickSort(T arr[], int len){
quickSort(arr, 0, len - 1);
} 可以看出，在取基准时，每次都取右边，当待排序数组近乎有序时，递归不再是二叉树，而是链表，复杂度退化到O(n^2).。我们可以测试一下10W个近乎排序的数组，快速排序和归并排序做个比较：
我的烂电脑直接Segmentation FaulO(∩_∩)O，换50000个元素：
可以看到，和归并排序的差距很大。主要就是我们每次都选择右边为基准点，改进的方法就是随机选择基准点。其实就是在选择基准前，partition方法中随机选取一个点，和右边点交换。
template<typename T>
int partition(T arr[], int l, int r){
// 在选择基准前，先随机选择一个点，与基准交换
srand(time(NULL));
int i = rand() % (r - l + 1) + l;
swap(arr[i], arr[r]);
// 以右边为基准, index记录基准的索引，最后和l交换
T p = arr[r];
int index = r;
while (l < r)
{
while (l < r && arr[l] <= p)l++;
while (l < r && arr[r] >= p)r--;
swap(arr[l], arr[r]);
}
swap(arr[index], arr[l]);
return l;
} 然后再测试一次：
改进后比前面的好了很多，但是仍然比归并排序要慢，这是因为快速排序不像归并排序每次都很规律的二分，快速排序的递归深度理论上应该超过log(N)的，而归并排序就是log(N)。此外，当数据重复数据比较多，快速排序的效果也不尽如意，下面同样生成50000个数据，但这些数据都0-10之间的，运行代码结果：
可以看到，和归并排序又差距很大。这个问题在于如果存在大量重复的元素，patition可能又会分得很不平衡，如下图：
这样的情况下，递归树的深度又会比归并的log(N)要大，解决这个问题，就是使用双指针，也就是常说的双路快速排序。我们使用两个指针，一个指向l一个指向r-1，如果直到两个指针相遇后停止循环。算法如下：
（1）在随机选择并与右边的交换后，取最右边的数p暂存。
（2）指针i指向l，指针j指向r-1，当r在边界内并且arr[i]<p，i向右，j同理。
（3）i、j找完时如果i>j结束循环，否则交换i、j索引对应的数。
具体改进代码如下：
template<typename T>
int partition2(T arr[], int l, int r){
// 在选择基准前，先随机选择一个点，与基准交换
srand(time(NULL));
swap(arr[rand() % (r - l + 1) + l], arr[r]);
// 以右边为基准, index记录基准的索引，最后和l交换
T p = arr[r];
int i = l, j = r - 1;
while (true)
{
while (i <= r - 1 && arr[i] < p)i++;
while (j >= l && arr[j] > p)j--;
if(i > j) break;
swap(arr[i++], arr[j--]);
}
swap(arr[i], arr[r]);
return i;
} 然后再来测试一下：
这回比前面的快多了，这是快速排序的双路优化，其实快速排序还有更好的三路排序，其实就是在双路的基础上加了一个==p的就是第三路。如下所示：
三路快速排序的代码如下：
template<typename T>
void quickSort3Ways(T arr[], int l, int r){
if(l >= r ) return;
srand(time(NULL));
swap(arr[rand() % (r - l + 1) + l], arr[l]);
T p = arr[l];
int lt = l, gt = r + 1, i = l + 1;
while(i < gt){
if(arr[i] < p)
swap(arr[i++], arr[++lt]);
else if(arr[i] > p)
swap(arr[i], arr[--gt]);
else i++;// arr[i] == p
}
swap(arr[l], arr[lt]);
quickSort3Ways(arr, l, lt - 1);
quickSort3Ways(arr, gt, r);
} 同样生成的数据实验结果如下：
可见，三路快速排序在多数重复的情况有很好的优势，在数据完全随机的情况下，实验结果如下：
可见，在数据随机的情况下，三路快速排序和其他排序也不会相差很大，这也是为什么系统级的排序使用的就是三路快速排序。这就是所总结的关于排序的一些优化，这些在面试够用了。关于面试，主要就是考插入排序（shell排序），归并排序，快速排序（特别是双路、三路快速排序），以及堆排序，这五个排序算法一定要非常了解。
4、一些常用排序思想来解决的面试题目
1、剑指offer第35题（归并排序思想）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
题解参考我前面的这篇https://blog.csdn.net/weixin_42363997/article/details/95171898第35题。
2、数组中第K小的数（考快速排序）
给一个数组，要求返回第K小数的索引，空间复杂度要求O(1)。
由于经过快速排序后，partition的位置不会再改变，我们只需递归k在的那一部分，就能找到arr[k]。代码如下：
template<typename T>
int quickSortGetN(T arr[], int l, int r, T k){
if(l >= r)return -1;
int p = partition(arr, l, r);
if(p == k) return p;
else if(p > k)
quickSortGetN(arr, l, p - 1, k);
else
quickSortGetN(arr, p + 1, r, k);
}
京公网安备 11010502036488号