数据结构与算法——排序算法—（3）快速排序

比眉伴天荒 2022-04-23 13:06 284阅读 0赞

1.3 快速排序  
快速排序（Quick Sort）的基本思想是选择一个基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的数据都比另一部分的所有数据要小。然后，在按此方法对这两部分的数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序流畅：  
（1） 从数列中挑出一个基准值。  
（2） 将所有比基准值小的摆放在前面，所有比基准值大的放在后面（相同的数可以任意一边）；在这个分区退出之后，该基准值就处于数列的中间位置。  
（3） 递归地把基准值前面和后面的子序列进行排序

//快速
    void quickSort(int* array, int low, int high)
    {
    	if (low >= high)
    	{
    		return;
    	}
    	int first = low;
    	int last = high;
    	int key = array[first];
    
    	while (first < last)//>=退出循环
    	{
    //从右往左，比基准值大的继续执行while,找到比基准值小的跳出while
    		while (first < last && array[last] >= key)
    		{
    			--last;
    		}
    		//将第一个比基准值小的数，放在first的位置。（不是最左边）
    		array[first] = array[last];
    
    //从左往右，比基准值小的继续执行while，找到比基准值大的跳出while
    		while (first < last && array[first] <= key)
    		{
    			++first;
    		}
    		//将第一个比基准值大的数，放在last的位置。（不是最右边）
    		array[last] = array[first];
    
    	}
    	array[first] = key ;//将基准值还原到相应位置
    	quickSort(array,low,first-1);//基准值位置之前 -1
    	quickSort(array, first+1, high);//基准值位置之后 +1
    
    }

快速排序的时间复杂度和稳定性

快速排序时间复杂度：快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N\*lgN)。  
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。  
(01) 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。  
(02) 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

快速排序稳定性：不稳定

快速排序目前被认为是同数量级O(nlgn)中最快的内部排序方法