「算法刷题」排序专题汇总（力扣版）

本文记录作者刷题过程中与排序相关的题目。

一、通用排序

912. 排序数组（中等难度）

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // 1.选择排序
        //selectSort(nums);
        // 2.冒泡排序
        //bubbleSort(nums);
        // 3.插入排序
        //insertSort(nums);
        // 4.快速排序
        //quickSort(nums,0,nums.size()-1);
        // 5.希尔排序
        //shellSort(nums);
        // 6.归并排序
        //mergeSort(nums, 0, nums.size()-1);
        // 7.堆排序
        heapSort(nums);
        return nums;
    }
    /**选择排序**/
    void selectSort(vector<int> &nums) {
        for(int i=0;i<nums.size();i++){
            // 查找未排序序列中的最值
            int minIndex = i;
            for(int j=i+1;j<nums.size();j++){
                if(nums[minIndex]>nums[j]){
                    minIndex=j;
                }
            }
            // 交换nums[i]和nums[minIndex]
            if(minIndex!=i){
                int temp=nums[minIndex];
                nums[minIndex]=nums[i];
                nums[i]=temp;
            }
        }
    }
    /**冒泡排序**/
    void bubbleSort(vector<int> &nums) {
        bool swapped;
        for(int i=nums.size()-1;i>0;i--){
            swapped = false;
            // 查找未排序序列中的最值
            for(int j=0;j<i;j++){
                if(nums[j]>nums[j+1]){
                    int temp=nums[j+1];
                    nums[j+1]=nums[j];
                    nums[j]=temp;
                    swapped=true;
                }
            }
            if (!swapped) break;
        }
    } 
    /**插入排序**/
    void insertSort(vector<int> &nums) {
        int n = nums.size();
        // 从左至右扩展已排序序列
        for (int i = 1; i < n; i++) {
            // 从右至左在已排序序列交换完成排序
            for (int j = i; j > 0; j--) {
                // 交换元素 swap(nums[j], nums[j-1])
                if(nums[j] < nums[j-1]){
                    int tmp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = tmp;
                }
            }
        }
    }
    
    
    /**快速排序**/
    void quickSort(vector<int> &nums, int left, int right) {
        if (left >= right) return; 
        int first = left, last = right, key = nums[first];
        while (first < last) {
            // 从右往左找到第一个小于key的值
            while (first < last && nums[last] >= key) --last;
            nums[first] = nums[last];
            // 从左往右找到第一个大于key的值
            while (first < last && nums[first] <= key) ++first;
            nums[last] = nums[first];
        }
        nums[first] = key;
        quickSort(nums, left, first-1);
        quickSort(nums, first+1, right);
    }
    
    /**希尔排序**/
    void shellSort(vector<int> &nums) {
        int n = nums.size();
        int h = 1; 
        while (h < n/3) h = 3*h + 1;//初始增量h应该比n/3稍大，不能直接为n/3（因为必须保证h的最后一个值为1）
        for(;h >= 1;h /= 3) {  // 将数组变为h有序
            // 遍历各个组（从h开始）
            for (int i = h; i < n; i++) {
                //遍历各个组中的所有的元素（从右到左，每个组元素索引间隔h）
                for (int j = i-h; j >= 0; j -= h) {
                    if(nums[j] > nums[j+h]){
                        swap(nums[j],nums[j+h]);// 交换两个元素
                    }
                }
            }
        }
    }
    /**归并排序**/
    void mergeSort(vector<int> &nums, int left, int right){
        // 如果 left == right，表示数组只有一个元素，则不用递归排序
        if (left < right) {
            // 把大的数组分隔成两个数组
            int mid = left + (right - left) / 2;
            // 对左半部分进行排序
            mergeSort(nums, left, mid);
            // 对右半部分进行排序
            mergeSort(nums, mid + 1, right);
            // 将两部分合并后再重新排一次序
            //1、先用一个临时数组把他们合并汇总起来
            vector<int> temp(right - left + 1);
            int i = left;
            int j = mid + 1;
            int k = 0;
            //2、分别选取左右两半部分中的较小值放入临时数组
            while (i <= mid && j <= right) {
                // 谁小先放谁到临时数组
                if (nums[i] < nums[j]) {
                    temp[k++] = nums[i++];
                } else {
                    temp[k++] = nums[j++];
                }
            }
            //3、跳出循环的条件i>mid或者j>right,此时两个小数组中有一个一定没有剩余，另一个有未放入临时数组的数
            // 不知道哪个有剩余，干脆两者都判断下，有剩余直接进循环
            while(i <= mid) temp[k++] = nums[i++];
            while(j <= right) temp[k++] = nums[j++];
            // 此时原有数组的左右部分全部复制到临时数组并已排序，把临时数组复制回原数组
            for (i = 0; i < k; i++) {
                nums[left++] = temp[i];
            }
        }
    }
    /**堆排序**/
    void adjust(vector<int> &nums, int len, int parent){
        int left = 2 * parent + 1; // index的左子节点
        int right = 2 * parent + 2;// index的右子节点

        int maxIdx = parent;//假设父节点为最大值
        // 如果左子节点大于最大值，则最大值设为左子节点
        if (left < len && nums[left] > nums[maxIdx])     maxIdx = left;
        // 如果右子节点大于最大值，则最大值设为右子节点
        if (right < len && nums[right] > nums[maxIdx])     maxIdx = right;
        // 如果此时父节点已经不是最大值
        if (maxIdx != parent) {
            swap(nums[maxIdx], nums[parent]);//交换父节点和最大值，
            adjust(nums, len, maxIdx);//交换后，原来最大值的位置可能已不是其对应子树的最大值，所以要重新调整下
        }
    }
    // 堆排序
    void heapSort(vector<int> &nums){
        int len=nums.size();
        // 构建最大堆
        for(int i = (len-1) / 2 ; i >= 0; i--){
            adjust(nums, len, i);// 负责将i为父节点的子树调整为堆
        }
        // 进行堆排序
        for(int i = len - 1; i >= 1; i--){
            // 把最大堆的堆顶元素与最后一个元素交换
            swap(nums[0], nums[i]); 
            // 调整打乱的最大堆，恢复堆的特性   
            adjust(nums, i, 0);              
        }
    }
};

75. 颜色分类（中等难度）

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        if(n<2) return;
        // 整个数组需要分成3个区间:
        int zero = 0;//[0,zero)，红色元素,存放0
        int one = 0;//[zero,one)，白色元素，存放1,同时负责遍历
        int two = n-1;// [one,two)，篮色元素，存放2
        while (one < n) {
            // 如果当前元素==0,移动到头部
            if (nums[one] == 0&&zero<one) 
                swap(nums[one], nums[zero++]);
            
            // 如果当前元素==2,移动到表尾
            else if (nums[one] == 2&& one<two) {
                swap(nums[one], nums[two--]);
            }
            // 如果当前元素==1，跳过
            else {
                one++;
            }
        }
    }
    void quickSort(vector<int>& nums, int left,int right){
        if (left >= right) return; 
        int first=left,last=right,key=nums[first];
        // 开始分区
        while(first<last){
            // 从右到左找第一个比key小的数
            while (first<last&&nums[last]>=key)last--; 
            nums[first]=nums[last];
            // 从左到右找第一个比key大的数
            while (first<last&&nums[first]<=key )first++;
            nums[last]=nums[first];
        }
        nums[first]=key;//基准值归位
        // 结束分区
        quickSort(nums,left,first-1);
        quickSort(nums,first+1,right);
    }
};

179. 最大数（中等难度）

class Solution {
public:
    static bool cmp(int a,int b){
        string sa = to_string(a);
        string sb = to_string(b);
        return sa+sb>sb+sa;//难点，首字母相同的树，C++默认比较第二个字母
    }

    string largestNumber(vector<int>& nums) {
        string result;
        sort(nums.begin(),nums.end(),cmp);//将每个数排序
        if(nums[0]==0) return "0";// 排除特殊情况，第1个数字是0
        // 将数组内的数拼接起来
        for(auto num:nums) result+=to_string(num);
        return result;
    }
};

252. 会议室（简单难度）

class Solution {
public:
    static bool cmp(pair<int, int>&a,pair<int, int>&b){
        // 如果两个时间点相同，则结束时间在前
        if(a.first==b.first) return a.second<b.second;
        // 如果两个时间点不同，则小的时间在前
        else return a.first<b.first;
    }
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n < 2) return true;
        // 将所有的开始时间和结束时间加入数组
        vector<pair<int, int>>  times;
        for (auto & inter : intervals) {
            times.emplace_back(make_pair(inter[0],1));//会议开始，会议室+1
            times.emplace_back(make_pair(inter[1],-1));//会议结束，会议室-1
        }
        // 将所有的时间点排序
        sort(times.begin(), times.end(), cmp); 
        int works = 0, res = 1;                             
        for (auto & t : times) {
            works += t.second;// 此时开会的会议室数量
            res = max(res, works);// 记录最多数量
        }
        return res==1;
    }
};

253. 会议室 II（中等难度）

class Solution {
public:
    /*按这道题其实就是操作系统课程中，
    计算确定运行时间的多线程占用资源至少数量的问题，
    创建一个序列记录每个会议的起止时间，
    并用1和-1分别标记这个时间是开始还是结束，
    这样就能确定某个时刻有几个会议室处于工作中*/
    static bool cmp(pair<int, int>&a,pair<int, int>&b){
        // 如果两个时间点相同，则结束时间在前
        if(a.first==b.first) return a.second<b.second;
        // 如果两个时间点不同，则小的时间在前
        else return a.first<b.first;
    }
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n < 2) return n;
        // 将所有的开始时间和结束时间加入数组
        vector<pair<int, int>>  times;
        for (auto & inter : intervals) {
            times.emplace_back(make_pair(inter[0],1));//会议开始，会议室+1
            times.emplace_back(make_pair(inter[1],-1));//会议结束，会议室-1
        }
        // 将所有的时间点排序
        sort(times.begin(), times.end(), cmp); 
        int works = 0, res = 1;                             
        for (auto & t : times) {
            works += t.second;// 此时开会的会议室数量
            res = max(res, works);// 记录最多数量
        }
        return res;
    }
};

二、插入排序

147. 对链表进行插入排序

class Solution {
public:
    // 从小到大排序，难点：插入算法的思想，搜索插入位置
    ListNode* insertionSortList(ListNode* head) {
        if(head==nullptr) return nullptr;
        // 新建虚拟头结点
        ListNode* myHead=new ListNode(0);
        myHead->next=head;
        // 双指针进行插入排序
        ListNode* lastSorted=head;//最后一个排序好的节点
        ListNode* cur=head->next;// 当前遍历到的节点
        while(cur){
            // 如果当前节点值>最后一个排序好的节点，直接+1
            if(cur->val>=lastSorted->val){
                lastSorted=lastSorted->next;
            }
            // 如果当前节点值<最后一个排序好的节点，从头遍历寻找插入位置
            else{
                ListNode* prev = myHead;//从虚拟头结点开始
                // 遍历找到第一个prev->next的值大于cur的值
                while (prev->next->val <= cur->val) {
                    prev = prev->next;
                }
                // 保存cur的后一个元素
                lastSorted->next = cur->next;//排序好的节点+1
                // 在prev后面插入cur
                cur->next = prev->next;//当前节点
                prev->next = cur;
            }
            cur = lastSorted->next;
        }
        return myHead->next;
    }
};

三、快速排序

215. 数组中的第K个最大元素（中等难度）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        //从大到小排序，第k大就是第k-1个索引，返回第k-1个索引的值
        return quickFind(nums,k-1,0,len-1);
    }
    // 快排法
    int quickFind(vector<int>& nums, int k,int left,int right){
        int index = partition(nums,left,right);//开始分区
        // 结束分区
        if(index==k) return nums[index];//first是基准值索引，表示第first个
        else if(index>k)  return quickFind(nums, k,left,index-1);
        else return quickFind(nums, k,index+1,right);
    }
    // 分区函数
    int partition (vector<int> &nums, int first, int last) {
        int key = nums[first];//默认第一个为基准值
        while (first < last) {
            // 从右往左找到第一个小于key的值
            while (first < last && nums[last] <= key) --last;
            nums[first] = nums[last];
            // 从左往右找到第一个大于key的值
            while (first < last && nums[first] >= key) ++first;
            nums[last] = nums[first];
        }
        nums[first] = key;// 基准值归位
        return first;// 返回索引
    } 
};

四、归并排序

88. 合并两个有序数组

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> temp(m+n);//临时数组
        int i=0,j=0,k=0;//双指针 //从小到大
        while(i<m&&j<n){
            if(nums1[i]<nums2[j]) temp[k++]=nums1[i++];
            else temp[k++]=nums2[j++];
        }
        while(i<m) temp[k++]=nums1[i++];
        while(j<n) temp[k++]=nums2[j++];
        for(int i=0;i<m+n;i++) nums1[i]=temp[i];
    }
};

21. 合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* result = new ListNode(-1); // 结果链表,默认第一个为虚拟头结点
        ListNode* p = result;// 遍历指针，该指针会变化
        while(list1!=NULL&&list2!=NULL){
            if(list1->val<=list2->val){
                p->next=list1;
                list1=list1->next;
                p=p->next;
            }
            else{
                p->next=list2;
                list2=list2->next;
                p=p->next;
            }
        }
        while(list1!=NULL){
            p->next=list1;
            list1=list1->next;
            p=p->next;
        }
        while(list2!=NULL){
            p->next=list2;
            list2=list2->next;
            p=p->next;
        }
        return result->next;
    }
};

剑指 Offer 51. 数组中的逆序对

class Solution {
public:
    /*逆序对：数组中的长度为2且第1个元素大于第2个元素的子序列
    该题可以利用归并排序，归并排序先划分出若干个有序数组，然后合并
    合并时，需要比较有序前半段nums[i]和有序后半段的nums[j]：
    如果nums[i]<=nums[j]：说明当前位置没有逆序；
    如果nums[i] > nums[j]: 说明在有序的前半段中，位置i的都已经比nums[j]大,
    则前半段中位置i及其后面的数字一定比nums[j]大，大的数是区间[i,mid]，则
    每次累加mid-i+1
    该题的答案只在归并排序中加了一个res+=mid-i+1*/
    int res=0;
    int reversePairs(vector<int>& nums) {
        mergeSort(nums,0,nums.size()-1);
        return res;
    }
    void merge(vector<int>& nums,int left,int mid,int right){
        //1、先用一个临时数组把他们合并汇总起来
        vector<int> temp(right - left + 1);
        int i = left;
        int j = mid + 1;
        int k = 0;
        //2、分别选取左右两半部分中的较小值放入临时数组
        while (i <= mid && j <= right) {
            // 谁小先放谁到临时数组(注意必须等号)
            if (nums[i]<=nums[j]) temp[k++]=nums[i++];
            else {
                res+=mid-i+1;// 本题在归并排序算法添加的唯一一行
                temp[k++]=nums[j++];
            }
        }
        //3、跳出循环的条件i>mid或者j>right,
        //此时两个小数组中有一个一定没有剩余，另一个有未放入临时数组的数
        // 不知道哪个有剩余，干脆两者都判断下，有剩余直接进循环
        while(i<=mid) temp[k++]=nums[i++];
        while(j<=right) temp[k++]=nums[j++];
        // 此时原有数组的左右部分全部复制到临时数组并已排序，把临时数组复制回原数组
        for (i = 0; i < k; i++) nums[left++] = temp[i];
    }
    void mergeSort(vector<int> &nums, int left, int right){
        if(left>=right) return;// 表示数组只有一个元素，则不用递归排序
        // 把大的数组分隔成两个数组
        int mid = left+(right-left) / 2;
        // 对左半部分进行排序
        mergeSort(nums, left, mid);
        // 对右半部分进行排序
        mergeSort(nums, mid +1, right);
        // 将两部分合并后再重新排一次序
        merge(nums, left, mid,right);
    }
};

五、堆排序

​ 堆排序（heap-sort）是利用一种叫做堆（heap）的数据结构所设计的排序算法。堆本质上就是用数组实现的二叉树，所以也叫做二叉堆。堆有一个性质，叫做堆有序。根据这种堆有序的性质，堆分为2种，最大堆（大顶堆）和最小堆（小顶堆）。在最大堆中，父节点的值都比每一个子节点的值要大；在最小堆中，父节点的值都比每一个子节点的值要小。（注意和二叉搜索树的区别，二叉搜索树是左子树的值比父节点的值小，右子树的值比父节点的值大）。下图是一个最大堆的内部数据的逻辑结构，根据这种特点，给定任意一个数所在的索引index，我们就可以知道它的父节点索引或者左右子节点的索引。

1、算法思路

​ 假设从小到大排序，堆排序的基本思路是先将整个无序数组构造成一个最大堆，那么最大堆的根节点一定就是全局最大的数，将其取出来放入已排序序列；删除掉根节点的最大堆在重新构建一个最大堆，从而又找到了一个局部最大值，接着将其放入已排序序列，当无序序列中构建最大堆的数只剩下一个时，排序也就完成。过程如下：

2、编码思路

​ 在上述思路分析中，可知将一个无序序列转换为堆是最关键的步骤。最大堆是一个父节点都大于子节点的二叉树，在编码上可以采取递归的方式来实现。

​ 假设我们有一个函数adjust()，其功能就是负责将i为根节点的子树调整为堆有序，即满足最大堆或最小堆，那么我们借助这个adjust就可以写出如下堆排序的代码：

​ 现在我们的任务就是写出adjust函数，其也利用了二叉树递归的思路，只要保证每个小子树中父节点比孩子节点都大或者都小即可，如下：

3、性能分析

​ 先给出堆排序的性能分析结论：

​ 此时我们已经完成了整个堆排序的任务，最重要的是adjust的实现，读者要多默写几遍。

​ 为了帮助读者学习该算法，笔者给出了自己写本文的参考资料和代码。本文的归并排序的代码如下：

//调整为堆有序，len是调整的序列长度，parent是堆对应的二叉树的根节点索引
void adjust(vector<int> &nums, int len, int parent){
    int left = 2 * parent + 1; // parent的左子节点
    int right = 2 * parent + 2;// parent的右子节点

    int maxIdx = parent;//假设父节点为最大值
    // 如果左子节点大于最大值，则最大值设为左子节点
    if (left < len && nums[left] > nums[maxIdx])     maxIdx = left;
    // 如果右子节点大于最大值，则最大值设为右子节点
    if (right < len && nums[right] > nums[maxIdx])     maxIdx = right;
    // 如果此时父节点已经不是最大值
    if (maxIdx != parent) {
        swap(nums[maxIdx], nums[parent]);//交换父节点和最大值，
        adjust(nums, len, maxIdx);//交换后，原来最大值的位置可能已不是其对应子树的最大值，所以要重新调整下
    }
}
/**堆排序**/
void heapSort(vector<int> &nums){
    int len=nums.size();
    // 构建最大堆（从右向左依次传入父节点的索引i，最右侧的父节点索引一定是（len-1）/2）
    for(int i = (len-1) / 2 ; i >= 0; i--){
        adjust(nums, len, i);// 负责将i为根节点的子树调整为堆
    }
    // 进行堆排序
    for(int i = len - 1; i >= 1; i--){
        // 把最大堆的堆顶元素与最后一个元素交换
        swap(nums[0], nums[i]); 
        // 调整剩余的打乱的数为最大堆，其根节点索引始终是0，长度为i（i=1时表示排序完成）
        adjust(nums, i, 0);              
    }
}

六、桶排序/计数排序

1365. 有多少小于当前数字的数字（简单难度）

方法一：

class Solution {
public:
    /* [8,1,2,2,3]排序后就是[1,2,2,3,8],其索引就是[0,1,2,3,4]
    最终想要[0,1,1,3,4],发现除了重复元素其他就是其所在索引*/
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<pair<int, int>> data;// 数字-索引
        int n = nums.size();
        for (int i = 0; i < n; i++) data.emplace_back(nums[i], i);
        // 按照数字从小到大排序，排序后
        sort(data.begin(), data.end());
        // 预先建立一个n个元素的数组
        vector<int> res(n, 0);
        // 遍历索引
        int prev = -1;
        for (int i = 0; i < n; i++) {
            if (prev==-1|| data[i].first != data[i - 1].first) {
                prev=i;
            }
            res[data[i].second] = prev;// 对应索引
        }
        return res;
    }
};

七、奇偶排序

八、拓扑排序

二、堆排序

​