快速排序的优化2: 解决所有数据相同时的退化问题，C语言实现

野性酷女 2023-03-01 12:39 6阅读 0赞

上一节优化解决了数据有序的情况下，快速排序退化成冒泡排序的问题，但仍然不能解决所有数据都一样大的情况下算法退化的问题。其实这个问题很容易解决，我们只需要让虫虫和东东轮流移动即可，这样还能确保两个小朋友每次都在数组中间相遇，使数组分成均匀的两段。  
那么，怎样才能让两个小朋友轮流移动呢？很简单，设定一个变量flag，flag == 0时，让东东先动，flag == 1时，让虫虫先动就可以啦。这个思想很简单，但实现起来需要一点点技巧。下面是代码：

void quickSort(int arr[], int low, int high)
    {
        
    	if(low > high) //递归的出口
    	{
        
    		return;
    	}
    	
    	//用随机位置的一个元素作为基准 
    	int randomIndex = rand()%(high - low + 1) + low;
    	swap(low, randomIndex); //交换首元素和随机位置的数据 
    	
    	int num = arr[low];
    	int i = low; //虫虫在最左边 
    	int j = high; //东东在最右边 
    	
    	while(i < j) //虫虫和东东没有相遇的时候继续走 
    	{
        
    		if(flag == 0) //控制东东先走 
    		{
        
    			//虫东东先走。 
    			if(num <= arr[j]) //没有相遇，且右边的元素比基准大 
    			{
        
    				j--; //东东往左走一步 
    				isRun1 = 1; //标记东东走过了 
    			}
    			else if(num >= arr[i]) //没有相遇，且左边的元素比基准大
    			{
        
    				i++; //虫虫往右走一步
    				isRun1 = 1;//标记东虫虫走过了 
    			}
    		}
    
    		else //控制虫虫先走
    		{
        
    			//这次虫虫先走 
    			if(num >= arr[i]) //没有相遇，且左边的元素比基准大
    			{
        
    				i++; //虫虫往右走一步
    				isRun2 = 1; //标记东虫虫走过了
    			}
    
    			else if(num <= arr[j]) //没有相遇，且右边的元素比基准大 
    			{
        
    				j--; //东东往左走一步 
    				isRun2 = 1; //标记东东走过了
    			}
    		}
    		flag = !flag; //反转标记，让东东和虫虫轮流移动 
    	
    		if(isRun1 || isRun2) //只要东东或虫虫任何一个人走了一步，那就说明还可以继续走 
    		{
        
    			isRun1 = 0; //重新为东东和虫虫设定标记为不能走动 
    			isRun2 = 0;
    		}
    		else //东东和虫虫都不走了，说明要交换一下 
    		{
        
    			if(i < j) //两个小朋友都停止的时候，如果他们还没有相遇 
    			{
        
    				swap(i, j); //说明还没有到家，两个元素交换一下。虫虫和东东没有交换哦 
    			}
    			else 
    			{
        
    				break;	
    			}
    		}
    	}
    	
    	//i==j时，虫虫和东东帮基准元素找到家了 
    	//arr[i] > arr[low]表示虫虫多走一步，这时需要i--，这时的i才是基准真正的家 
    	if(arr[i] > arr[low])
    	{
        
    		i--; //这时的i才是基准真正的家
    	}
    
    	//交换一下基准和家里的元素，也就是让基准元素回家 
    	swap(low, i);  	
    	
    	//递归函数的等价关系式：用同样的方法帮左边和右边的两段数据排序 
    	quickSort(arr, low, i - 1); //左边一段数组继续排序 
    	quickSort(arr, i + 1, high); //右边一段数组继续排序
    }

这一节中，我们又解决了数据完全相同时的排序问题，但仍然没有解决人为构造的数据的问题。例如arr = \[0, 1, 0, 1, 0, 1, 0, 1\]时，算法仍然会退化。下一节我们将彻底解决这些问题。