快速排序和相关题目

快速排序的基本的过程

快速排序的两种实现方式

快速排序的过程在十大排序有讲解,所以这里只是复习

image-20240227173548841

第一种

这里有几点需要注意一下:

  1. left>right
  2. start与end

看下方代码的注释

 public static void quick(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int left = start, right = end;
        int base = nums[left];
     //这里防止当left==right时造成的死循环,不能使用 =
        while (left < right) {
            //这里从右边开始,但是其实从左开始也可以
            while (left < right && nums[right] >= base) {
                right--;
            }
            while (left < right && nums[left] <= base) {
                left++;
            }
            //这里的判断是为了防止当left==right时,多余的交换
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }

        nums[start] = nums[left];
        nums[left] = base;
     //因为要递归,因此start与end的值始终是变化的,因此无法使用固定值
        quick(nums, start left - 1);
        quick(nums, left + 1, end);
    }

第二种

这种方法和上面方法不同一点是,这种方法使用了一个指针,这里也就是arr[j] < pivot时,但是其他都不变

public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //取右边的基准值
            int pivot = arr[right];
            //从-1开始
            int i = left - 1;
            //j从左向右开始,j<right
            for (int j = left; j < right; j++) {
                //当小于基准值的时候,i+1
                if (arr[j] < pivot) {
                    i++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            //哨兵移动到位置pivotIndex上,这里意思是一轮结束后,将pivot放在分割的索引,,类似之前方法的base
            int pivotIndex = i + 1; //这里的意思是,将指针指向未排好序的地方
            
            int temp = arr[pivotIndex];
            arr[pivotIndex] = arr[right];
            arr[right] = temp;

            quickSort(arr, left, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, right);
        }
    }

以上两种方法都可以不随便选择基准值

从原理来看,如果我们选择的pivot每次都正好在中间,效率是最高的,但是这是无法保证的,因此我们需要从最好、最坏和中间情况来分析

  • 最坏情况就是如果每次选择的恰好都是low结点作为pivot,如果元素恰好都是逆序的,此时时间复杂度为O(n^2
  • 如果元素恰好都是有序的,则时间复杂度为 O(n)
  • 折中的情况是每次选择的都是中间结点,此时序列每次都是长度相等的序列,此时的时间复杂度为**(O(nlogn))**

相关题目

数组中第K大的数字

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
 

在解决这道题前,我们再次进行复习快速排序的过程,能够发现快速排序的一个特点:

当我们选择基准值后,进行一次整个循环过后,基准值的位置在与left或right重合处交换过位置后,此后只需要对这个位置的左右进行快速排序,而这个位置的数字一直保持不变

通过上面的结论,我们可以知道,根据数组: {26, 53, 48, 15, 13, 48, 32, 15};

当经过一轮排序(循环后)得到新顺序: {15,15,13,26,48,48,32,53}

此时可以知道,26是索引第3个,也就是说是这个数组第5大的数,

想找到第k大的数,只需要根据k的大小来判断在26的左边或者是右边来寻找

根据这些,可以通过快速排序的方法来求出——也就是快速选择算法

class Solution {
    public int findKthLargest(int[] nums, int k) {
       return quick(nums, 0, nums.length - 1, nums.length-k);
    }

    public static int quick(int[] nums, int start, int end, int k) {
        if ( start == end)
            return nums[k];
        int left = start;
        int right = end;
        // int base = nums[(left+right)>>1];
        int base = nums[start];
        while (left < right) {
            while (left < right && nums[right] >= base) {
                right--;
            }
            while (left < right && nums[left] <= base) {
                left++;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        nums[start] = nums[left];
        nums[left] = base;

        // 判断递归范围
        
       if (left == k) {
            return nums[left];
        } else if (left < k) {
            return quick(nums, left + 1, end, k);
        } else {
            return quick(nums, start, left - 1, k);
        }
    }
}

这里有几个注意点:

  1. 结束条件不需要再使用start>=right,因为当左右相等说明此时已经找到了目标值
  2. 当if (left == k) 时,此时已经找到直接返回即可

对这段代码进行优化: