快速排序的另种高效率的写法

￡神魔★判官ぃ 2022-08-27 06:51 108阅读 0赞

快速排序是大家所熟知的排序算法，昨天立文问起我这个算法来；虽然代码不费力可以正常跑，可我发现里面有诸多问题；他写的代码就不公布了；

首先，里面的两个小循环的位置不能随意调换的，Pivot的位置和两个小循环的关系密切哦^\_^

第二， 这个程序效率是最高的，其他快速排序的写法每交换一对记录需进行3次赋值，实际上，在排序过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，low = = high的位置才是枢轴的最后位置。

于是，我们可以写出下面的代码：

#include <iostream>
    
    using namespace std;
    
    
    
    int QuickSort(int *asArray, int aiLow, int aiHigh)//left
    
    {
    
    	int liLeft = aiLow;
    
    	int liRight = aiHigh;
    
    	int liPivot = asArray[liLeft];
    
    	
    
    	if(liLeft <liRight)
    
    	{
    
    		while(liLeft < liRight)
    
    		{	
    
    			while(asArray[liRight] >= liPivot&&liLeft < liRight)
    
    				--liRight;
    
    			asArray[liLeft] = asArray[liRight];
    
    			
    
    			while(asArray[liLeft] <=liPivot&&liLeft<liRight) 
    
    				++liLeft;
    
    			asArray[liRight] = asArray[liLeft];
    
    		}			
    
    		asArray[liLeft] = liPivot;
    
    		
    
    		QuickSort(asArray, aiLow, liLeft-1);
    
    		QuickSort(asArray, liLeft+1, aiHigh);
    
    	}
    
    
    
    
    
    	
    
    	return 0;
    
    }
    
    
    
    
    
    int QuickSort2(int *asArray, int aiLow, int aiHigh)//Right
    
    {
    
    	int liLeft = aiLow;
    
    	int liRight = aiHigh;
    
    	int liPivot = asArray[liRight];
    
    
    
    	if(liLeft < liRight)
    
    	{
    
    		while(liLeft < liRight)
    
    		{
    
    			while(asArray[liLeft] <=liPivot&&liLeft<liRight) 
    
    				++liLeft;
    
    			asArray[liRight] = asArray[liLeft];
    
    			
    
    			while(asArray[liRight] >= liPivot&&liLeft < liRight)
    
    				--liRight;
    
    			asArray[liLeft] = asArray[liRight];
    
    		}
    
    	
    
    		asArray[liRight] = liPivot;
    
    		QuickSort(asArray, aiLow, liLeft-1);
    
    		QuickSort(asArray, liLeft+1, aiHigh);
    
    	}
    
    
    
    
    
    	return 0;
    
    }
    
    
    
    int main()
    
    {
    
    	int lsArray[] = {4, 20, 8,1,9, 5, 3, 2};
    
    	QuickSort2(lsArray, 0, 7);
    
    
    
    	return 0;
    
    }

睡觉去，明天晚上再把一些注释补上去，并做下探讨