快速排序(Quick Sort)浅析
in Solutions with 5 comments

快速排序(Quick Sort)浅析

in Solutions with 5 comments

一些对快速排序的理解

就像说起map肯定会问到红黑树,那么说起排序自然也少不了快速排序。
之前快速排序也反反复复学了很多次,无奈学了忘,忘了之后又得从头学一遍。快速排序的写法有很多。仅以递归版本为例,partition函数的写法真是千奇百怪,有把pivot换到前面的,也有把pivot换到末尾的,还有压根就不用交换直接指定pivot为array的末端元素的。即使pivot位置确定了,还有若干种元素交换的方法。如果不懂得原理的话那只怕是,学一次忘一次。

总体思想

总体有个分治的思想,我们需要把一个array中的元素分成3类,即pivot比pivot小的哥们儿比pivot大的哥们儿。我们需要有一种动作将这三种元素按照比pivot小的哥们儿-pivot-比pivot大的哥们儿排列。这样的动作之后,pivot会跑到它该有的位置上,后续的排序不需要更改位置。左边的哥们儿只需要在内部进行排序,右边的哥们儿也只需要和自己同一类的哥们儿进行比较排序。所以这个动作就变得至关重要。我们在下面的代码中用partition去表示。

实现

首先写一下主体框架

void quickSort(int* array,int low,int high)
{
    while(low>=high)return;
    int index=partition(array,low,high);
    quickSort(array,low,index-1);
    quickSort(array,index+1,high);
    return;
}

主体框架很简单,如果low和high已经没必要排序了那就直接返回。接下来通过partition函数把我们的pivot放到它最终的位置上,调整小哥们和大哥们儿到两边,返回pivot的下标。做完之后根据index的值,分别对左边和右边的subarray进行quickSort。
接下来写一下最关键的partition函数

int partition(int* array,int low,int high)
{
    int i=low-1;
    for(int j=low;j<=high;++j)
    {
        if(array[j]<=array[high]
        {
            ++i;
            swap(array,i,j);
        }
    }
    return i;

总体的思路就是,要把小于pivot的东西放在左边,大于pivot的东西放在右边。所以从头到尾遍历整个数组,i代表目前已经遍历完的数字中所有比pivot小的数字最后那个位置。如果在遍历数组的时候发现有个数字比pivot小,显然我们把代表小哥们目前位置的i去加1,与当前遍历到的数字(j指向的位置)进行交换。交换完之后i之前(包括i)的数字都小于等于pivot。最后遇到pivot自己,同样符合条件array[j]<=array[high],把pivot放到该放的位置即可,完成了partiton的过程。
至于为什么要选最后那个数字作为pivot?这里假设数组不是基本有序的,所以在任何位置找都没有关系,最后那个地方作为pivot单纯因为方便考虑。
至于swap函数的话,随便怎么写,常规或者异或都可以,这边随便写一下:

void swap(int* array,int a,int b)
{
    int tmp=array[a];
    array[a]=array[b];
    array[b]=tmp];
}

至于递归优化和时间开销的详细分析,下章分解。
(逃 XD

Responses
  1. Buy Amoxicillin Spain Zithromax Sinusitis Dosage Acheter Cialis Belgique cialis 5 mg Do People Overdose On Amoxicillin Generic Worldwide Zentel Internet Cash Delivery Zithromax At Publix

    Reply
  2. Priligy Acquistare In Italia Low Cost Viagra Generic CytotecР’В® Prix Pharmacie Cialis Shipped Ups Bentyl 20mg Medication Bienfaits De Clomid How To Order Amoxicillin Online

    Reply
  3. Levitra Im Preisvergleich Cialis Donde Puedo Comprar Fruta Acai Canadian Drug

    Reply
  4. Amoxicillin No Side Effects http://viacialisns.com - Cialis Liquid Tadalis Sx Soft canadian cialis Acticin Where To Buy Renfrewshire

    Reply
  5. Original Cialis Erkennen http://buyciallisonline.com/# - Cialis Isotretinoin Acne cialis without a doctor's prescription Levitra 40 Mg Samples

    Reply