NC140 #排序#

题意分析

一个面试经常会问的题目，考察基本的排序。给我们一个序列，需要我们将这个数进行从小到大排序。

思路分析

这种题目算是一个很经典的题目，这里介绍两种高效的排序方法。其思想都是利用递归进行实现的。

快速排序法

快速排序的思想就是我们先设定一个基准，然后将这个要排序的区间里面的数字比它小的扔到左边，比他大的扔到右边。然后进行递归的操作，从而达到了排序的目的。
分为以下三步
- 选择一个基准
- 以基准为中心，将序列划分为左右两个子序列，序列左边的都比这个数字小，序列右边的都比这个数字大
- 递归到序列长度为1或者序列为空就结束

alt

代码如下
- 递归的次数为log级别的，每个递归最多遍历长度为n的序列，但是在排列越有序的情况下时间复杂度会越高，在接近有序的情况会退化成暴力的排序方法，总的时间复杂度为 $O (n^{2})$
- 每次递归需要开辟长度为若干个变量，最多递归的次数为n，所以总的开辟的栈空间为 $O (n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    int partition(vector<int> &A,int left,int right){
        int tmp=A[left]; // 将最左边的数字暂时存入tmp
        while(left<right){
            while(left<right&&A[right]>tmp) right--; // 反复移动左边界
            A[left]=A[right];
            while(left<right&&A[left]<=tmp) left++; // 反复移动右边界
            A[right]=A[left];
        }
        A[left]=tmp; // 将tmp放到left和right相遇的地方
        return left;
    }
    void quickSort(vector<int> &A,int left,int right){
        if(left<right){
            int pos=partition(A, left, right);
            quickSort(A,left,pos-1); // 对左半部分的区间进行递归排序
            quickSort(A,pos+1,right); // 对右半部分的区间进行递归排序
        }
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quickSort(arr, 0, arr.size()-1);
        
        return arr;
    }
};

归并排序法

归并排序的思想就是我们将区间划分为很小的区间，先确保小区间有序，然后将两个小的区间合并成一个大的区间，从而实现大区间的有序。最后实现全部有序。
归并排序分为三步
- 将区间进行划分
- 对小区间进行排序
- 将小区间合并成大区间，由于小区间已经保证了有序，归并的方法是根据这个来进行遍历，实现O(n)的归并

alt

代码如下
- 递归的次数为 $l o g n$ ，每个归并的时间复杂度为 $O (n)$ ，总的时间复杂度为 $O (n l o g n)$
- 在每次进行归并的时候，我们开了一个数组暂时存储数据，数组最长为 $n$ ，递归的次数为 $l o g n$ 次，所以最坏的空间复杂度为 $O (n + l o g n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    // 合并函数
    void merge(vector<int> &A,int L1,int R1,int L2,int R2){
        vector<int> tmp;
        int i=L1,j=L2;
        // 我们将这个区间合并成一个有序的区间
        while(i<=R1&&j<=R2){
            if(A[i]<=A[j]){
                tmp.push_back(A[i++]);
            }else{
                tmp.push_back(A[j++]);
            }
        }
        // 将区间剩余的放到后面
        while(i<=R1) tmp.push_back(A[i++]);
        while(j<=R2) tmp.push_back(A[j++]);
        int n=tmp.size();
        // 更新A数组为有序的
        for(int i=0;i<n;i++){
            A[L1+i]=tmp[i];
        }
    }
    
    // 归并排序，我们将排序区间进行两两划分，然后再合并
    void mergeSort(vector<int> &A,int left,int right){
        
        if(left<right){
            int mid=(left+right)>>1;
            // 区间划分
            mergeSort(A,left,mid);
            mergeSort(A,mid+1,right);
            // 区间合并
            merge(A,left,mid,mid+1,right);
        }
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        mergeSort(arr, 0, arr.size()-1);
        
        return arr;
    }
};

NC140 题解 | #排序#

NC140 #排序#

题意分析

思路分析

快速排序法

归并排序法