算法原理

快速排序是图灵奖得主 C. R. A. Hoare 于 1960 年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)

C. R. A. Hoare
C. R. A. Hoare

分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

利用分治法可将快速排序的分为三步:

  1. 在数据集之中,选择一个元素作为”基准”(pivot)。
  2. 所有小于”基准”的元素,都移到”基准”的左边;所有大于”基准”的元素,都移到”基准”的右边。这个操作称为分区 (partition) 操作,分区操作结束后,基准元素所处的位置就是最终排序后它的位置。
  3. 对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
    图片来自维基百科
    图片来自维基百科分区是快速排序的主要内容,用伪代码可以表示如下:
function partition(a, left, right, pivotIndex)
     pivotValue := a[pivotIndex]
     swap(a[pivotIndex], a[right]) // 把 pivot 移到結尾
     storeIndex := left
     for i from left to right-1
         if a[i] < pivotValue
             swap(a[storeIndex], a[i])
             storeIndex := storeIndex + 1
     swap(a[right], a[storeIndex]) // 把 pivot 移到它最後的地方
     return storeIndex // 返回 pivot 的最终位置

首先,把基准元素移到結尾(如果直接选择最后一个元素为基准元素,那就不用移动),然后从左到右(除了最后的基准元素),循环移动小于等于基准元素的元素到数组的开头,每次移动 storeIndex 自增 1,表示下一个小于基准元素将要移动到的位置。循环结束后 storeIndex 所代表的的位置就是基准元素的所有摆放的位置。所以最后将基准元素所在位置(这里是 right)与 storeIndex 所代表的的位置的元素交换位置。要注意的是,一个元素在到达它的最后位置前,可能会被交换很多次。

一旦我们有了这个分区算法,要写快速排列本身就很容易:

procedure quicksort(a, left, right)
    if right > left
        select a pivot value a[pivotIndex]
        pivotNewIndex := partition(a, left, right, pivotIndex)
        quicksort(a, left, pivotNewIndex-1)
        quicksort(a, pivotNewIndex+1, right)

实例分析

举例来说,现有数组 arr = [3,7,8,5,2,1,9,5,4],分区可以分解成以下步骤:

  1. 首先选定一个基准元素,这里我们元素 5 为基准元素(基准元素可以任意选择):
          pivot
            ↓
3   7   8   5   2   1   9   5   4
  1. 将基准元素与数组中最后一个元素交换位置,如果选择最后一个元素为基准元素可以省略该步:
                              pivot
                                ↓
3   7   8   4   2   1   9   5   5
  1. 从左到右(除了最后的基准元素),循环移动小于基准元素 5 的所有元素到数组开头,留下大于等于基准元素的元素接在后面。在这个过程它也为基准元素找寻最后摆放的位置。循环流程如下:

循环 i == 0 时,storeIndex == 0,找到一个小于基准元素的元素 3,那么将其与 storeIndex 所在位置的元素交换位置,这里是 3 自身,交换后将 storeIndex 自增 1,storeIndex == 1:

                                pivot
                                  ↓
  3   7   8   4   2   1   9   5   5
  ↑
storeIndex

循环 i == 3 时,storeIndex == 1,找到一个小于基准元素的元素 4:

     ┌───────┐                 pivot
     ↓       ↓                   ↓
 3   7   8   4   2   1   9   5   5
     ↑       ↑
storeIndex   i

交换位置后,storeIndex 自增 1,storeIndex == 2:

                              pivot
                                ↓
3   4   8   7   2   1   9   5   5
        ↑           
   storeIndex

循环 i == 4 时,storeIndex == 2,找到一个小于基准元素的元素 2:

        ┌───────┐             pivot
        ↓       ↓               ↓
3   4   8   7   2   1   9   5   5
        ↑       ↑
   storeIndex   i

交换位置后,storeIndex 自增 1,storeIndex == 3:

                              pivot
                                ↓
3   4   2   7   8   1   9   5   5
            ↑           
       storeIndex

循环 i == 5 时,storeIndex == 3,找到一个小于基准元素的元素 1:

            ┌───────┐         pivot
            ↓       ↓           ↓
3   4   2   7   8   1   9   5   5
            ↑       ↑
       storeIndex   i

交换后位置后,storeIndex 自增 1,storeIndex == 4:

                              pivot
                                ↓
3   4   2   1   8   7   9   5   5
                ↑           
           storeIndex

循环 i == 7 时,storeIndex == 4,找到一个小于等于基准元素的元素 5:

                ┌───────────┐ pivot
                ↓           ↓   ↓
3   4   2   1   8   7   9   5   5
                ↑           ↑
           storeIndex       i

交换后位置后,storeIndex 自增 1,storeIndex == 5:

                              pivot
                                ↓
3   4   2   1   5   7   9   8   5
                    ↑           
               storeIndex
  1. 循环结束后交换基准元素和 storeIndex 位置的元素的位置:
                  pivot
                    ↓
3   4   2   1   5   5   9   8   7
                    ↑           
               storeIndex

那么 storeIndex 的值就是基准元素的最终位置,这样整个分区过程就完成了。

引用维基百科上的一张图片:

图片来自维基百科
图片来自维基百科

JavaScript 语言实现

查看了很多关于 JavaScript 实现快速排序方法的文章后,发现绝大多数实现方法如下:

function quickSort(arr) {  
    if (arr.length <= 1) {
        return arr;
    }  
    var pivotIndex = Math.floor(arr.length / 2);  
    var pivot = arr.splice(pivotIndex, 1)[0];  
    var left = [];  
    var right = [];  
    for (var i = 0; i < arr.length; i++) {    
        if (arr[i] < pivot) {      
            left.push(arr[i]);    
        } else {      
            right.push(arr[i]);    
        }  
    }  
    return quickSort(left).concat([pivot], quickSort(right));
}

上面简单版本的缺点是,它需要Ω(n)的额外存储空间,也就跟归并排序一样不好。额外需要的存储器空间配置,在实际上的实现,也会极度影响速度和高速缓存的性能。

摘自维基百科

按照维基百科中的原地(in-place)分区版本,实现快速排序方法如下:

function quickSort(array) {
    // 交换元素位置
    function swap(array, i, k) {
        var temp = array[i];
        array[i] = array[k];
        array[k] = temp;
    }
    // 数组分区,左小右大
    function partition(array, left, right) {
        var storeIndex = left;        
        var pivot = array[right]; // 直接选最右边的元素为基准元素
        for (var i = left; i < right; i++) {
            if (array[i] < pivot) {
                swap(array, storeIndex, i);
                storeIndex++; // 交换位置后,storeIndex 自增 1,代表下一个可能要交换的位置
            }
        }
        swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
        return storeIndex;
    }

    function sort(array, left, right) {
        if (left > right) {
            return;
        }
        var storeIndex = partition(array, left, right);
        sort(array, left, storeIndex - 1);
        sort(array, storeIndex + 1, right);
    }

    sort(array, 0, array.length - 1);
    return array;
}

另外一个版本,思路和上面的一样,代码逻辑没有上面的清晰

function quickSort(arr) {
    return sort(arr, 0, arr.length - 1);

    function swap(arr, i, k) {
        var temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }

    function sort(arr, start, end) {
        sort(arr, 0, arr.length - 1);
        return arr;

        function swap(arr, i, k) {
            var temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }

        function sort(arr, start, end) {
            if (start >= end) return;

            var pivot = arr[start],
                i = start + 1,
                k = end;

            while (true) {
                while (arr[i] < pivot) {
                    i++;
                }
                while (arr[k] > pivot) {
                    k--;
                }

                if (i >= k) {
                    break;
                }
                swap(arr, i, k);
            }

            swap(arr, start, k);
            sort(arr, start, Math.max(0, k - 1));
            sort(arr, Math.min(end, k + 1), end);
        }
    }
}

参考文章

版权及转载说明

本站原创、转载文章欢迎任何形式的转载,但请务必注明出处,尊重他人劳动共创开源社区

本站转载文章版权归原作者所有,如发现本站文章涉嫌侵权请点击「联系我们」反馈,本站将给予删除

本教程数据来源「 http://bubkoo.com/2014/01/17/sort-algorithm/archives/ 」