快速排序模板

提高编程能力：了解主要思想——>模板题——>重复3~5次

题目

给定你一一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

输入格式
输入共两行，第一行包含整数n。
第二行包含n个整数(所有整数均在1~10范围内)，表示整个数列。

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

数据范围
1<n<100000

输入样例:
5
3 1 2 4 5
输出样例:
1 2 3 4 5

C++

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

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int x = q[l], i = l -1, j = 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]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

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

代码注意的几个要点：

1. 输出的%d后加空格；
2. 指针指向数组前后的空位解决边界问题；
3. x 取q[l], q[r], q[l + r >> 1]均可但要注意边界问题

Python代码

def quicksort(array):
  if len(array) < 2:
    # base case, arrays with 0 or 1 element are already "sorted"
    return array
  else:
    # recursive case
    pivot = array[0]
    # sub-array of all the elements less than the pivot
    less = [i for i in array[1:] if i <= pivot]
    # sub-array of all the elements greater than the pivot
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))