README.md

快速排序

快速排序也采用了分治的思想：把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

快速排序算法模板：

void quickSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left - 1, j = right + 1;
    int x = nums[left];
    while (i < j) {
        while (nums[++i] < x);
        while (nums[--j] > x);
        if (i < j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quickSort(nums, left, j);
    quickSort(nums, j + 1, right);
}

题目描述

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

代码实现

Python3

N = int(input())
nums = list(map(int, input().split()))


def quick_sort(nums, left, right):
    if left >= right:
        return
    i, j = left - 1, right + 1
    x = nums[(left + right) >> 1]
    while i < j:
        while 1:
            i += 1
            if nums[i] >= x:
                break
        while 1:
            j -= 1
            if nums[j] <= x:
                break
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    quick_sort(nums, left, j)
    quick_sort(nums, j + 1, right)


quick_sort(nums, 0, N - 1)
print(' '.join(list(map(str, nums))))

Java

import java.util.Scanner;

public class Main {
    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();
        }
        quickSort(nums, 0, n - 1);
        for (int i = 0; i < n; ++i) {
            System.out.printf("%d ", nums[i]);
        }
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left - 1, j = right + 1;
        int x = nums[left];
        while (i < j) {
            while (nums[++i] < x);
            while (nums[--j] > x);
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        quickSort(nums, left, j);
        quickSort(nums, j + 1, right);
    }
}

JavaScript

var buf = '';

process.stdin.on('readable', function () {
    var chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});

let getInputArgs = line => {
    return line
        .split(' ')
        .filter(s => s !== '')
        .map(x => parseInt(x));
};

function quickSort(nums, left, right) {
    if (left >= right) {
        return;
    }

    let i = left - 1;
    let j = right + 1;
    let x = nums[(left + right) >> 1];
    while (i < j) {
        while (nums[++i] < x);
        while (nums[--j] > x);
        if (i < j) {
            const t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    quickSort(nums, left, j);
    quickSort(nums, j + 1, right);
}

process.stdin.on('end', function () {
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx % 2 === 1) {
            nums = getInputArgs(line);
            quickSort(nums, 0, nums.length - 1);
            console.log(nums.join(' '));
        }
    });
});

Go

package main

import "fmt"

func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	i, j := left-1, right+1
	x := nums[(left+right)>>1]
	for i < j {
		for {
			i++
			if nums[i] >= x {
				break
			}
		}
		for {
			j--
			if nums[j] <= x {
				break
			}
		}
		if i < j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	quickSort(nums, left, j)
	quickSort(nums, j+1, right)
}

func main() {
	var n int
	fmt.Scanf("%d\n", &n)
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &nums[i])
	}

	quickSort(nums, 0, n-1)

	for _, v := range nums {
		fmt.Printf("%d ", v)
	}
}

Rust

use rand::Rng; // 0.7.2
use std::io;

fn quick_sort(nums: &mut Vec<i32>, left: usize, right: usize) {
    if left >= right {
        return;
    }

    let random_index = rand::thread_rng().gen_range(left, right + 1);
    let temp = nums[random_index];
    nums[random_index] = nums[left];
    nums[left] = temp;

    let pivot = nums[left];
    let mut i = left;
    let mut j = right;
    while i < j {
        while i < j && nums[j] >= pivot {
            j -= 1;
        }
        nums[i] = nums[j];
        while i < j && nums[i] < pivot {
            i += 1;
        }
        nums[j] = nums[i];
    }
    nums[i] = pivot;

    quick_sort(nums, left, i);
    quick_sort(nums, i + 1, right);
}

fn main() -> io::Result<()> {
    let mut n = String::new();
    io::stdin().read_line(&mut n)?;
    let n = n.trim().parse::<usize>().unwrap();

    let mut nums = String::new();
    io::stdin().read_line(&mut nums)?;
    let mut nums: Vec<i32> = nums.split(' ').map(|s| s.trim().parse().unwrap()).collect();

    quick_sort(&mut nums, 0, n - 1);
    for num in nums.iter() {
        print!("{} ", num);
    }

    Ok(())
}

C++

#include <iostream>
#include <vector>

using namespace std;
void printvec( const vector<int> &vec, const string &strbegin = "", const string &strend = "" )
{
	cout << strbegin << endl;
	for ( auto val : vec )
	{
		cout << val << "\t";
	}

	cout << endl;
	cout << strend << endl;
}


int partition( vector<int> & vec, int left, int right )
{
	if ( left >= right )
	{
		return left;
	}

	int base = vec[left];
	while ( left < right )
	{
		while ( left < right && vec[right] >= base )
		{
			right--;
		}
		if ( left >= right )
		{
			break;
		}

		vec[left] = vec[right];

		while ( left < right && vec[left] <= base )
		{
			left++;
		}

		if ( left >= right )
		{
			break;
		}

		vec[right] = vec[left];
	}

	vec[left] = base;
	return left;
}


void quicksort( vector<int> & vec, int left, int right )
{
	if ( left >= right )
	{
		return;
	}

	int idx = partition( vec, left, right );
	quicksort( vec, left, idx - 1 );
	quicksort( vec, idx + 1, right );
}


int main( void )
{
	vector<int> vec = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	printvec( vec );
	quicksort( vec, 0, vec.size() - 1 );
	printvec( vec, "after insert sort" );
	return 0;
}