經典排序算法

排序算法

冒泡排序

冒泡排序（Bubble Sort）的基本思路是：每一次從待排序的資料元素中，依次比較相鄰的兩個元素，将比較小的數放在前面，比較大的數放在後面，直到比較到最後兩個數。重複步驟，直到待排序的資料元素全部排完。

這個算法的名字又來是因為越大的元素會經由交換慢慢“浮”到數列的頂端（升序或降序排列），就如同碳酸飲料重的氣泡會最終會上浮到頂端一樣，故名“冒泡排序”。

const bubbleSort = （arr） => {
        for (let i = arr.length - 1; i > 0; i--) {
            for (let j = 0; j < i; j++) {
                if (arr[i] > arr[i + 1]) {
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                }
            }
        }
        return arr;
    }

           

• 時間複雜度：O（n^2）
• 空間複雜度：O（1）

選擇排序

選擇排序（selection sort）的基本思路是：每一次從待排序的資料元素中選出最小（或最大）的一個元素，把這個元素存放在序列的起始位置，直到待排序的資料元素全部排完。

選擇排序是不穩定的排序算法

const selectSort = (arr) => {
        for (let i = 0; i < arr.length; i++) {\
            const minIndex = 0;
            for (let j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            } 
            [arr[mindex], arr[i]] = [arr[i], arr[minIndex]];
        }
        return arr;
    }
           

快速排序

快速排序（QuickSort）又稱為交換排序，簡稱快排。基本思路是：每一次從待排序的資料元素中找一個基準點，再建立兩個數組left與right。left存儲大于（或等于）基準點數，right存儲小于（或等于）基準點的資料元素，利用遞歸依次繼續比較left于right。

const quickSort = (arr) => {
        if (arr.length <= 1) return arr;
        let left = [];
        let right = [];
        const num = Math.floor(arr.length / 2);
        const numValue = arr.splice(num, 1)[0];
        for (let i = 0; i < arr.length; i++) {
            if(arr[i] > numValue) {
                right.push(arr[i])
            } else {
                arr.push(arr[i])
            }
        }
        return [...quickSort(left), ...quickSosrt(right)]
    }
           

插入排序

插入排序（insertion sort）。基本思路是：通過建構有序序列（把第一個元素預設是已排序的元素），對于未排序的資料，在已排序序列中從後向前掃描，找到相應位置并插入。

插入排序在實作上，通常采用in-place排序（即隻需用到O（1）的額外空間的排序）。因而在從後向前掃描過程中，需要反複把已排序元素逐漸向後挪位，為最新元素提供插入空間。

const insertSort = (arr) => {
        for (let i = 1; i < arr.length; i++) {
            const preIndex = i - 1;
            const current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[PreIndex];
                preIndex--;
            }
            arr[preIndex + 1] =current 
        }
        return arr;
    }