<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??碼云GVP開源項目 12k star Uniapp+ElementUI 功能強大 支持多語言、二開方便! 廣告
                [TOC] ## 算法原理 > 快速排序是圖靈獎得主[?C. R. A. Hoare](http://zh.wikipedia.org/wiki/%E6%9D%B1%E5%B0%BC%C2%B7%E9%9C%8D%E7%88%BE)?于 1960 年提出的一種劃分交換排序。它采用了一種分治的策略,通常稱其為[分治法(Divide-and-ConquerMethod)](http://en.wikipedia.org/wiki/Quicksort)。 [![C. R. A. Hoare](http://bubkoo.qiniudn.com/C.R.A.Hoare.jpg)](https://box.kancloud.cn/2015-07-26_55b453b1daebc.jpg "C. R. A. Hoare") C. R. A. Hoare 分治法的基本思想是:將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題,然后將這些子問題的解組合為原問題的解。 利用分治法可將快速排序的分為三步: 1. 在數據集之中,選擇一個元素作為”基準”(pivot)。 2. 所有小于”基準”的元素,都移到”基準”的左邊;所有大于”基準”的元素,都移到”基準”的右邊。這個操作稱為[分區 (partition) 操作](http://en.wikipedia.org/wiki/Quicksort),分區操作結束后,基準元素所處的位置就是最終排序后它的位置。 3. 對”基準”左邊和右邊的兩個子集,不斷重復第一步和第二步,直到所有子集只剩下一個元素為止。 [![圖片來自維基百科](http://bubkoo.qiniudn.com/Sorting_quicksort_anim.gif)](https://box.kancloud.cn/2015-07-26_55b453d030132.gif "圖片來自維基百科") 圖片來自維基百科分區是快速排序的主要內容,用偽代碼可以表示如下: ~~~ 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 ~~~ 2. 將基準元素與數組中最后一個元素交換位置,如果選擇最后一個元素為基準元素可以省略該步: ~~~ pivot ↓ 3 7 8 4 2 1 9 5 5 ~~~ 3. 從左到右(除了最后的基準元素),循環移動小于基準元素 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 ~~~ 4. 循環結束后交換基準元素和 storeIndex 位置的元素的位置: ~~~ pivot ↓ 3 4 2 1 5 5 9 8 7 ↑ storeIndex ~~~ 那么 storeIndex 的值就是基準元素的最終位置,這樣整個分區過程就完成了。 引用[維基百科](http://en.wikipedia.org/wiki/Quicksort)上的一張圖片: [![圖片來自維基百科](http://bubkoo.qiniudn.com/Partition_example.svg.png)](https://box.kancloud.cn/2015-07-26_55b453d0afa49.png "圖片來自維基百科") 圖片來自維基百科 ## 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)的額外存儲空間,也就跟歸并排序一樣不好。額外需要的存儲器空間配置,在實際上的實現,也會極度影響速度和高速緩存的性能。 > > 摘自[維基百科](http://en.wikipedia.org/wiki/Quicksort) 按照[維基百科](http://en.wikipedia.org/wiki/Quicksort)中的原地(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); } } } ~~~ ## 參考文章 * [wiki Quicksort](http://en.wikipedia.org/wiki/Quicksort) * [維基百科 - 快速排序](http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F) * [快速排序(Quicksort)的Javascript實現](http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html) * [Quicksort in JavaScript](http://www.cnblogs.com/ethanzheng/archive/2013/02/20/quicksort-in-javascript.html) * [經典排序算法 - 快速排序Quick sort](http://www.cnblogs.com/kkun/archive/2011/11/23/2260270.html) * [快速排序(QuickSort)](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.1.htm) * [ソートアルゴリズムを映像化してみた](http://jsdo.it/norahiko/oxIy/fullscreen) * [Stable quicksort in Javascript](http://acatalept.com/blog/2008/10/28/stable-quicksort-in-javascript/) * [Friday Algorithms: Quicksort – Difference Between PHP and JavaScript](http://www.stoimen.com/blog/2010/06/11/friday-algorithms-quicksort-difference-between-php-and-javascript/)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看