快速排序、堆排序等各种排序算法C++代码，topK问题

一时失言乱红尘 2023-07-18 12:47 28阅读 0赞

## 一、快速排序 ##

快速排序，面试经常可能碰到的题，今天整理了一下，方便以后自己查看复习。原理可以参见博客：[快速排序的原理][Link 1]  
我也是参考这个博客的，写的挺好的。以下是c++代码。

#include<bits/stdc++.h>
    using namespace std;
    //找到基准数下标
    int getIndex(vector<int>& arr, int low, int high) {
        
       int temp = arr[low];
       while (low < high) {
        
       	while (arr[high] >= temp && high > low)
      	 high--;
       	arr[low] = arr[high];
       	while (arr[low] <= temp && high > low)
       	low++;
       	arr[high] = arr[low];
     }
     arr[low] = temp;
     return low;
    }
    void quickSort(vector<int>& arr, int low, int high) {
        
        if (low < high) {
        
        	int index = getIndex(arr, low, high);
        	quickSort(arr, low, index - 1);
           quickSort(arr, index + 1, high);
        }
    }
    //主函数测试一下
    int main() {
        
        vector<int> arr = {
         2,18,5,1,7,4,39,23 };
        quickSort(arr, 0, arr.size() - 1);
        for (int i = 0; i < arr.size(); i++)
        cout << arr[i]<<" ";
        cout << endl;
    }

输出结果：![在这里插入图片描述][2020032711553916.png]  
快速排序不适合对已基本有序的数据排序，空间复杂度最好是O(logn)，最坏是O(n)；时间复杂度最好是O(nlogn)，最坏是O(n^2)；

如果要用快排找第K小的数，实现如下：

class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            int low=0,high=nums.size()-1;
            while(low<=high){
        
                int index=getIndex(nums,low,high);
                if(index==k-1) return nums[index];
                else if(index<k-1) low=index+1;
                else high=index;
            }
            return -1;
        }
        //找到基准数下标
        int getIndex(vector<int>& nums, int low, int high) {
        
        //加这个随机速度会变快，防止数组元素已经基本有序
            int idx=rand()%(high-low+1)+low;
            swap(nums[idx],nums[high]);
    
            int temp = nums[low];
            while (low < high) {
        
            	//如果要改成找第K大的数，把下面改成nums[high]<=temp
                while (nums[high] >= temp && high > low)
                high--;
                nums[low] = nums[high];
                //如果要改成找第K大的数，把下面改成nums[low]>=temp
                while (nums[low] <= temp && high > low)
                low++;
                nums[high] = nums[low];
            }
            nums[low] = temp;
            return low;
        }
    };

## 二、堆排序，top K ##

如果是找最小的K个值用大顶堆，先从待排序数组中取前K个创建堆，再将后面的数依次与堆顶数比较，小于堆顶则插入，并重新调整堆。如果是找最大的K个值则相反。下面以大顶堆为例。

#include<bits/stdc++.h>
    using namespace std;
    void adjustMinHeap(vector<int>& nums,int root,int len){
        
        int lch=2*root+1;
        int rch=lch+1;
        int index=root;
        //调整最大堆
        if(lch<len && nums[lch]>nums[index]) index=lch;
        if(rch<len && nums[rch]>nums[index]) index=rch;
        if(index!=root){
        
            swap(nums[index],nums[root]);
            adjustMinHeap(nums,index,len);
        }
    }
    vector<int> TopKInHeap(vector<int>& nums,int k){
        
        vector<int> res(nums.begin(),nums.begin()+k);
        //用前k个数建立最大堆
        for(int i=k/2-1;i>=0;i--)
            adjustMinHeap(res,i,k);
        for(int i=k;i<nums.size();i++){
        
            if(nums[i]<res[0]){
        //小于堆顶的数
                res[0]=nums[i];//插入最大堆并进行调整
                adjustMinHeap(res,0,k);
            }
        }
        return res;
    }
    int main() {
        
        int len, k;
        while (cin >> len >> k) {
        
            vector<int> nums(len);
            for (int i = 0; i < len; i++) cin >> nums[i];
            vector<int> res = TopKInHeap(nums, k);
            for (int i = 0; i < k; i++)
                cout << res[i] << ' ';
            cout << endl;
        }
    }

## 三、冒泡排序 ##

void BubbleSort(vector<int>& arr)
    {
        
        int n = arr.size();
        for (int i = 0; i < n - 1; i++)
        {
        
            for (int j = 0; j < n - i - 1; j++)
            {
        
                if (arr[j] > arr[j + 1])
                    swap(arr[j], arr[j + 1]);
            }
        }
    }

# 四、桶排序 #

[见力扣题目，利用桶排序解答][Link 2]

[Link 1]: https://blog.csdn.net/nrsc272420199/article/details/82587933
[2020032711553916.png]: /images/20230528/2f23bc8c72634f16b47ff3db5538edf9.png
[Link 2]: https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode/