數據結構與算法（排序） --javascript語言描述

Dongjie_Liu 發布于2019-08-26 11:44 / 2090人閱讀

摘要：最差情況輸入數組按降序排列。平均情況穩定性穩定希爾排序排序法是對相鄰指定距離稱為增量的元素進行比較，并不斷把增量縮小至，完成排序。若將兩個有序表合并成一個有序表，稱為二路歸并。

冒泡排序

從數組中第一個數開始，依次遍歷數組中的每一個數，通過相鄰比較交換，每一輪循環下來找出剩余未排序數的中的最大數并”冒泡”至數列的頂端。

function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1 ; i++) {
    for (var j = 0; j < arr.length - i - 1 ; j++) {
      if (arr[j] > arr[j+1]) {        //相鄰元素兩兩對比
          let temp = arr[j+1];        //元素交換
          arr[j+1] = arr[j];
          arr[j] = temp;
      }
    }
  }
  return arr;
}
console.log(bubbleSort([72,54,58,30,31,78,2,77,82,72]))

最佳情況：輸入數組按升序排列。 T(n) = O(n)
最差情況：輸入數組按降序排列。 T(n) = O(n2)
平均情況：T(n) = O(n2)
穩定性：穩定

選擇排序

從所有記錄中選出最小的一個數據元素與第一個位置的記錄交換；然后在剩下的記錄當中再找最小的與第二個位置的記錄交換，循環到只剩下最后一個數據元素為止。

function selectionSort(arr) {
  let minIndex,temp;
  for (let i = 0; i < arr.length-1; i++) {
    minIndex = i;
    for (let j = i+1; j < arr.length; j++) {
      if(arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    temp = arr[i];
    arr[i]=arr[minIndex];
    arr[minIndex]=temp;
  }
  return arr;
}

console.log(selectionSort([72,54,58,30,31,78,2,77,82,72]))

最佳情況：T(n) = O(n2)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(n2)
穩定性：不穩定

插入排序

從待排序的n個記錄中的第二個記錄開始，依次與前面的記錄比較并尋找插入的位置，每次外循環結束后，將當前的數插入到合適的位置。

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j>=0 && arr[j] > key) {
      arr[j+1] = arr[j];
      j--;
    }
    arr[j+1] = key;
  }
  return arr;
}

console.log(insertionSort([6,10,0,6,5,8,7,4,2,7]))

最佳情況：輸入數組按升序排列。T(n) = O(n)
最壞情況：輸入數組按降序排列。T(n) = O(n2)
平均情況：T(n) = O(n2)
穩定性：穩定

希爾排序

Shell排序法是對相鄰指定距離(稱為增量)的元素進行比較，并不斷把增量縮小至1，完成排序。

function shellSort(arr) {
　　var len = arr.length,
　　temp,
　　gap = 1;
　　while(gap < len/5) { //動態定義間隔序列
　　　　gap =gap*5+1;
　　}
　　for (gap; gap > 0; gap = Math.floor(gap/5)) {
　　　　for (var i = gap; i < len; i++) {
　　　　　　temp = arr[i];
　　　　　　for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
　　　　　　　　arr[j+gap] = arr[j];
　　　　　　}
　　　　　　arr[j+gap] = temp;
　　　　}
　　}
　　return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));

最佳情況：T(n) = O(nlog2 n)
最壞情況：T(n) = O(nlog2 n)
平均情況：T(n) =O(nlog n)
穩定性：不穩定

歸并排序

歸并排序是分治法（Divide and Conquer）的一個典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

function mergeSort(arr) {
  if(arr.length < 2) {
    return arr;
  }
  let middle = Math.floor(arr.length/2);
  let left = arr.slice(0,middle);
  let right = arr.slice(middle);
  return merge(mergeSort(left),mergeSort(right));
}

function  merge(left,right) {
  let res = [];
  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      res.push(left.shift());
    }
    else {
      res.push(right.shift());
    }
  }
  while(left.length) {
    res.push(left.shift());
  }
  while(right.length) {
    res.push(right.shift());
  }
  return res;
}

let arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

最佳情況：T(n) = O(n)
最差情況：T(n) = O(nlogn)
平均情況：T(n) = O(nlogn)
穩定性：穩定

快速排序

1.從待排序的n個記錄中任意選取一個記錄（通常選取第一個記錄）為分區標準;
2.把所有小于該排序列的記錄移動到左邊，把所有大于該排序碼的記錄移動到右邊，中間放所選記錄，稱之為第一趟排序；
3.然后對前后兩個子序列分別重復上述過程，直到所有記錄都排好序。

方法一：

function quickSort(arr,left,right) {
  let i = left;
  let j = right;
  let temp = 0;
  if(i < j) {  //待排序的元素至少有兩個的情況
    temp = arr[i];  //待排序的第一個元素作為基準元素
    while(i != j) {    //從左右兩邊交替掃描，直到i = j
      while(j > i && arr[j] >= temp) {
        j --;  //從右往左掃描，找到第一個比基準元素小的元素
      }
      arr[i] = arr[j];  //找到這種元素arr[j]后與arr[i]交換
      while(i < j && arr[i] <= temp) {
        i ++;  //從左往右掃描，找到第一個比基準元素大的元素
      }
      arr[j] = arr[i];  //找到這種元素arr[i]后，與arr[j]交換
    }
    arr[i] = temp;  //基準元素歸位
    quickSort(arr,left,i-1);  //對基準元素左邊的元素進行遞歸排序
    quickSort(arr,i+1,right);  //對基準元素右邊的進行遞歸排序
  }
  return arr;
}

let arr = [5,7,1,8,4]
console.log(quickSort(arr,0,arr.length-1));

方法二：

function quickSort(arr) {
  if(arr.length <= 1) {
    return arr;
  }
  let middleIndex = Math.floor(arr.length/2);
  let middle = arr.splice(middleIndex,1)[0];//選取基準值 并從數組中刪除
  let left = [];  //小于middle的數組
  let right = [];  //大于middle的數組
  for (var i = 0; i < arr.length; i++) {
    if(arr[i] < middle) {
      left.push(arr[i]);
    }
    else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([middle],quickSort(right));
}
let arr = [5,7,1,8,4]
console.log(quickSort(arr));

最佳情況：T(n) = O(nlogn)
最差情況：T(n) = O(n2)
平均情況：T(n) = O(nlogn)
穩定性：不穩定

云服務器 GPU云服務器算法與數據結構數據結構與算法數據結構與算法教程數據結構與算法答案

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/107480.html

JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0
JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0
Java面試題：穩定和不穩定排序算法之間的區別-MergeSort與QuickSort

摘要：穩定與不穩定算法示例以下圖片解釋了穩定和不穩定的排序是如何工作的這就是穩定和不穩定排序算法之間的區別。穩定排序算法的一些常見示例是合并排序，插入排序和冒泡排序。 showImg(https://segmentfault.com/img/remote/1460000018913243); 來源 | 愿碼(ChainDesk.CN)內容編輯愿碼Slogan | 連接每個程序員的故事網...

wanghui 2019-08-16 16:46 評論0 收藏0
JavaScript 數據結構與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 評論0 收藏0
JavaScript 數據結構與算法之美 - 桶排序、計數排序、基數排序

摘要：之所以把計數排序桶排序基數排序放在一起比較，是因為它們的平均時間復雜度都為。動畫計數排序思想找出待排序的數組中最大和最小的元素。桶排序計數排序能派上用場嗎手機號碼有位，范圍太大，顯然不適合用這兩種排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言算法為王。想學好前端，先練好內功，只有內功深厚者...

Awbeci 2019-08-26 10:24 評論0 收藏0
JS數據結構與算法_排序和搜索算法

摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。上一篇：JS數據結構與算法_樹寫在前面這是《學習JavaScript數據結構與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

姘擱『 2019-08-23 16:26 評論0 收藏0