快速排序(Quick Sort)浅析
in Solutions with 0 comment

快速排序(Quick Sort)浅析

in Solutions with 0 comment

一些对快速排序的理解

就像说起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