【CT】LeetCode手撕—手撕快排

发布于:2024-06-17 ⋅ 阅读:(101) ⋅ 点赞:(0)

题目


1-思路-快排

1-1 快排的核心思想

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

image.png

快速排序算法步骤

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

优美的调整区间

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

766AC1FD4EB24C2579F850B29BD8E35B.png

  • 当两个指针都停下来的时候,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+" ");
        }
    }
}

网站公告

今日签到

点亮在社区的每一天
去签到