• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    6年前 (2013-04-16)  算法/数据结构 |   抢沙发  4 
    文章评分 0 次,平均分 0.0

    快速排序是一种交换排序算法,是笔试面试常考的算法,而且应用很广。时间复杂度下界为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大元素上面。

     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/696.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享