快速排序

自己對快速排序的一些理解和心得

像是冒泡排序的升級版，也有著插入排序的影子，大多數情況下，效率最高

核心思想:分而治之,與二分查找法有點聯系，像是一種東西的正反兩用，

舉個生活中的例子，就像切豆腐，一塊豆腐切成兩塊，給兩個人，原先一個人的作業量，相當于兩個人完成，效率近似于一半(畢竟切開這個動作，再給兩個人這都是浪費效率的)，然后兩塊豆腐再切開，最開始一個人的作業量，四個人共同完成，這就是快速排序為什么快，就像細胞分裂一樣，這種速度是相當恐怖的，也可以想象下2的次冪
當然如果只是很小的一塊豆腐，那這樣來回分，反倒不如直接一個人切來的快，所以，快速排序的時間復雜度（效率）會隨著資料量的增加，慢慢顯露出其明顯的優勢,平均效率為O(nlogn)
而我們也可以看出，豆腐切開的點，也就是入刀點尤其重要，因為只有最中間的時候，才是最快的，如果從豆腐的最邊緣切開，那無疑一個人，還是切那一塊豆腐，而另一個人完全是摸魚了

選擇入刀點的方法:前人總結出來的比較優秀的一種方法，是開頭，結尾，中間位置取三個數，然后求中位數

執行流程:quick方法,把第一次的實參傳遞給quickSort,并呼叫quickSort方法,quickSort,先呼叫median方法,取得中位數,然后依次執行完，再根據條件，是否繼續遞回,全部遞回完,順序就排好了

下面附上用js實作的代碼:

<script>
    // 封裝一個方法,使原型方法之間能互相呼叫,更方便
    function Arr() {
        this.array = []

        //往陣列里添加元素
        Arr.prototype.insert = function (item) {
            this.array.push(item)
        }
        
        //把結果轉換為字串形式
        Arr.prototype.toString = function () {
            return this.array.join()
        }
    
        //兩個數進行交換
        Arr.prototype.swap = function (m, n) {
            var temp = this.array[m]
            this.array[m] = this.array[n]
            this.array[n] = temp
        }

        // 選擇入刀點
        Arr.prototype.median = function (left, right) {
            // 1.求出中間的位置,這里必須用向下取整,不然會造成無限遞回
            var center = Math.floor((left + right) / 2)

            // 2.通過交換,把中位數放到中間的位置
            if (this.array[left] > this.array[center]) {
                this.swap(left, center)
            }
            if (this.array[center] > this.array[right]) {
                this.swap(center, right)
            }
            if (this.array[left] > this.array[center]) {
                this.swap(left, center)
            }

            // 3. 將center移動到right - 1的位置,這個時候能得出center一定比right位置的數小
            //再之后就是left和center之間的數依次和center比大小，然后最后把center放到一個正好的位置
            //左面的數全部比它小，右面的全部比它大
            this.swap(center, right - 1)

            // 4.回傳入刀點
            return this.array[right - 1]
        }

        // 快速排序實作
        Arr.prototype.quick = function () {
            //第一次呼叫quickSort,并把實參傳過去,之后就是quickSort遞回了
            this.quickSort(0, this.array.length - 1)
        }

        Arr.prototype.quickSort = function (left, right) {
            // 0.遞回結束條件
            if (left >= right) return

            // 1.獲取樞紐
            var pivot = this.median(left, right)

            // 2.開始進行交換
            var i = left
            var j = right - 1
            while (true) { //代表一個死回圈
                while (this.array[++i] < pivot) { }
                while (this.array[--j] > pivot) { }
                if (i < j) {
                    this.swap(i, j)
                } else {
                    break //不滿足if條件，此時中斷死回圈
                }
            }

            // 3.將樞紐放在正確的位置,因為前面已經排好,所以有限制條件，不然會造成重復排序
           if(i<right-1){
            this.swap(i, right - 1)}

            // 4.遞回呼叫左邊部分
            
            this.quickSort(left, i - 1)

            // 4.遞回呼叫右邊部分
            this.quickSort(i + 1, right)              
        }
    }

    // 初始化資料項
    var list = new Arr()
    list.insert(7)
    list.insert(11)
    list.insert(70)
    list.insert(10)
    list.insert(6)
    list.insert(5)
    list.insert(101)
    list.insert(99)
    list.insert(50)
    list.insert(100)
    alert(list) // 7,11,70,10,6,5,101,99,50,100

    
    list.quick()// 測驗快速排序
    alert(list)//5,6,7,10,11,50,70,99,100,101
</script>

多畫畫圖比較容易理清

關鍵詞:分而治之，遞回，中位數，冒泡排序升級版

注意:快速排序不是一種穩定的演算法，何為穩定，簡單來說就是兩個大小一樣的數，多次用同一排序演算法，兩個數字出現的位置是否一樣
快速排序有多種寫法，但是核心思想都是分而治之

標籤：其他

上一篇：請教：關于TCP的快速重傳

下一篇：如何理解尾遞回