首页 > 代码库 > 算法---快速排序(quick sort)

算法---快速排序(quick sort)

在前面介绍的排序算法中,最快的排序算法为归并排序,但是归并排序有一个缺陷就是排序过程中需要O(N)的额外空间。本文介绍的快速排序算法时一种原地排序算法,所需的额外空间复杂度为O(1)。

算法介绍:快速排序其实一种根据需找某个元素的具体位置进行排序的方法。比如所存在如下数组

 

选择第一个元素5,找到5最终的位置,即5的左边的数都小于或者等于5,右边的数都大于或者等于5.


从"6"开始,可知6大于5,此处停住,从“2”开始2小于5,因此交换6与2的位置,然后接着往下走,将所有小于等于5的都放在左边,大于等于5的都放在右边,等到如下所示的数组:


此时的索引在4的位置,然后交换5和4的位置,这样就保证了左边的都小于5,右边的都大于5。


然后再分别对5的左右两边重复上述过程即可将数组按升序排列。

算法发复杂度分析:假设每次都从中间将数组分开,且算法的运行时间为T(N),则依据算法的执行过程可知,找到当前元素的位置需要扫面一遍数组即N次,然后再对此元素两边的子数组重复上述操作。为此T(N)=2*T(N/2)+N,解得T(N)=O(NlogN)。

算法实现:

寻找切分点

int sort::partition(int* a, const int low, const int high)
{
	int value = http://www.mamicode.com/a[low];>
快速排序:

void sort::quick_sort(int* a, const int low, const int high)
{
	if(low >= high)
		return;
	int loc = partition(a,low,high);
	quick_sort(a,low,loc-1);
	quick_sort(a,loc+1,high);
}

上述即为快速排序的具体实现。但是对上述算法还有很多的改进之处,比如说对存在大多数重复数据的数组排序,初始切分点的选取等等都可以进行改进。具体的改进如下所示:

对于较小的子数组使用插入排序:

void sort::insert_sort_update(int* a, const int n)
{
	for(int i=1; i<n; i++)
	{
		int j=i;
		int temp = a[i];
		for(; j>0 && temp < a[j-1]; j--)
		{
			a[j] = a[j-1];
		}
		a[j] = temp;
	}
}
void sort::quick_sort_update_with_insert_sort(int* a, const int low, const int high)
{
	if(high <= low+N)
	{
		insert_sort_for_update(a,low,high);
		return;
	}
	int loc = partition(a,low,high);
	quick_sort_update_with_insert_sort(a,low,loc-1);
	quick_sort_update_with_insert_sort(a,loc+1,high);
}

对于含有大多数重复元素的改进:

void sort::quick_sort_update_with_partition(int* a,const int low, const int high)
{
	if(low>=high)
		return;
	int lt = low;
	int gt = high;
	int value = http://www.mamicode.com/a[low];>
上述博文主要介绍了快速排序算法及其改进。欢迎拍砖

算法---快速排序(quick sort)