學(xué)習(xí)排序算法的目的

1. 解決實(shí)際問題：排序算法是計(jì)算機(jī)科學(xué)中的基礎(chǔ)算法之一，幾乎在任何領(lǐng)域的軟件開發(fā)中都會(huì)遇到排序的需求。了解各種排序算法能夠幫助程序員解決實(shí)際問題，提供高效的數(shù)據(jù)處理和查詢功能。
2. 性能優(yōu)化：排序算法的選擇會(huì)對(duì)程序的性能產(chǎn)生直接影響。不同的排序算法在時(shí)間復(fù)雜度和空間復(fù)雜度上有不同的特點(diǎn)，了解不同排序算法的性能特點(diǎn)可以幫助程序員選擇最適合的算法，優(yōu)化程序的執(zhí)行效率。
3. 數(shù)據(jù)結(jié)構(gòu)：排序算法與數(shù)據(jù)結(jié)構(gòu)密切相關(guān)。對(duì)于不同類型的數(shù)據(jù)結(jié)構(gòu)，選擇合適的排序算法能夠充分發(fā)揮數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)，提高數(shù)據(jù)處理的效率。例如，對(duì)于鏈表結(jié)構(gòu)，插入排序可能更加適用，而對(duì)于數(shù)組結(jié)構(gòu)，快速排序或堆排序可能更高效。
4. 算法設(shè)計(jì)和分析：排序算法是算法設(shè)計(jì)和分析的經(jīng)典案例之一。通過學(xué)習(xí)排序算法，程序員可以培養(yǎng)良好的算法設(shè)計(jì)思維，學(xué)會(huì)分析和評(píng)估算法的性能，提高解決問題的能力。
5. 面試準(zhǔn)備：排序算法是面試中常見的考點(diǎn)之一。許多技術(shù)面試會(huì)涉及排序算法的實(shí)現(xiàn)和性能分析，熟悉排序算法可以幫助程序員在面試中更好地展示自己的技術(shù)能力。

常見的十大排序算法分類

1. 比較類排序：通過比較來決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此也稱為非線性時(shí)間比較類排序。
2. 非比較類排序：不通過比較來決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線性時(shí)間運(yùn)行，因此也稱為線性時(shí)間非比較類排序。

冒泡排序（Bubble Sort）

重復(fù)地遍歷要排序的列表，依次比較相鄰的兩個(gè)元素，并按照升序或降序交換它們的位置，直到整個(gè)列表排序完成。

實(shí)現(xiàn)原理

1. 從列表的第一個(gè)元素開始，將其與下一個(gè)元素比較，如果順序錯(cuò)誤（升序時(shí)當(dāng)前元素大于下一個(gè)元素，降序時(shí)當(dāng)前元素小于下一個(gè)元素），則交換它們的位置。
2. 繼續(xù)比較下一個(gè)相鄰元素，重復(fù)上述步驟，直到遍歷到列表的最后一個(gè)元素。
3. 重復(fù)步驟1和2，直到?jīng)]有任何元素需要交換位置，即列表已排序完成。

冒泡.gif

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相鄰元素兩兩對(duì)比
                var temp = arr[j+1];        // 元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

使用場(chǎng)景

冒泡排序是一種簡單但效率較低的排序算法，適用于小規(guī)模的列表；在大規(guī)模數(shù)據(jù)的情況下，其他高效的排序算法（如快速排序、歸并排序）更常被使用。
列表幾乎已經(jīng)有序時(shí)，冒泡排序可能會(huì)比其他算法更加高效。

快速排序（Quick Sort）

快速排序（Quick Sort）是一種高效的排序算法，它的原理是通過選擇一個(gè)基準(zhǔn)元素，將數(shù)組分割成較小和較大兩個(gè)子數(shù)組，然后對(duì)子數(shù)組進(jìn)行遞歸排序，直到整個(gè)數(shù)組有序。

實(shí)現(xiàn)原理

1. 選擇一個(gè)基準(zhǔn)元素（通常是數(shù)組中的中間元素）。
2. 將數(shù)組分成兩個(gè)子數(shù)組，比基準(zhǔn)元素小的放在左邊，比基準(zhǔn)元素大的放在右邊。
3. 遞歸地對(duì)左右子數(shù)組進(jìn)行快速排序。
4. 合并左子數(shù)組、基準(zhǔn)元素和右子數(shù)組，得到最終有序的數(shù)組。

  function quickSort(arr) {
    // 檢查數(shù)組元素的個(gè)數(shù)，如果小于等于1，就返回
    if (arr.length <= 1) return arr;
    // 基準(zhǔn)索引
    let pivotIndex = Math.floor(arr.length / 2);
    // 找到基準(zhǔn)，并且把基準(zhǔn)從原數(shù)組中刪除
    let pivot = arr.splice(pivotIndex, 1)[0];
    // 定義左右數(shù)組
    let left = [];
    let right = [];
    // 把基準(zhǔn)小的放在left數(shù)組中，大的放在right中
    arr.forEach(ele => {
      if (ele < pivot) {
        left.push(ele);
      } else {
        right.push(ele);
      }
    });
    return quickSort(left).concat([pivot], quickSort(right));
  }
console.log("快速排序",quickSort([49, 38, 65, 97, 76, 13, 27, 49]));

使用場(chǎng)景

適用于大規(guī)模數(shù)據(jù)的排序，它在實(shí)際應(yīng)用中被廣泛使用
許多編程語言和庫中的默認(rèn)排序算法，如JavaScript中的Array.prototype.sort()方法就使用了快速排序算法。

選擇排序（Selection Sort）

在一組數(shù)據(jù)中，首先找到最?。ɑ蜃畲螅┑臄?shù)據(jù)并放在最前面（數(shù)據(jù)的后面），以此類推，直到全部數(shù)據(jù)排序完畢。

實(shí)現(xiàn)原理

1. 每一輪從待排序的元素中選擇最小（或最大）的元素，將其與序列中的第一個(gè)元素交換位置
2. 再從剩下的元素中選擇最小（或最大）的元素，與序列中的第二個(gè)元素交換位置
3. 以此類推，直到整個(gè)序列有序

function selectionSort(arr) {
  let len = arr.length;
  let minIndex, temp;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < len; j++) {
      console.log("循環(huán)找最小的值", arr[j], arr[minIndex], minIndex);
      if (arr[j] < arr[minIndex]) {
        // 尋找最小的數(shù)
        minIndex = j; // 將最小數(shù)的索引保存
      }
    }
    // 將當(dāng)前遍歷的項(xiàng)和查找到的最小項(xiàng)交換位置
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

// 使用
let arr = [3, 1, 5, 7, 2, 4, 6, 8];
console.log(selectionSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8]

使用場(chǎng)景

由于選擇排序的時(shí)間復(fù)雜度較高，對(duì)于大規(guī)模數(shù)據(jù)的排序效率較低，因此在實(shí)際應(yīng)用中并不常用。更適合在小規(guī)?；虿糠钟行虻臄?shù)組中使用。

插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法

實(shí)現(xiàn)原理

通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入

1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序；
2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置；
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
5. 將新元素插入到該位置后；

6. 重復(fù)步驟2~5。

   
   
   插入排序.gif

function insertionSort(arr) {
    // current 是我們需要插入的當(dāng)前元素。preIndex 是我們正在與 current 進(jìn)行比較的元素的位置。
    let preIndex, current;
    for (let i = 1; i < arr.length; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
          // 將當(dāng)前滿足的條件的值和當(dāng)前比較的
          // 當(dāng) preIndex 存在且其對(duì)應(yīng)元素值大于 current 時(shí)，我們一直將這些元素往后移。
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = insertionSort(array);
console.log(sortedArray); // 輸出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

使用場(chǎng)景

插入排序適用于小規(guī)?；虿糠钟行虻臄?shù)組。當(dāng)待排序數(shù)組基本有序時(shí)，插入排序的效率較高。它比冒泡排序和選擇排序的性能稍好，且實(shí)現(xiàn)簡單，適用于對(duì)于數(shù)據(jù)量較小的排序任務(wù)。插入排序也可以用作其他高級(jí)排序算法的子過程，例如快速排序的優(yōu)化版本中的小數(shù)組排序。

希爾排序（Shell Sort）

希爾排序（Shell Sort），也稱作縮小增量排序，是插入排序的一種改進(jìn)版本。它通過將待排序數(shù)組分成多個(gè)子數(shù)組，并對(duì)每個(gè)子數(shù)組進(jìn)行插入排序，逐步減小子數(shù)組的大小，最終完成整個(gè)數(shù)組的排序。

實(shí)現(xiàn)原理

1. 選擇一個(gè)初始增量（通常為數(shù)組長度的一半）。
2. 將數(shù)組分成多個(gè)子數(shù)組，每個(gè)子數(shù)組相隔增量個(gè)位置。
3. 對(duì)每個(gè)子數(shù)組進(jìn)行插入排序，將子數(shù)組中的元素插入到正確的位置。

4. 逐步減小增量，重復(fù)上述步驟，直到增量為1，完成整個(gè)數(shù)組的排序。

   
   
   希爾排序.gif
   
   
   希爾排序.gif

 function shellSort(arr) {
    let len = arr.length,
    temp,
    gap = Math.floor(len / 2); // 初始增量
    while (gap > 0) {
        // 對(duì)每個(gè)子數(shù)組進(jìn)行插入排序
      for (let i = gap; i < len; i++) {
        temp = arr[i];
        let preIndex = i - gap;
        // 在子數(shù)組中進(jìn)行插入排序
        while (preIndex >= 0 && arr[preIndex] > temp) {
          arr[preIndex + gap] = arr[preIndex];
          preIndex -= gap;
        }
        arr[preIndex + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}          
// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = shellSort(array);
console.log(sortedArray); // 輸出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

使用場(chǎng)景

希爾排序適用于中等大小的數(shù)組排序，特別適用于需要在性能和簡單實(shí)現(xiàn)之間取得平衡的場(chǎng)景。它在實(shí)際應(yīng)用中常用于對(duì)大型數(shù)據(jù)集進(jìn)行初步排序的預(yù)處理步驟，為后續(xù)排序算法提供更好的初始狀態(tài)。希爾排序相對(duì)于其他簡單的初級(jí)排序算法具有更好的性能，但仍然不如快速排序、歸并排序等高級(jí)排序算法。

歸并排序（Merge Sort）

歸并排序（Merge Sort）是一種高效的排序算法，它的原理是將待排序的數(shù)組遞歸地分成兩個(gè)子數(shù)組，分別對(duì)子數(shù)組進(jìn)行排序，然后將兩個(gè)排序好的子數(shù)組合并成一個(gè)有序的數(shù)組。

實(shí)現(xiàn)原理

1. 將待排序數(shù)組分割成較小的子數(shù)組，直到每個(gè)子數(shù)組只包含一個(gè)元素（遞歸基線條件）。
2. 遞歸地將子數(shù)組排序，直到得到排好序的子數(shù)組。

3. 合并排好序的子數(shù)組，得到最終有序的數(shù)組。

   
   
   歸并排序.gif

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr; // 基線條件：數(shù)組為空或只有一個(gè)元素，直接返回
  }

  const mid = Math.floor(arr.length / 2); // 找到數(shù)組的中間位置
  const left = arr.slice(0, mid); // 分割為左子數(shù)組
  const right = arr.slice(mid); // 分割為右子數(shù)組
    console.log("分組",left,right)
  return merge(mergeSort(left), mergeSort(right)); // 遞歸地對(duì)左右子數(shù)組進(jìn)行歸并排序并合并
}

// 合并兩個(gè)有序數(shù)組
function merge(left, right) {
  console.log("獲取的數(shù)組",left,right)
  const merged = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      merged.push(left[leftIndex]); // 左子數(shù)組元素較小，放入合并數(shù)組
      leftIndex++;
    } else {
      merged.push(right[rightIndex]); // 右子數(shù)組元素較小，放入合并數(shù)組
      rightIndex++;
    }
  }

  // 將剩余的元素放入合并數(shù)組
  return merged.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 10, 5, 6, 2, 3];
const sortedArray = mergeSort(array);
console.log(sortedArray); // 輸出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

使用場(chǎng)景

歸并排序適用于大規(guī)模數(shù)據(jù)的排序，特別適用于外部排序，即排序數(shù)據(jù)量大到無法全部加載到內(nèi)存中的場(chǎng)景。歸并排序的優(yōu)勢(shì)在于排序速度較快且穩(wěn)定，對(duì)于處理大規(guī)模亂序數(shù)據(jù)或需要保持相同元素相對(duì)順序的排序任務(wù)非常有效。

堆排序（Heap Sort）

堆排序（Heap Sort）是一種高效的排序算法，它利用堆這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序。堆是一種特殊的完全二叉樹，它滿足堆的性質(zhì)：對(duì)于每個(gè)節(jié)點(diǎn)，其值大于（或小于）其子節(jié)點(diǎn)的值。

實(shí)現(xiàn)原理

1. 構(gòu)建最大堆：從最后一個(gè)非葉子節(jié)點(diǎn)開始，依次將數(shù)組轉(zhuǎn)換為最大堆，保證每個(gè)節(jié)點(diǎn)的值大于或等于其子節(jié)點(diǎn)的值。
2. 依次取出堆頂元素：將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，將剩余元素重新構(gòu)建為最大堆。
3. 重復(fù)上述步驟，直到堆中的所有元素都被取出并排好序。

function heapSort(arr) {
  const len = arr.length;

  // 構(gòu)建最大堆
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    console.log("sss===構(gòu)建堆循環(huán)前" + i, arr, len, i);
    heapify(arr, len, i);
    console.log("sss===構(gòu)建堆循環(huán)后" + i, arr, len, i);
  }

  // 依次取出堆頂元素并調(diào)整堆
  for (let i = len - 1; i > 0; i--) {
    console.log("sss===調(diào)整前" + i, arr, i);
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 將堆頂元素與最后一個(gè)元素交換
    console.log("sss===調(diào)整交換中" + i, arr, i);
    heapify(arr, i, 0); // 調(diào)整堆
    console.log("sss===調(diào)整后" + i, arr, i);
  }

  return arr;
}

function heapify(arr, n, i) {
  let largest = i; // 當(dāng)前節(jié)點(diǎn)索引
  const left = 2 * i + 1; // 左子節(jié)點(diǎn)索引
  const right = 2 * i + 2; // 右子節(jié)點(diǎn)索引

  // 找出最大值的索引
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  // 如果最大值的索引不是當(dāng)前節(jié)點(diǎn)，則交換節(jié)點(diǎn)并繼續(xù)調(diào)整堆
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    console.log("sss===內(nèi)部調(diào)用前" + largest, arr, largest);
    heapify(arr, n, largest);
    console.log("sss===內(nèi)部調(diào)用后" + largest, arr, largest);
  }
}

// 示例用法
const array = [4, 2, 2, 8, 3, 3, 5, 6, 2, 3，10];
const sortedArray = heapSort(array);
console.log(sortedArray); // 輸出: [2, 2, 2, 3, 3, 3, 4, 5, 6, 8, 10]

使用場(chǎng)景

堆排序適用于大規(guī)模數(shù)據(jù)的排序，尤其適用于需要找出最大或最小的K個(gè)元素的問題。由于堆排序的構(gòu)建最大堆操作具有線性時(shí)間復(fù)雜度，因此可以在一些特定場(chǎng)景中提供較好的性能，如優(yōu)先隊(duì)列的實(shí)現(xiàn)、Top K 問題等。