【排序算法】快速排序

快速排序

各种排序算法的效率(:ms

如果对10万个数据进行排序，则冒泡排序需要8174ms，快速排序只需要3.634ms。

快速排序的基本思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

对比合并排序：
合并排序每次都从中间位置把问题一分为二，一直分解到不能再分时再执行合并操作。
合并排序的划分很简单，但合并操作需要在辅助数组中完成，是一种异地排序的方法。合并排序分解容易、合并难，属于先易后难。
而快速排序是原地排序，不需要辅助数组，但分解困难、合并容易，属于先难后易。

算法设计

快速排序是基于分治策略的，算法思想：

• 分解：先从数列中取出一个元素作为基准元素。以基准元素为标准，将问题分解为两个子序列，使小于或等于基准元素的子序列在左侧，使大于基准元素的子序列在右侧。
• 治理：对两个子序列进行快速排序。
• 合并：将排好序的两个子序列合并在一起，得到原问题的解。

【如何分解】

如果基准元素选取不当，有可能将数据分解成规模0和n-1的两个子序列，这样子的话快排直接变冒泡了。

最理想的状态是选出的基准元素能够将序列分解成两个规模相当的子序列。

一般来说：

• 取第一个元素
• 取最后一个元素
• 取中间位置的元素
• 取第一个元素、最后一个元素、中间位置的元素三者的中位数
• 取第一个元素和最后一个元素之间位置的随机数k

举个栗子：选取第一个元素作为基准元素

当前待排序的序列为r[low : high]，其中low <= high。

（1）取数组的第一个元素作为基准元素pivot=r[low]，i =low，j=high。

（2）从右向左扫描，找小于或等于pivot的数，如果找到，则r[i]和r[j ]交换，i ++。

（3）从左向右扫描，找大于pivot的数，如果找到，则r[i ]和r[j]交换，j --。

（4）重复第2～3步，直到i 和j 重合，返回mid=i ，该位置的数正好是pivot元素。

至此完成一趟排序。此时以mid为界，将原数据分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大。然后分别对这两个子序列进行快速排序。

以序列(30 , 24 , 5 , 58 , 18 , 36 , 12, 42, 39)为例：

1. 初始化。i = low ， j = high ， pivot = r[low] = 30
   

2. 向左走。从数组的右边位置向左找，一直找小于或等于pivot的数，找到r[j] = 12。
   
   r[i] 和 r[j] 交换，i ++。
   

3. 向右这批。从数组的左边位置向右找，一直找比pivot大的数，找到r[i] = 58。
   
   r[i] 和 r[j] 交换，j --。
   

4. 向左走。从数组的右边位置向左找，一直找小于或等于pivot的数，找到r[j] = 18。
   
   r[i] 和 r[j] 交换，i++。
   

5. 向右走。从数组的左边位置向右找，一直找比pivot大的数，此时i = j，第一趟排序结束，返回 i 的位置，mid = i。
   
   此时以mid为界，将原序列分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大。然后分别对两个子序列(12,24,5,18)、(36,58,42,39)进行快速排序。

算法实现

【划分函数】

划分函数对原序列进行分解，将其分解为两个子序列，以基准元素pivot为界，左侧子序列都比pivot小，右侧子序列都比pivot大。先从右向左扫描，找小于或等于pivot的数，找到后两者交换（在r[i ]和r[j ]交换后，i ++）；再从左向右扫描，找比基准元素大的数，找到后两者交换（在r[i ]和r[j ]交换后，j --）。扫描交替进行，直到i =j 时停止，返回划分的中间位置i 。

int Partition(int r[] , int low , int high){ //划分函数
	int i = low , j = high , pivot = r[low] ; //基准元素
	while(i < j){
		while(i < j && r[j] > pivot){ //向左扫描
			j --;
		}
		if(i < j){
			swap(r[i++] , r[j]);  //在r[i]和r[j] 交换后，i + 1，右移1位
		}
		while(i < j && r[i] <= pivot){ //向右扫描
			i ++;
		}
		if(i < j){
			swap(r[i] , r[j--]); //在r[i] 和 r[j] 交换后，j - 1，左移1位
		}
	}
	return i; //返回基准元素位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

【快速排序】

首先对原序列划分，得到划分的中间位置mid；然后以中间位置为界，分别对左半部分(low,mid-1)执行快速排序，对右半部分(mid+1,high)执行快速排序。递归结束的条件是low≥high。

void QuickSort(int r[] , int low, int high){
	if(low < high){
		int mid = Partition(r , low , high); //划分
		QuickSort(r, low , mid - 1); //左区间递归快速排序
		QuickSort(r, mid + 1,high); //右区间递归快速排序
	}
}
1
2
3
4
5
6
7

算法分析

【最好情况】

在最理想情况下，每次划分都将问题分解为两个规模为n /2的子问题，递归求解两个规模为n /2的子问题，合并因为是原地排序，所以合并操作不需要时间复杂度。

快速排序算法在最好情况下的时间复杂度为O (n logn )，空间复杂度为O (logn )。

【最坏情况】

在最坏情况下，每次划分并将问题分解后，基准元素的左侧（或者右侧）都没有元素，基准元素的另一侧为1个规模为n -1的子问题，递归求解这个规模为n -1的子问题，所需时间为T (n -1)，合并因为是原地排序，所以合并操作不需要时间复杂度。

快速排序算法在最坏情况下的时间复杂度为O (n ^ 2 )，空间复杂度为O (n )。

【平均情况】

快速排序算法在平均情况下的时间复杂度为O (n logn )，平均情况下的空间复杂度为O (logn)

快速排序的优化

假设当前待排序的序列为r[low: high]，其中low≤high。

（1）首先取数组的第一个元素作为基准元素，pivot=r[low]，i=low，j =high。

（2）从右向左扫描，找小于或等于pivot的数r[i ]。

（3）从左向右扫描，找大于pivot的数r[j ]。

（4）r[i ]和r[j ]交换，i ++，j --。

（5）重复第2～4步，直到i 和j 相等。此时如果r[i ]大于pivot，则r[i -1]和基准元素r[low]交换，返回该位置，mid=i -1；否则r[i ]和r[low]交换，返回该位置，mid=i 。该位置的数正好是基准元素。至此完成一趟排序。此时以mid为界，将原数据分为两个子序列，左侧子序列都比pivot小，右侧子序列都比pivot大。然后分别对这两个子序列进行快速排序。

算法代码：

int Partition2(int r[], int low ,int high){ //划分函数优化
	int i = low , j = high , pivot = r[low]; //基准元素
	while(i < j){
		while(i < j && r[j] > pivot){ //向左扫描
			j --;
		}
		while(i < j && r[i] <= pivot){ //向右扫描
			i ++; 
		}
		if(i < j){
			swap(r[i ++] , r[j --]); //r[i] 和 r[j] 交换
		}
	}
	if(r[i] > pivot){
		swap(r[i - 1] , r[low]); //r[i-1] 和 r[low]交换
		return i - 1;  //返回基准元素的位置
	}
	swap(r[i] , r[low]); //r[i] 和 r[low]交换
	return i; //返回基准元素的位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20