快速排序的优化1: 选取中间值或随机值作为基准，C语言实现

红太狼 2023-03-01 10:22 10阅读 0赞

我们考虑一个问题。如果要排序的数组本身就是有序的，例如：1, 2, 3, 4, 5。用上面的方法排序会发生什么情况？

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]基准数是1，东东从右边开始往左边走，结果一直走到最左边，遇到了虫虫才停止，这个过程中，虫虫根本没有机会移动。也就是说这个基准数本来就在正确的位置。这时这个数组只能被分为两部分，而不是希望的三部分。除了基准数之外，剩下的一部分仅仅比原数组少了一个元素。而这个过程的时间复杂度为O(N)，接下去继续，结果发现每次得到的新数组都仅仅比原先少一个元素，所以一共需要进行N次。这个过程与冒泡排序的运行过程是一样的。也就是说快速排序在遇到有序的数组时会退化成冒泡排序，所以时间复杂度为O(N2)。遇到这样的问题，我们该怎么办呢？  
如果不管三七二十一，我们先把这个数组的最左边的元素与中间元素进行交换，得到一个新数组：3, 1, 2, 4, 5。这时再用上面的方法进行排序，就可以把数组分成三段。时间复杂度可以重新回到O(N \* logN)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]这是改进后的快速排序，与原始的快速排序代码相比，仅仅多了两行代码：

void quickSort(int arr[], int low, int high)
    {
        
    	if(low > high) //递归的出口
    	{
        
    		return;
    	}
    	
    	//如果要排序的数组是有序的。用原始的快速排序方法会导致退化成冒泡排序 
    	//这时如果把中间的元素跟low的元素交换，则每次都能把数组分成几乎相等的两份
    	//增加这两行代码后就可以把时间复杂度重新变为O(N * logN)了。
    	int middle = low + (high - low) / 2; //求中间元素的下标，不要写成 (low + high) / 2
    	swap(middle, low);
    
    	int num = arr[low];
    	int i = low; //虫虫在最左边 
    	int j = high; //东东在最右边 
    	
    	while(i < j) //虫虫和东东没有相遇的时候继续走 
    	{
        
    		//虫虫是哥哥，要让着弟弟，所以每次都是东东先走。 
    		while(i < j && num <= arr[j]) //没有相遇，且右边的元素比基准大 
    		{
        
    			j--; //东东往左走一步 
    		}
    		while(i < j && num >= arr[i]) //没有相遇，且左边的元素比基准大
    		{
        
    			i++; //虫虫往右走一步
    		}
    		
    		if(i < j) //两个小朋友都停止的时候，如果他们还没有相遇 
    		{
        
    			swap(i, j); //说明还没有到家，两个元素交换一下。虫虫和东东没有交换哦 
    		}
    	}
    	
    	//i==j时，虫虫和东东帮基准元素找到家了 
    	//交换一下基准和家里的元素，也就是让基准元素回家，把家里的元素放到最前面 
    	swap(low, i);  
    	
    	//递归函数的等价关系式：用同样的方法帮左边和右边的两段数据排序 
    	quickSort(arr, low, i-1); //左边一段数组继续排序 
    	quickSort(arr, i+1, high); //右边一段数组继续排序
    }

**选择中间的元素作为基准，或者随机选择一个元素作为基准**，这个方法就能解决待排序的数组有序 (升序和降序均可) 时算法退化的问题了。但是这个改进仍然不能解决所有数据都相同时，算法成冒泡排序的问题。下一节，我们将解决这个问题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/0d8736e7e9dd4f279bcf9d3072193c88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/f3e4feab4235447a850b50f3bcc6df8e.png