【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+" ");}}
}