快速排序

AcWing 785. 快速排序

题目说明

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

笔者理解

此题是一道排序算法问题，在AcWing题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题有多种解法，根据题目所以使用快速排序，快速排序采用基准元素的方式，将原数组部分进行逐渐有序化进行求解，让我们来看看具体如何实现的吧。

实现

import java.util.Scanner;

class Main {
    /*
     * 快速排序 
     * 分治
     */
    public void quickSort(int[] nums, int left, int right) {
        // 区间内只有一个元素时
        if (left >= right + 1) {
            return ;
        }
        // 这里我们采用左边界作为基准元素
        int temp = nums[left];
        int front = left;
        int rear = right;
        
        // 不断将大于基准元素的数放到后面，小于基准元素的数放到前面
        while (front < rear) {
            while (front < rear && nums[rear] > temp) {
                rear--;
            }
            if (front < rear) {
                nums[front] = nums[rear];
                front++;
            }
            while (front < rear && nums[front] < temp) {
                front++;
            }
            if (front < rear) {
                nums[rear] = nums[front];
                rear--;
            }
        }
        // 整理完成后，确定基准元素应该在的位置
        nums[front] = temp;
        
        // 整理基准元素前面位置的数
        quickSort(nums, left, front - 1);
        // 整理基准元素后面位置的数
        quickSort(nums, front + 1, right);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] nums = new int [n];
        
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Main m = new Main();
        
        m.quickSort(nums, 0, n - 1);
        
        for (int i = 0; i < n - 1; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.print(nums[n - 1]);
    }
}

总结

本题是今天的一题，难度是为简单，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。