快速排序sort分析

2013年4月16日 由 Creater 留言 »

快速排序是一种交换排序算法,是笔试面试常考的算法,而且应用很广。时间复杂度下界为O(n*log2^n),最坏的情况下O(n^2),是不稳定的排序算法。
大致的思路是:已知数组a,索引开始为s,结束为e。以从小到大排序为例子.sort1
总体思路为将数组序列按照某个基准划分成两个部分,数组中索引小于该基准索引的数都小于等于该元素,数组中索引大于该基准索引的数都大于该元素。这样就将数组划分成两个区间,对这两个区间继续分区间直到每个元素都作为一个区间为止。

1.首先选取一个基准元素tmp,该元素在数组中的索引可以用随机函数生成,通常使用第一个元素;
2.从数组左端到右端扫描,直到当前元素大于基准元素tmp,记录下索引i,很明显a[i]应该在基准的右边;
3.从数组右端到左端扫描,直到当前元素小于基准元素tmp,记录下索引j,很明显a[j]应该在基准的左边;
4.如果i<j,说明存在3-4这样的序列对则交换该序列对;
5.将tmp置换到他该有的位置,这样分区间就完成。
6.递归执行分区间,回到步骤1.

#include <iostream>

using namespace std;

 void swap(int &x,int &y)
 {
 	int tmp;
	tmp = x;
	x = y;
	y = tmp;
 }

 void quick_sort(int *arr,int s,int e)
 {
     if(s < e)
     {
         int tmp = arr[s];
         int i = s+1;
         int j = e;
         while(i < j)
         {
             while(i <= j && arr[i] <= tmp)
             {
                 i++;
             }
             while(i <= j && arr[j] > tmp)
             {
                 j--;
             }
             if(i < j)
             {
                 swap(arr[i],arr[j]);
             }
         }
				 if(s != i-1)
         	swap(arr[s],arr[i-1]);
				 for(int k = s; k <= e;++k) cout<<" "<<arr[k];cout<<endl;
         quick_sort(arr,s,i-2);
         quick_sort(arr,i,e);
     }
 }

 int main()
 		{
		//int arr[] = {2,1,4,3,8,7,5,6};
 		int arr[] = {1,2,3,7,3,5,2,8};
     quick_sort(arr,0,7);
     for(int i = 0 ; i < 8 ; ++i)
     {
         cout<<arr[i]<<" ";
     }
     cout<<endl;
     return 0;
 }

可以看出分区标准为:
1 2 4 3 8 7 5 6
3 4 8 7 5 6
6 7 5 8
5 6 7
第一次执行后,1与2交换了位置,2左边的小于等于2,2右边的大于2.两个子区间为(1)(4,3,8,7,5,6)
第二次执行区间(4,3,8,7,5,6),该子区间又划分成(3)(8,7,5,6)
第三次执行区间(8,7,5,6),该子区间分为(6,7,5)(8)
。。。省略了一个元素区间的分析。

基于这个特点,还可以将快排应用与找前k大元素上面。

广告位

发表评论

你必须 登陆 方可发表评论.