关于几个基本排序的优化

红太狼 2021-11-24 02:06 233阅读 0赞

### 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个数测试，结果如下：

![20190727152356965.png][]

### 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个随机数测试：

![20190727153937978.png][]

此外，我们可以像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个近乎排序的数组，快速排序和归并排序做个比较：

![20190727163231387.png][]

我的烂电脑直接Segmentation FaulO(∩\_∩)O，换50000个元素：

![20190727163340399.png][]

可以看到，和归并排序的差距很大。主要就是我们每次都选择右边为基准点，改进的方法就是随机选择基准点。其实就是在选择基准前，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;
    }

然后再测试一次：

![20190727164126589.png][]

改进后比前面的好了很多，但是仍然比归并排序要慢，这是因为快速排序不像归并排序每次都很规律的二分，快速排序的递归深度理论上应该超过log(N)的，而归并排序就是log(N)。此外，当数据重复数据比较多，快速排序的效果也不尽如意，下面同样生成50000个数据，但这些数据都0-10之间的，运行代码结果：

![20190727164905644.png][]

可以看到，和归并排序又差距很大。这个问题在于如果存在大量重复的元素，patition可能又会分得很不平衡，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70][]

这样的情况下，递归树的深度又会比归并的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;
    }

然后再来测试一下：

![20190727210152878.png][]

这回比前面的快多了，这是快速排序的双路优化，其实快速排序还有更好的三路排序，其实就是在双路的基础上加了一个==p的就是第三路。如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 1][]

三路快速排序的代码如下：

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);
    }

同样生成的数据实验结果如下：

![20190727213719891.png][]

可见，三路快速排序在多数重复的情况有很好的优势，在数据完全随机的情况下，实验结果如下：

![20190727214352301.png][]

可见，在数据随机的情况下，三路快速排序和其他排序也不会相差很大，这也是为什么系统级的排序使用的就是三路快速排序。这就是所总结的关于排序的一些优化，这些在面试够用了。关于面试，主要就是考插入排序（shell排序），归并排序，快速排序（特别是双路、三路快速排序），以及堆排序，这五个排序算法一定要非常了解。

### 4、一些常用排序思想来解决的面试题目 ###

1、剑指offer第35题（归并排序思想）

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 2][]

题解参考我前面的这篇[https://blog.csdn.net/weixin\_42363997/article/details/95171898][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);
    }

[20190727152356965.png]: /images/20211122/247655e989114139984e862cec433034.png
[20190727153937978.png]: /images/20211122/35d0075ff0674f659fa5e0ff6ea63f0c.png
[20190727163231387.png]: /images/20211122/a6fb4011635348ce901d4591f3407d37.png
[20190727163340399.png]: /images/20211122/ab3f0be3f2394459b70df06e0bdb94c3.png
[20190727164126589.png]: /images/20211122/01cfdacf62704b74b3c87091f5a4c51a.png
[20190727164905644.png]: /images/20211122/e4baea1223d543bfa5dd419f0fe04957.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70]: /images/20211122/fc86e94671b44106898add5fdfecee15.png
[20190727210152878.png]: /images/20211122/e5031103696448319fdfd6d216993147.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 1]: /images/20211122/fce6e4301c0a48cdbb1012f92871bb3e.png
[20190727213719891.png]: /images/20211122/884ce88a72c8470d8390c5f18685c6ff.png
[20190727214352301.png]: /images/20211122/a4faf1ae5e7f4722a7ea0711dc7146d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM2Mzk5Nw_size_16_color_FFFFFF_t_70 2]: /images/20211122/b88bef97aaa7425d89d41215e5ec46b0.png
[https_blog.csdn.net_weixin_42363997_article_details_95171898]: https://blog.csdn.net/weixin_42363997/article/details/95171898