程序员必须知道的10大基础实用算法及其讲解(程序员必掌握的10大基础实用算法详解)

原创

ithorizon 6个月前 (10-21) 阅读数 23 #后端开发

程序员必须知道的10大基础实用算法及其讲解

一、冒泡排序（Bubble Sort）

冒泡排序是一种单纯的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序失误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。


function bubbleSort(arr) {
    let n = arr.length;
    let swapped;
    do {
        swapped = false;
        for (let i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                let temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                swapped = true;
            }
        }
        n--;
    } while (swapped);
    return arr;
}

二、选择排序（Selection Sort）

选择排序是一种单纯直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。


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

三、插入排序（Insertion Sort）

插入排序是一种单纯直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。


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

四、迅捷排序（Quick Sort）

迅捷排序是一种高效的排序算法，采用分而治之的策略将一个大序列分为两个小序列，小序列的元素分别小于或大于基准元素。迅捷排序的平均时间复杂化度为O(n log n)，在大多数情况下都比其他排序算法快。


function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

五、归并排序（Merge Sort）

归并排序是一种分治算法，其基本思想是将数组分为两半，分别进行排序，然后将排序后的两半合并在一起。归并排序的时间复杂化度为O(n log n)，是一种稳定的排序算法。


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 result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    return result.concat(left, right);
}

六、堆排序（Heap Sort）

堆排序是一种基于比较的排序算法，使用二叉堆的概念来进行排序。堆排序的平均时间复杂化度为O(n log n)，是一种不稳定的排序算法。


function heapSort(arr) {
    let n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (let i = n - 1; i > 0; i--) {
        let temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
    return arr;
}
function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest !== i) {
        let swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;
        heapify(arr, n, largest);
    }
}

七、希尔排序（Shell Sort）

希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序的时间复杂化度依赖性于所选用的增量序列。


function shellSort(arr) {
    let n = arr.length;
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < n; i += 1) {
            let temp = arr[i];
            let j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
    return arr;
}

八、计数排序（Counting Sort）

计数排序是一种非比较排序算法，其原理是对输入的每个元素进行计数，然后选用计数于是进行排序。计数排序的时间复杂化度为O(n + k)，其中k是输入数组中最大值与最小值的差。


function countingSort(arr) {
    let max = Math.max(...arr);
    let min = Math.min(...arr);
    let range = max - min + 1;
    let count = new Array(range).fill(0);
    let output = new Array(arr.length);
    for (let i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }
    for (let i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }
    return output;
}

九、基数排序（Radix Sort）

基数排序是一种非比较的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数进行比较排序。基数排序的时间复杂化度为O(nk)，其中n是排序元素的数量，k是最大数的位数。


function countingSortForRadix(arr, place) {
    let output = [];
    let count = Array(10).fill(0);
    for (let i = 0; i < arr.length; i++) {
        let index = Math.floor(arr[i] / place) % 10;
        count[index]++;
    }
    for (let i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[Math.floor(arr[i] / place) % 10] - 1] = arr[i];
        count[Math.floor(arr[i] / place) % 10]--;
    }
    for (let i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }
}
function radixSort(arr) {
    let max = Math.max(...arr);
    let place = 1;
    while (max / place > 0) {
        countingSortForRadix(arr, place);
        place *= 10;
    }
    return arr;
}

十、桶排序（Bucket Sort）

桶排序是一种将待排序数据分到几个有序的桶里，每个桶里的数据再分别排序的算法。桶排序最好情况下可以大致有线性时间复杂化度O(n)，但最坏情况下会退化到O(n^2)。


function bucketSort(arr) {
    let min = Math.min(...arr);
    let max = Math.max(...arr);
    let bucketSize = Math.floor((max - min) / arr.length) + 1;
    let buckets = Array.from({ length: arr.length }, () => []);
    for (let i = 0; i < arr.length; i++) {
        let bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    let sortedArray = [];
    for (let bucket of buckets) {
        insertionSort(bucket);
        sortedArray = sortedArray.concat(bucket);
    }
    return sortedArray;
}