數據結構中的各種排序方法-JS實現

新技術一直在不斷變化,掌握一些基礎是未來學習不斷更新的技術的堅實基礎。近來閑來無事,為瞭溫習一下從前學的數據結構,將數據結構中的排序算法用JS實現瞭一遍,並在本文末尾處嵌入瞭DEMO。

 
簡單排序
冒泡排序
     冒泡排序是最簡單排序算法,時間復雜度為n的平方,代碼如下:

        function bubbleSort(array) {
            for (var i = 0; i < array.length; i++) {
                for (var j = array.length; j > 0; j–) {
                    if (array[j] < array[j – 1]) {
                        var temp = array[j – 1];
                        array[j – 1] = array[j];
                        array[j] = temp;
                    }

                }
                /* 輸出結果 */
                document.write("這是第 + (i + 1) + "次循環·,結果為:");
                for (var k = 0; k < array.length; k++) {
                    document.write(array[k] + ",");
                }
                document.write("<br />");
                /* 輸出結果結束 */
            }
        }
 

直接插入排序
    直接插入排序也屬於簡單排序算法,時間復雜度也為n的平方,但性能略好於冒泡排序,代碼如下:

        function insertSort(array) {
            var temp;
            for (var i = 1; i < array.length; i++) {
                var temp = array[i];
                for (var j = i; j > 0 && temp < array[j – 1]; j–) {
                    array[j] = array[j – 1];
                }
                array[j] = temp www.aiwalls.com
                /* 輸出結果 */
                document.write("第? + i + "遍排序的結果是:")
                for (var n = 0; n < array.length; n++) {
                    document.write(array[n] + ",");
                }

                document.write("<br />")
                /* 輸出結果結束 */

            }
        }

選擇排序
    選擇排序也屬於簡單排序算法,時間復雜度也為n的平方,性能同樣略微好於冒泡排序,代碼如下:

        function selectSort(array) {
            var min, temp; ;
            for (var i = 0; i < array.length; i++) {
                min = i;
                for (var j = i + 1; j < array.length; j++) {
                    if (array[min] > array[j])
                        min = j;
                }
                if (min != i) {
                    temp = array[i];
                    array[i] = array[min];
                    array[min] = temp;
                }
                /* 輸出結果 */
                document.write("第 + i + "遍排序的結果是:")
                for (var n = 0; n < array.length; n++) {
                    document.write(array[n] + ",");
                }

                document.write("<br />")
                /* 輸出結果結束 */

            }
        }

復雜排序
 

希爾排序
     希爾排序是插入排序的升級,1959年希爾通過將簡單排序中兩兩比較改為設置步長跳躍式比較而突破瞭n的平方的時間復雜度,希爾排序根據步長的不同時間復雜度由最好的nlogn到最壞的n的平方。代碼如下:

       function shallSort(array) {
           var increment = array.length;
           var i
           var temp; //暫存
           var count = 0;
           do {
               increment = Math.floor(increment / 3) + 1;
               for (i = increment; i < array.length; i++) {
                   if (array[i] < array[i – increment]) {
                       temp = array[i];
                       for (var j = i – increment; j > 0 && temp < array[j]; j -= increment) {

                           array[j + increment] = array[j];

                       }
                       array[j + increment] = temp;
                       /* 輸出結果 */
                       count++;
                       document.write("<br />第 + count + "遍排序的結果是:")
                       for (var n = 0; n < array.length; n++) {
                           document.write(array[n] + ",");
                       }
                       /* 輸出結果結束 */
                   }
               }
           }
           while (increment > 1)

       }

堆排序
      堆排序是選擇排序的升級,通過不斷構建大頂堆或者小頂堆來選擇最大或者最小的值放入隊列前端進行排序,堆排序任何情況下的時間復雜度都為n的平方,代碼如下:

        function heapSort(array) {
            var temp;
            var i;
            for (i = Math.floor(array.length / 2); i >= 0; i–) {
                heapAdjust(array, i, array.length – 1); //將數組array構建成一個大頂堆
            }
            for (i = array.length – 1; i >= 0; i–) {
                /*把根節點交換出去*/
                temp = array[i];
                array[i] = array[0];
                array[0] = temp;

                /*餘下的數組繼續構建成大頂堆*/
                heapAdjust(array, 0, i – 1);
                /* 輸出結果 */
                document.write("<br />第 + (array.length – i).toString() + "遍排序的結果是:")
                for (var n = 0; n < array.length; n++) {
                    document.write(array[n] + ",");
                }
                /* 輸出結果結束 */
            }
        }
        //要調整的子樹
        //start為數組開始下標
        //max是數組結束下標
        function heapAdjust(array, start, max) {
            var temp, j;
            temp = array[start];//temp是根節點的值
            for (j = 2 * start; j < max; j *= 2) {
                if (j < max && array[j] < array[j + 1]) {  //取得較大孩子的下標
                    ++j;

                }
                if (temp >= array[j])
                    break;
                array[start] = array[j];
                start = j;
            }
            array[start] = temp;

        }

歸並排序
     歸並排序是復雜排序中唯一一個穩定排序,通過將待排序數組進行分拆再合並來進行排序,歸並排序時間復雜度為n的平方,代碼如下:

        //source源數組        //dest目標數組
        //s起始下標
        //t目標下標
        function mSort(source, dest, s, t) {
            var m; //取中間值
            var dest2 = new Array();
            if (s == t) {
                dest[s] = source[s];
            
            }
            else {
                m = Math.floor((s + t) / 2);
                mSort(source, dest2, s, m);
                mSort(source, dest2, m+1 , t);
                merge(dest2, dest, s, m, t);
                /* 輸出結果 */
                document.write("<br />第 + ++count + "遍排序的結果是:")
                for (var n = 0; n < dest.length; n++) {
                    document.write(array[n] + ",");
                }
                /* 輸出結果結束 */
            }

        }
       
        //將兩個數組按照從小到大的順序融合
        //source原數組
        //dest排序後的數組
        //s第一個下標
        //m第二個數組下標
        //總長度
        function merge(source, dest, s, m, n) {
            for (var j = m+1, k = s; j <= n && s <= m; k++) {
                if (source[s] < source[j]) {
                    dest[k] = source[s++];
                }
                else {
                    dest[k] = source[j++];
                }
            }
          
                //將剩餘排不完的有序數組加入到dest的末端
                if (s <= m) {
                    for (var l = 0; l <= m – s; l++) {
                        dest[k + l] = source[s+l];
                    }
                }
                if (j <= n) {
                    for (var l = 0; l <= n – j; l++) {
                        dest[k + l] = source[j+l];
                    }
               
            }
        }

快速排序
     快速排序是目前已知的速度最快的排序,時間復雜度為nlogn,代碼如下:

        var count = 0;
        function quickSort(array, low, high) {
            var temp;
           
            if (low < high) {

                var keypoint = QuickSortHelp(array, low, high);
                count++;
                document.write("<br />第臺? + count + "遍括?排?序ò的?結á果?是?:")
                for (var l = 0; l < array.length; l++) {
                    document.write(array[l] + ",");
                }
                quickSort(array, low, keypoint – 1);
                quickSort(array, keypoint + 1, high);
               

                }
        }
        function QuickSortHelp(array, low, high) {
            while (low < high) {

                while (low < high && array[low] <= array[high]) {
                    high–;
                }
                temp = array[low];
                array[low] = array[high];
                array[high] = temp;
                while (low < high && array[low] <= array[high]) {
                    low++
                }
                temp = array[low];
                array[low] = array[high];
                array[high] = temp;

            }
            return low;
        }

摘自 www.cnblogs.com/CareySon

發佈留言