我对快速排序的理解

快速排序,是九大排序里面平均性能最好的,是对冒泡排序的改进。其运用了分治的思想,不难理解,但是用编程语言描述的时候会相对来说有点困难。

快速排序的方法

步骤为:

  1. 挑选基准值:从数列中挑出一个元素,称为“基准”(pivot)
  2. 分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成。
  3. 递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
    递归到最底部的判断条件是数列的大小是零或一,此时该数列显然已经有序。

上面这段话来自维基百科,如果我翻译翻译那就是:先在数列中随便找个数叫做基准数(pivot)。
1.png

然后将数列中小于pivot的数放到pivot的前面,把大于pivot的放到pivot的后面。

2.png
这样就是一轮排序了,得到的结果就是pivot前面的数字都比pivot小,pivot后面的数字都比pivot要大。然后,我们再用此方法分别将pivot两边的数排一下,其实就是递归了。

3.png

难点分析

看到这里,相信你应该已经知道快速排序是怎么一回事了。但是,说的轻巧,但如何用编程语言实现呢?其实是有挺多种方法的,这也就是为什么大家看的快速排序代码有很多版本。
其中,我认为最好理解的是挖坑法。

图解挖坑法

4.png

代码实现 (C语言)

/* 每一轮的排序 */
int sort(int arr[], int left, int right)
{   
    /* 选择arr[left]作为新坑,并将此值作为基准保存至pivot*/
    int pivot = arr[left];
    /* 当退出循环的时候,left与right相遇,left==right */
    while (left<right)
    {   
        /* right指针从右往左走,直到遇到比pivot值小的数 */
        while(arr[right] > pivot && left < right) right --;
        /* right指针遇到了比pivot值小的数,将其填入坑中, 此时产生新坑arr[right]*/
        arr[left] = arr[right];
        /* left指针从左往右走,直到遇到比pivot值大的数 */
        while(arr[left] < pivot && left < right) left ++;
        /*
        left指针遇到了比pivot值大的数,
        填入刚才的新坑 arr[right]中
        此时产生新坑arr[left] */
        arr[right] = arr[left];
    }
    /* 跳出循环,left==right,将基准值填入上一步产生的坑arr[left] */
    arr[left] = pivot;
    /* 至此所有坑填补完毕,pivot左边的都比pivot值大,右边反之。返回 pivot的下标*/
    return left;
}

void quick_sort(int arr[], int left, int right)
{   
    /* 递归的条件:如果left小于right表明arr数组至少有两个元素,可以进行排序 */
    if(left<right){
        /* 对arr排序,mid是排序后基准值的下标 */
        int mid = sort(arr, left, right);
        /* 由于mid左边的都比基准值小,mid右边的都比基准值大。
        所以,对mid两边的两部分分别排序 */
        quick_sort(arr, left, mid-1);
        quick_sort(arr, mid+1, right);
    }
}

如果觉得不够优雅,也可以整理成一个函数,多引入俩变量。

void quick_sort(int arr[], int left, int right)
{   
    if(left<right){
        int i=left, j=right;
        int pivot = arr[left];
        while(i<j){
            while(arr[j]>pivot && i<j) j--;
            arr[i] = arr[j];
            while (arr[i]<pivot && i<j) i++;
            arr[j] = arr[i];   
        }
        arr[i] = pivot;
        quick_sort(arr, left, i-1);
        quick_sort(arr, i+1, right);
    }
}

end

上面的代码可以作为理解快速排序用,实际上还有挺多小细节可以优化。

标签: 快速排序, 排序

分类: 所有文章,数据结构与算法

添加新评论