欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

數(shù)據(jù)結(jié)構(gòu)中的各種排序方法小結(jié)(JS實(shí)現(xiàn))

 更新時(shí)間：2016年07月23日 10:16:04   投稿：jingxian  
下面小編就為大家?guī)硪黄獢?shù)據(jù)結(jié)構(gòu)中的各種排序方法小結(jié)(JS實(shí)現(xiàn))。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

新技術(shù)一直在不斷變化，掌握一些基礎(chǔ)是未來學(xué)習(xí)不斷更新的技術(shù)的堅(jiān)實(shí)基礎(chǔ)。近來閑來無事,為了溫習(xí)一下從前學(xué)的數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)結(jié)構(gòu)中的排序算法用JS實(shí)現(xiàn)了一遍，并在本文末尾處嵌入了DEMO。

簡(jiǎn)單排序

冒泡排序

冒泡排序是最簡(jiǎn)單排序算法,時(shí)間復(fù)雜度為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;
          }

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

直接插入排序

直接插入排序也屬于簡(jiǎn)單排序算法,時(shí)間復(fù)雜度也為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
        /* 輸出結(jié)果 */
        document.write("第? + i + "遍排序的結(jié)果是:")
        for (var n = 0; n < array.length; n++) {
          document.write(array[n] + ",");
        }

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

      }
    }

選擇排序

選擇排序也屬于簡(jiǎn)單排序算法，時(shí)間復(fù)雜度也為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;
        }
        /* 輸出結(jié)果 */
        document.write("第 + i + "遍排序的結(jié)果是:")
        for (var n = 0; n < array.length; n++) {
          document.write(array[n] + ",");
        }

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

      }
    }

復(fù)雜排序

希爾排序

希爾排序是插入排序的升級(jí)，1959年希爾通過將簡(jiǎn)單排序中兩兩比較改為設(shè)置步長(zhǎng)跳躍式比較而突破了n的平方的時(shí)間復(fù)雜度,希爾排序根據(jù)步長(zhǎng)的不同時(shí)間復(fù)雜度由最好的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;
            /* 輸出結(jié)果 */
            count++;
            document.write("<br />第 + count + "遍排序的結(jié)果是:")
            for (var n = 0; n < array.length; n++) {
              document.write(array[n] + ",");
            }
            /* 輸出結(jié)果結(jié)束 */
          }
        }
      }
      while (increment > 1)

    }

堆排序

堆排序是選擇排序的升級(jí)，通過不斷構(gòu)建大頂堆或者小頂堆來選擇最大或者最小的值放入隊(duì)列前端進(jìn)行排序，堆排序任何情況下的時(shí)間復(fù)雜度都為nlogn，代碼如下：

function heapSort(array) {
      var temp;
      var i;
      for (i = Math.floor(array.length / 2); i >= 0; i--) {
        heapAdjust(array, i, array.length - 1); //將數(shù)組array構(gòu)建成一個(gè)大頂堆
      }
      for (i = array.length - 1; i >= 0; i--) {
        /*把根節(jié)點(diǎn)交換出去*/
        temp = array[i];
        array[i] = array[0];
        array[0] = temp;

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

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

    }

歸并排序

歸并排序是復(fù)雜排序中唯一一個(gè)穩(wěn)定排序，通過將待排序數(shù)組進(jìn)行分拆再合并來進(jìn)行排序，歸并排序時(shí)間復(fù)雜度為n的平方，代碼如下：

//source源數(shù)組    //dest目標(biāo)數(shù)組
    //s起始下標(biāo)
    //t目標(biāo)下標(biāo)
    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);
        /* 輸出結(jié)果 */
        document.write("<br />第 + ++count + "遍排序的結(jié)果是:")
        for (var n = 0; n < dest.length; n++) {
          document.write(array[n] + ",");
        }
        /* 輸出結(jié)果結(jié)束 */
      }

    }
    
    //將兩個(gè)數(shù)組按照從小到大的順序融合
    //source原數(shù)組
    //dest排序后的數(shù)組
    //s第一個(gè)下標(biāo)
    //m第二個(gè)數(shù)組下標(biāo)
    //總長(zhǎng)度
    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++];
        }
      }
      
        //將剩余排不完的有序數(shù)組加入到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];
          }
        
      }
    }

快速排序

快速排序是目前已知的速度最快的排序，時(shí)間復(fù)雜度為nlogn,代碼如下：

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

        var keypoint = QuickSortHelp(array, low, high);
        count++;
        document.write("<br />第臺(tái)? + count + "遍括?排?序ò的?結(jié)á果?是?:")
        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;
    }

以上這篇數(shù)據(jù)結(jié)構(gòu)中的各種排序方法小結(jié)(JS實(shí)現(xiàn))就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

相關(guān)文章

最新評(píng)論