《漫谈数据结构与算法之：Quick Sort (1)》

发表于 | 分类于 | 阅读次数

最近闲来无事，重新学习了一下算法，选用的教材则是大名鼎鼎的《算法导论》。不得不说算法导论真的是一本神书，只是当年自己过于年轻而不得其精髓。在看算法导论之前，自己对快排的理解只停留在实现和使用上，但是对里面的思想却一无所知。总的来说快排是分治思想的一种体现，而书中对快排优化时采用的随机算法和概率分析，让我不禁感慨理论才是指导实践的第一标准。

1. 经典的快排算法

快速排序的基本思想是：先选一个“主元”，用它对整个待排序列进行筛选，以保证：其左边的元素都不大于它，其右边的元素都不小于它。这样，排序问题就被分割为两个子区间。再分别对子区间排序就可以了。

简单的递归实现：
void QuickSort(int* array,int left,int right){
    //表示已经完成一个组
	if(left >= right){ 
		return;
	}
    //获取枢轴的位置，并保证主元左边的元素都不大于它，其右边的元素都不小于它
	int index = PartSort(array,left,right);
	QuickSort(array,left,index - 1);
	QuickSort(array,index + 1,right);
}

其中代码的核心部分便是 PartSort()函数，而PartSort()函数又有三种实现方式，包括 左右指针法，挖坑法和前后指针法。下面分别介绍这三种算法的实现方式和原理：

1. 左右指针法

原理：

  1. 选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。
  2. 设置两个变量left = 0;right = N - 1;从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
  3. 重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int PartSort(int* array,int left,int right){
	int& key = array[right];
	while(left < right){
		while(left < right && array[left] <= key){
			++left;
		}
		while(left < right && array[right] >= key){
			--right;
		}
		swap(array[left],array[right]);
	}
	swap(array[left],key);
	return left;
}
2. 挖坑法

原理：

  1. 选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴，也是初始的坑位。
  2. 设置两个变量left = 0;right = N - 1;
  3. 从left一直向后走，直到找到一个大于key的值，然后将该数放入坑中，坑位变成了array[left]。
  4. right一直向前走，直到找到一个小于key的值，然后将该数放入坑中，坑位变成array[right]。
  5. 重复3和4的步骤，直到left和right相遇，然后将key放入最后一个坑位。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int PartSort(int* array,int left,int right){
	int key = array[right];
	while(left < right){
		while(left < right && array[left] <= key){
			++left;
		}
		array[right] = array[left];
		while(left < right && array[right] >= key){
			--right;
		}
		array[left] = array[right];	 
	}
	array[right] = key;
	return right;
}
3. 前后指针法

原理:

  1. 定义变量cur指向序列的开头，定义变量pre指向cur的前一个位置。
  2. 当array[cur] < key时，cur和pre同时往后走，如果array[cur]>key，cur往后走，pre留在大于key的数值前一个位置。
  3. 当array[cur]再次 < key时，交换array[cur]和array[pre]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int PartSort(int* array,int left,int right){
	if(left < right){
		int key = array[right];
		int cur = left;
		int pre = cur - 1;
		while(cur < right){
            //如果找到小于key的值，并且cur和pre之间有距离时则进行交换。
			while(array[cur] < key && ++pre != cur)	{
				swap(array[cur],array[pre]);
			}
			++cur;
		}
		swap(array[++pre],array[right]);
		return pre;
	}
	return -1;
}

2. 快排的时间复杂度分析

快速排序的时间复杂度和每次划分的比例相关其公式如下所示:

1
2
T（n）= T（n/a） + T(n/b) + n
T（1）= 0
1 . 最优情况

在最优情况下Partition每次都划分的很均匀，即每次都对半分。则 T(n) = 2 T(n/2) + n

解得 Ｔ(n) = O(nlogn)

2. 最坏情况：

而最坏情况Partition每次都划分的极不均匀，即每次都分成1个和n-1个。则 T(n) = T(n-1) + T(1) + n

解得 Ｔ(n) = O(n^2)

由于markdown打公式非常累具体过程可以参照：https://www.cnblogs.com/LzyRapx/p/9565827.html

3. 随机快排

从上面的分析可知，当快排遇到已排好的数据时时间复杂度会降到 O(n^2) 的复杂度，那么怎么避免出现这种情况呢，使得无论输入数据是什么都有一个较为稳定的性能。其实实现的方法非常简单因为传统的快排在选取主元的时候，每次都选取最右/左边的元素。当序列为有序时，会发现划分出来的两个子序列一个里面没有元素，而另一个则只比原来少一个元素。为了避免这种情况，我们可以引入一个随机化量来破坏这种有序状态。即随机取一个主元而不是取最右/左边的元素。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int PartSort(int* array,int left,int right){
	int random = randomValue(left, right);
    int key = array[random];
	while(left < right){
		while(left < right && array[left] <= key){
			++left;
		}
		array[right] = array[left];
		while(left < right && array[right] >= key){
			--right;
		}
		array[left] = array[right];	 
	}
	array[right] = key;
	return right;
}

由于使用了随机选取主元的方式，所以随机快排的时间复杂度和输入数据的顺序便不相关了，使得他趋避免了最坏的情况而更加近于平均时间复杂度O(nlogn)使得快排的性能得到了保障，避免了出现性能极差的情况。

4. 三数取中

由于随机基准选取的随机性(即使是同一个数组，多次运行的时间也大有不同)，使得它并不能很好的适用于所有情况。虽然随机数算法能有效的减少升序数组排序所用的时间，并且数组元素越多，随机数算法的效果越好（无限趋近O(nlogn)）。但是在一个有0万个元素而且各不相同的上升序数组中，第一次划分时，基准选的最差的概率就是十万分之一，当然选择最优基准的概率也是十万分之一。这使得随机快排的性能非常不稳定，O(nlogn)的复杂度只是一个理论上的平均值。因此除了随机选取基准之外，比较好的方法是使用三数取中选取基准。它的思想是：选取数组开头，中间和结尾的元素，通过比较，选择中间的值作为快排的基准。其实可以将这个数字扩展到更大(例如5数取中，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

int NumberOfThree(int array[],int left,int right){
    int mid = left + ((right - left) >> 1);
    if (array[mid] > array[right]){
        Swap(array[mid],array[right]);
    }
    if (array[left] > array[right]){
        Swap(array[left],array[right]);
    }
    if (array[mid] > array[left]) {
        Swap(array[mid],array[left]);
    }
    return array[left];
}

......

int PartSort(int* array,int left,int right){
	int random = randomValue(left, right);
    int key = array[random];
	while(left < right){
		while(left < right && array[left] <= key){
			++left;
		}
		array[right] = array[left];
		while(left < right && array[right] >= key){
			--right;
		}
		array[left] = array[right];	 
	}
	array[right] = key;
	return right;
}