数据结构-快速排序（优化版本）

谁借莪１个温暖的怀抱￠ 2023-06-30 10:49 25阅读 0赞

**快速排序的思想是划分交换排序，利用分治法策略把一个序列划分成两个子序列。**

步骤：我们先找一个基准（pivot），在学习中通常会选择第一个数为基准数，先从右往左找第一个比基准数大的数，再从左往右找第一个比基准数小的数，满足（i<j）,交换两个数，再把基准数和a\[i\]交换。  
从此我们就把序列分成\[l,i-1\] 和 \[i+1,r\],把基准数归位。反复递归…就可以把整个序列排好序。

平均时间复杂度为O（n \* log2 （n））

code：

void quicksort(int left,int right)
    { 
    	int i,j,temp,t;
    	if(left>right)
    		return ;
    	temp=a[left];
    	i=left; 
    	j=right;
    	while(i!=j)
    	{ 	
    		while(i<j&&a[j]>=temp)
    			j--;
    		while(i<j&&a[i]<=temp)
    			i++;
    		if(i<j)
    		{ 
    			t=a[i];
    			a[i]=a[j];
    			a[j]=t;
    		}
    	}
    	a[left]=a[i];
    	a[i]=temp;
    	quicksort(left,i-1);
    	quicksort(i+1,right);
    	return ;
    }

我们考虑下最坏时间复杂度  
如果待排序的序列就是有序序列 1 2 3 4 5 6 7…  
利用快排的算法排序，他的时间复杂度达到了O（n^2）。  
解释：每次都选择第一个数为基准数，每次递归只会减少一个数，递归n-1次，  
就是n +（n-1）+ （n-2）+ …+ 3 + 2 + 1 求和公式算出时间复杂度为O（n^2）。  
数据加强了这个模板就过不去…  
比如这个题 [快速排序][Link 1]

那我们怎么办呢？

其实很简单，我们只需要把基准数换一下，  
换成序列中间的数为基准数就可以满足最坏时间复杂度为O（n \* log2 （n））  
步骤就是我们每次选取中间的数为基准数(选取基准数为a\[(l+r)>>1\])，从左往右找比基准数大的，从右往左找比基准数小的，满足条件就交换。这样就把一个序列分成了\[l,j\] 和 \[j+1,r\] (a\[j\]就是分界点，左边(包括a\[j\])都比基准数小，右边都比基准数大 ) ,当然你选择\[l,i-1\] 和 \[i,r\]也是可以(选取基准数为a\[(l+r+1)>>1\])。

code：

void quicksort(ll l,ll r)
    { 
    	ll i,j,temp;
    	if(l>=r)
    		return;
    	temp=a[l+r>>1];
    	i=l-1,j=r+1;
    	while(i<j)
    	{ 
    		while(a[++i]<temp) ;
    		while(a[--j]>temp) ;
    		if(i<j) swap(a[i],a[j]);
    	}
    	quicksort(l,j);  //a[j]就是分界点，左边都比基准数小，右边都比基准数大 
    	quicksort(j+1,r);
    }

[Link 1]: https://www.acwing.com/problem/content/787/