leetcode(3)排序系列题目

（1）912. 排序数组

class Solution {
public:
    vector sortArray(vector& nums) {
        int n = nums.size();
        SelectSort(nums,n);
        //quickSort(nums,0,n-1,n);
        return nums;
    }
    //插入
    void InsertSort(vector& nums,int n) {
        for(int i=0;i= 0 && nums[j] >temp) {
                nums[j+1] = nums[j];
                j--;
            }
            nums[j+1] = temp;
        }
    }
    //折半插入
    void HInsertSort(vector& nums,int n) {
        int i,j,low,high,mid;
        for( i=0;i tmp){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
            for(j=i-1;j>=high+1;j--){
                nums[j+1] = nums[j];
            }
            nums[high+1] = tmp;
        }
    }
    //希尔
    void ShellSort(vector& nums,int n){
        for(int dk = n/2;dk>=1;dk=dk/2){
            for(int i=dk;i=0&&tmp& nums,int n){
        for(int i=0;ii;j--) {
                if(nums[j-1]>nums[j]){
                    swap(nums[j-1],nums[j]);
                    flag = true;
                }
            }
            if(flag == false){
                return ;
            }
        }
    }
    //快排
    void quickSort(vector&nums ,int left,int right,int n){
        if(left&nums,int low,int high){
        // int pivot=nums[low];//数组的第一个数为主元，会超时
        int pivot=random()%(high-low+1)+low;//随机选择主元的位置，注意是主元的位置
        int tmp=nums[low];
        nums[low]=nums[pivot];
        nums[pivot]=tmp;       //交换主元和第一个元素
        pivot=nums[low];      //注意这里才是主元
        while(low=pivot)--high;
            nums[low]=nums[high];//把比主元小的数移到前面
            //从前向后找比主元大的数
            while(low& nums,int n) {
        for(int i=0;i &nums, int len, int index){
        int left = 2*index + 1; // index的左子节点
        int right = 2*index + 2;// index的右子节点

        int maxIdx = index;
        if(left nums[maxIdx])     maxIdx = left;
        if(right nums[maxIdx])     maxIdx = right;
 
    if(maxIdx != index)
    {
        swap(nums[maxIdx], nums[index]);
        adjust(nums, len, maxIdx);
    }
 
}
 
// 堆排序
    void HeapSort(vector &nums, int size){
       for(int i=size/2 - 1; i >= 0; i--){
            adjust(nums, size, i);
        }
         for(int i = size - 1; i >= 1; i--){
                swap(nums[0], nums[i]);        
                adjust(nums, i, 0);              
            }
        }
};

（2）剑指 Offer 45. 把数组排成最小的数

1、冒泡排序

2、选择排序

3、插入排序

4、希尔排序

5、归并排序-自顶向下

6、归并排序-自底向上

7、快速排序

8、快速排序-三向切分

（3）剑指 Offer 40. 最小的k个数

4种解法秒杀TopK： 快排 / 堆 / 二叉搜索树 / 计数排序

（4）215. 数组中的第K个最大元素

1.快排，因为要取第k大的，从大到小排列，左边是大的右边是小的，

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n = len(nums)
        left, right = 0, n - 1
        while True:
            idx = self.partition(nums, left, right)
            if idx == k - 1:
                return nums[idx]
            elif idx < k - 1:
                left = idx + 1
            else:
                right = idx - 1

    def partition(self, nums, left, right):
        begin = left
        pivot = nums[left]
        while left < right:
            while left < right and nums[right] <= pivot:
                right -= 1
            while left < right and nums[left] >= pivot:
                left += 1
            if left < right:
                nums[left], nums[right] = nums[right], nums[left]
        nums[left], nums[begin] = nums[begin], nums[left]
        return left

2.使用优先队列构造小根堆
参考资料：
写一下常见的排序算法吧!!!
912.排序数组 题目评论
各种常用排序算法的时间复杂度和空间复杂度
经典排序算法的时间复杂度和空间复杂度