快速排序

基本快速排序

快速排序和冒泡排序同属交换排序,但是由于关键字的比较和交换是跳跃进行的,所以是不稳定的排序。

快速排序的基本思想:通过一趟排序讲待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对着两部分记录进行排序,以达到整个序列有序的目的。

C++代码

/**********************************/
/***********快速排序***************/
/**********************************/
int Partition(ElemType a[],int low,int high)
{
//将选取的pivotkey不断交换,将比它小的换到它的左边,比它大的换到它的右边,
//它也在交换中不断更改自己的位置
	int pivotkey;
	pivotkey = a[low];
	while(low < high)
	{
		while(low < high && a[high] >= pivotkey)
			high--;
		swap(a,low,high);
		while(low < high && a[low] <= pivotkey)
			low++;
		swap(a,low,high);
	}
	return low;
}
void QSort(ElemType a[],int low,int high)
{
	int pivot;
	if(low < high)
	{
		pivot = Partition(a,low,high);
		QSort(a,low,pivot-1);
		QSort(a,pivot+1,high);
	}
}

void QuickSort(ElemType a[],int n)
{
	QSort(a,1,n);
}

Python代码

#---------------#
#--Quick sort1--#
#---------------#
def partition(arr,low,high):
		pivotkey = arr[low]
		while low < high:
				while low < high and arr[high] >= pivotkey:
						high -= 1
				swap(arr,low,high)
				while low < high and arr[low] <= pivotkey:
						low +=1
				swap(arr,low,high)
		return low

def qsort(arr,low,high):
		if low < high:
				pivot = partition(arr,low,high)
				qsort(arr,low,pivot-1)
				qsort(arr,pivot+1,high)

def quick_sort(arr):
		arrlen = len(arr)
		qsort(arr,0,arrlen-1)

快速排序复杂度分析
快速排序的时间性能取决于快速排序递归的深度,可以用递归树来描述递归算法的执行情况。
最优情况下,时间复杂度为O(nlogn),空间复杂度O(logn)。
最坏情况下,待排序的序列为正序或逆序,时间复杂度为O(n^2),空间复杂度O(n)。

快速排序优化

1.优化选取pivot
三数取中法,即去三个关键字先进行排序,讲中间数作为pivot,一般取左端、右端和中间,也可以随机选取。

int pivotkey;

int m = low+(high-low)/2;
if(a[low]>a[high]) swap(a,low,high);
if(a[m]>a[high]) swap(a,m,high);
if(a[low]<a[m]) swap(a,low,m);

pivotkey = a[low];//此时已为左中右三个关键字的中间值

2.优化不必要的交换

int Partition(ElemType a[],int low,int high)
{
//将选取的pivotkey不断交换,将比它小的换到它的左边,
//比它大的换到它的右边,它也在交换中不断更改自己的位置
	int pivotkey;
	pivotkey = a[low];
	while(low < high)
	{
		while(low < high && a[high] >= pivotkey)
			high--;
		a[low] = a[high];//采用替换而不是交换的方式
		while(low < high && a[low] <= pivotkey)
			low++;
		a[high] = a[low];
	}
       a[low] = pivotkey;//最后赋值回去
       return low;
}


3.优化小数组时的排序方案
改进QSort,使得其在high-low不大于某个常数时(7或者50,实际调节),就使用直接插入排序,保证最大化的利用两种排序。

4.优化递归操作
如果排序的序列划分极端不平衡,递归深度讲趋近于n,而不是平衡时的logn,这不仅是速度快慢的问题,栈的大小也是有限的。
对QSort实现尾递归

void QSort(ElemType a[],int low,int high)
{
	int pivot;
        //if --> while
        while(low < high)
	{
		pivot = Partition(a,low,high);
		QSort(a,low,pivot-1);
		low = pivot+1;//实现尾递归
	}
}

采用迭代而不是递归的方法缩减堆栈深度,提高了整体性能。

 

Leave a Reply

Your email address will not be published. Required fields are marked *