KJHの博客

记录&回忆

0%

数据结构快速排序

发表于 更新于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

快速排序也是采用分治法，将问题化整归零来处理。

步骤为：

  1. 从数列中调出一个元素，称为 “基准”（pivot）；

  2. 重新排序数列，排序规则就是将数列中比基准值大的放在基准的后面，将比基准值小的放在基准的前面，在这个分区退出之后，该基准就处于数列的中间位置（非绝对中间位置），这个称为分区操作；

  3. 递归地把小于基准值元素的子数列和大于基准值元素的子序列排序。递归的终止条件就是数列的大小是零或一，也就是都已经被排序好了。

通俗点说就是，

  1. 先从数列中取出一个数作为基准；

  2. 分区过程，将比这个数大的数全部放到它的右边，小于或等于它的数全放到它的左边；

  3. 对左右分区重复第 2 步，直到各分区只有一个数或没有数据。

具体流程参见下图（这里以数列的首元素作为基准）：

经过一轮分区，基准值 “4” 已经到了排序好的位置，然后将其左右两边的子数列再次进行分区比较

全部与基准值比较放置后，基准值便到了合理位置，如此递归，知道子序列中的元素为零或一，如上面的 57，7是基准值，位置放好后，其左子数列元素个数为一，右子数列元素个数为零。

从上面的操作图可以很好地理解快速排序的设计思想，就是留出一个空位，然后用数补上，就又留下一个空位，再补上，最后将基准值补上最后一个空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int Partition(int Array[], int left, int right)
{
	int L = left, R = right;
	int pivot = Array[L];

	while (L < R)    
	{
		while ((L < R) && (Array[R] > pivot))
			--R;
		if (L < R)
		{
			Array[L] = Array[R];   //补数的时候，要知道空位在哪
			++L;
		}
	 
		while ((L < R) && (Array[L] < pivot))
			++L;
		if (L < R)
		{
			Array[R] = Array[L];
			--R;
		}
	}
	 
	Array[L] = pivot;    //补上最后的空位
	return L;

}

void QuickSort(int Array[], int left, int right)
{
	if (left < right)
	{
		int pos = Partition(Array, left, right);
		QuickSort(Array, left, pos - 1);           //注意边界
		QuickSort(Array, pos + 1, right);
	}
}

针对上面的 partition() ，下面简化一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Partition(int Array[], int left, int right)
{
    int pivot = Array[left];

    while (left < right)
    {
        while (left < right && Array[right] > pivot)   //两种情况跳出循环
            --right;
        Array[left] = Array[right];                   
     
        while (left < right && Array[left] <= pivot)   //
            ++left;
        Array[right] = Array[left];
    }
     
    Array[left] = pivot;
    return left;

}

复杂度分析：

  1. 快排的时间复杂度取决于快排递归的深度，上面的分治可以用递归树来描述递归算法的执行情况

    ​

细心点就会发现上面这是一棵平衡二叉树（AVL 树，其每个节点的左子树和右子树的高度最多差 1 的二叉查找树），其高度一般都良好地维持在O(logN)，所以快速排序在时间复杂度上性能比较好。上面是AVL 树的前提是 Partition 每次都划分的很均匀（最优情况下）。前面说到快速排序的时间复杂度取决于快排递归的深度，递归树是一棵二叉查找树，其最大深度为 logN，即快速排序会递归 logN，每次对 N 个数进行一次处理，所以其时间复杂度为 O(NlogN)。

  1. 空间复杂度，主要是递归造成的栈空间的使用，最好情况下，递归树的深度为 logN，其空间复杂度也就是O(logn)，最坏情况下，递归树严重不平衡，需要进行 N-1 递归调用，其空间复杂度为O(N)，平均情况下，空间复杂度为O(logN)。

  2. 稳定性，从上可知，元素值得比较和交换是跳跃进行的，所以，快速排序是一种不稳定的排序算法。

一般情况下，快速排序比大部分排序算法都要快，尤其在Partition 很均与的情况下（递归树为AVL树）。