【AcWing 785. 快速排序】题解

【AcWing 785. 快速排序】题解

【AcWing 785. 快速排序】

C++ 题解一：手写快排

#include 
using namespace std;
const int N = 1e6 + 10;
int n, q[N];

void quickSort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do ++ i ; while (q[i] < x);
        do -- j ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quickSort(q, l, j);
    quickSort(q, j + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (auto i = 0; i < n; ++ i)   scanf("%d", &q[i]);
    quickSort(q, 0, n - 1);
    for (auto i = 0; i < n; ++ i)   printf("%d ", q[i]);
    return 0;
}

题解二：STL的sort()

#include 
#include 
using namespace std;
const int N = 1e6 + 10;
int n, q[N];

int main()
{
    scanf("%d", &n);
    for (auto i = 0; i < n; ++ i)   scanf("%d", &q[i]);
    sort(q, q + n);
    for (auto i = 0; i < n; ++ i)   printf("%d ", q[i]);
    return 0;
}

题解三：vector + sort()

#include 
#include 
#include 
using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
    vector nums(n);
	for (auto i = 0; i < n; ++ i)	scanf("%d", &nums[i]);
	sort(nums.begin(), nums.end()); // C++ 11 貌似不需要algorithm头文件了
    // for_each(nums.begin(), nums.end(), [](int num) {printf("%d ", num);});
    for (auto num : nums)   printf("%d ", num);
    return 0;
}

题解四：valarray + sort()

#include 
#include 
#include 
using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	valarray nums(n);
	for (auto i = 0; i < n; ++ i)	scanf("%d", &nums[i]);
	sort(begin(nums), begin(nums) + n);
	for_each(begin(nums), end(nums), [](int num) {printf("%d ", num);});
    // for (auto num : nums)   printf("%d ", num);
    return 0;
}

题解五：multiset

#include 
#include 
#include 
using namespace std;

int main()
{
	int n, num;
	scanf("%d", &n);
    multiset nums;
	for (auto i = 0; i < n; ++ i) {
		scanf("%d", &num);
		nums.insert(num);
	}
    // for_each(nums.begin(), nums.end(), [](int num) {printf("%d ", num);});
    for (auto num : nums)   printf("%d ", num);
    return 0;
}

Java 题解一：手写快排

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
        quickSort(nums, 0, n - 1);
        for (var num : nums) System.out.print(num + " "); // Java10可以使用var
    }

    public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;

        int i = l - 1, j = r + 1, x = q[l+r>>1];
        while (i < j) {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            if (i < j) {
                int temp = q[i]; q[i] = q[j]; q[j] = temp;
            }
        }

        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
}

题解二：Arrays.sort() 函数

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = sc.nextInt();
        Arrays.sort(nums, 0, n);
        for (var num : nums) System.out.print(num + " ");
    }
}

Python3 题解一：手写快排

def quickSort(nums, l, r):
    if l >= r: return
    i, j, x = l - 1, r + 1, nums[l + r >> 1]
    while i < j:
        while True:
            i += 1
            if nums[i] >= x: break
        while True:
            j -= 1
            if nums[j] <= x: break
        if i < j: nums[i], nums[j] = nums[j], nums[i]
    quickSort(nums, l, j)
    quickSort(nums, j + 1, r)

n = int(input())
nums = list(map(int, input().split()))
quickSort(nums, 0, n - 1)
for num in nums:
    print(num, end=" ")

AcWing暂时不支持Python3.8的海象运算符（据说近期将升级到3.10），如支持，则可进一步简化
​

def quickSort(nums, l, r):
    if l >= r: return
    i, j, x = l - 1, r + 1, nums[l + r >> 1]
    while i < j:
        while (i := i + 1) >= 0:
            if nums[i] >= x: break
        while (j := j - 1) >= 0:
            if nums[j] <= x: break
        if i < j: nums[i], nums[j] = nums[j], nums[i]
    quickSort(nums, l, j)
    quickSort(nums, j + 1, r)

n = int(input())
nums = list(map(int, input().split()))
quickSort(nums, 0, n - 1)
for num in nums:
    print(num, end=" ")

题解二：list.sort() 方法

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
for num in nums:
    print(num, end=" ")

题解三：heapq.heapify() 函数

import heapq

n = int(input())
nums = list(map(int, input().split()))
heapq.heapify(nums)
for num in nums:
    print(num, end=" ")

解析：heapq.heapify() 函数在列表上原地建（最小）堆。