本文主要是介绍【CT】LeetCode手撕—手撕快排,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
- 题目
- 1-思路-快排
- 1-1 快排的核心思想
- 快速排序算法步骤
- 优美的调整区间
- 1-2 ⭐快排的实现
- 2- 实现
- ⭐912. 排序数组——题解思路
- 3- ACM 实现
题目
- 原题连接: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+" ");}}
}
这篇关于【CT】LeetCode手撕—手撕快排的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!