【CT】LeetCode手撕—手撕快排

题目

• 原题连接：912. 排序数组

1-思路-快排

1-1 快排的核心思想

• 选择一个基准
  • 基准左侧的元素都小于该元素
  • 基准右侧的元素都大于该元素

快速排序算法步骤

• ① 确定分界点：
  • 方式有三种：第一种取左边界点 q[ l ]；第二种取中间点q[ l+r ]；第三种取右边界点q[ r ]；随机
• ② 调整区间（★难点）
  • 使得左半边区间内的数都小于等于 x ；右半边区间内的数都大于等于 x
• ③ 递归
  • 递归处理左右两段

优美的调整区间

• 用两个指针分别指向数组的左边和右边，两个指针同时往中间走。
• 如果指针 i 指向的数组的元素值小于 x ，则指针 i 向右移动一位，以此类推一直往下移动，直到指针 i 所指向的某个元素的值 大于等于 x，此时指针 i`` 停下不动。
• 同理此时移动指针 j ，若指针 j 指向的元素的值大于等于 x 则指针 j 便向左移动，直到移动到 j 所指向的值小于等于 x 。

• 当两个指针都停下来的时候，swap 交换两个指针指向的数，之后两个指针继续往中间走，以此类推直到两个指针相遇为止。

1-2 ⭐快排的实现

    public void quickSort(int[] nums,int left,int right){
        if(right<=left) return;
        // 定义 
        int i = left-1;
        int j = right+1;
        int x = nums[(i+j)/2];

        while(i<j){
            do{
                i++;
            }while(nums[i]<x);
            do{
                j--;
            }while(nums[j]>x);

            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        quickSort(nums,left,j);
        quickSort(nums,j+1,right);
    }

2- 实现

⭐912. 排序数组——题解思路

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums,int left,int right){
        if(right<=left) return;
        // 定义 
        int i = left-1;
        int j = right+1;
        int x = nums[(i+j)/2];

        while(i<j){
            do{
                i++;
            }while(nums[i]<x);
            do{
                j--;
            }while(nums[j]>x);

            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        quickSort(nums,left,j);
        quickSort(nums,j+1,right);
    }
}

3- ACM 实现

public class quickSort {



    public static void quickSort(int[] nums,int left,int right){
        if(right<=left) return;
        // 定义
        int i = left-1;
        int j = right+1;
        int x = nums[(i+j)/2];

        while(i<j){
            do{
                i++;
            }while(nums[i]<x);
            do{
                j--;
            }while(nums[j]>x);

            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        quickSort(nums,left,j);
        quickSort(nums,j+1,right);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组长度");
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0 ;i < n;i++){
            nums[i] = sc.nextInt();
        }
        quickSort(nums,0,nums.length-1);

        System.out.println("排序结果为");
        for (int i:nums){
            System.out.print(i+" ");
        }
    }
}