【LeetCode】手撕系列—912. 排序数组_快排

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

1- 思路

• 使用快排的思想

2- 题解

⭐快排实现数组排序——题解思路

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模式

import java.util.Scanner;

public class sortArray {

    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];
        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;
        }
    }

    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 = 0 ; i < n;i++){
            System.out.print(nums[i]+" ");
        }
    }
}