每日一题之快速排序

快速排序

1、快速排序原理

快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进。

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

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

• 首先设定一个分界值，通过该分界值将数组分成左右两部分。

• 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。

• 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

• 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

2、快速排序步骤

3、快速排序的代码

• 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);
    }
}

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

• 作者测试

@Test
public void test() {
    int[] str={6,5,4,8,9,7,2,1,3,0};
    int left=0;
    int right=9;
    quicksort(str,left,right);
    for (int i : str) {
        System.out.println(i);
    }
}
public 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);
}

• 通用模板

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

4、快速排序的算法分析

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。

为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H->r[low].key、H->r[high].key与H->r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。

可以证明，快速排序的平均时间复杂度也是O(nlog2n)。因此，该排序方法被认为是目前最好的一种内部排序方法。

从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log2(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(log2n)。