重启数据结构与算法6

[Ray-56]

重启数据结构与算法6

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

1. 重启数据结构与算法1
2. 重启数据结构与算法2
3. 重启数据结构与算法3
4. 重启数据结构与算法4
5. 重启数据结构与算法5
6. 重启数据结构与算法6

排序算法

排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。

常见排序算法分类图：

常见排序算法时间复杂度图：

冒泡排序 BubbleSort

冒泡排序（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

• 每趟可以确定最大值放在最后
• 当这趟没有进行冒泡，则说明以排好序，终止循环

function bubbleSort(arr: number[]) {
    let flag = false; // 加入条件优化
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (!flag) break;
    }
}

选择排序 SelectionSort

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

function selectSort(arr: number[]) {
    for (let i = 0; i < arr.length; i++) {
        let min = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        if (min != i) {
            const temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
}

插入排序 InsertionSort

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到{\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

思路，将需要排序的数组分为两部分，前部分为已排序的，后面为乱序
每次从乱序的第一位中取出，判断找出插入到已排序的位置，然后插入

function insertSort(arr: number[]) {
    for (let i = 1; i < arr.length; i++) {
        let insertIndex = i;
        // insertIndex > 0 边界判断
        // arr[i] < arr[insertIndex] 需要移位条件
        while (insertIndex > 0 && arr[i] < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex]; // 将已排好序的，位置向后移动一位，给要插入的留出位置
            insertIndex--;
        }
        if (insertIndex !== i) { // 如果是相等的说明当前数据不需要插入
            arr[insertIndex] = arr[i];
        }
    }
}

希尔排序 ShellSort

希尔排序（Shellsort），也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

// 交换法
function shellSort(arr: number[]) {
    const len = arr.length;
    // 步长遍历
    for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < len; i++) {
            for (let j = i - gap; j >= 0; j -= gap) {
                if (arr[j] > arr[j + gap]) {
                    const temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
    }
}

// 移位法
function shellSort1(arr: number[]) {
    const len = arr.length;
    for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for (let i = gap; i < len; i++) {
            let j = i;
            let temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
            }
            arr[j] = temp;
        }
    }
}

移位法性能高于交换法

快速排序 QuickSort

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序{\displaystyle n}个项目要{\displaystyle \ O(n\log n)}（大O符号）次比较。在最坏状况下则需要{\displaystyle O(n^{2})}次比较，但这种状况并不常见。事实上，快速排序{\displaystyle \Theta (n\log n)}通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot）
2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

/**
 * 方法一：交换快排
 * @param arr
 * @param left
 * @param right
 */
function quickSort1(arr: number[], left: number, right: number) {
    if (left >= right) return arr;
    let x = arr[right]; // 作为对比值
    let i = left - 1;
    for (let j = left; j <= right; j++) {
        if (arr[j] <= x) {
            i++;
            const temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    quickSort1(arr, left, i - 1);
    quickSort1(arr, i + 1, right);
}

/**
 * 创建新数组快排
 * @param arr
 */
function quickSort2(arr: number[]): number[] {
    if (arr.length < 2) return arr;
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [];
    let right = [];
    for (let item of arr) {
        if (item < pivot) {
            left.push(item);
        } else {
            right.push(item);
        }
    }

    return quickSort2(left).concat([pivot]).concat(quickSort2(right));
}

归并排序

归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为{\displaystyle O(n\log n)}（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

采用分治法:

• 分割：递归地把当前序列平均分割成两半。
• 集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

import getRandomNum from './getRandomNum.ts';

/**
 * 分治中的治
 * @param arr 源数据
 * @param left 左边下标
 * @param right 右边下标
 * @param temp 中转数据
 */
function merge(arr: number[], left: number, mid: number, right: number, temp: number[]) {
    let i = left;
    let j = mid + 1;
    let t = 0;

    // 第一步，对比处理，进中转数据
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) { // 谁小，谁入
            temp[t] = arr[i];
            t++;
            i++;
        } else {
            temp[t] = arr[j];
            t++;
            j++
        }
    }

    // 第二步，将剩余的进中转，先进小的
    while (i <= mid) {
        temp[t] = arr[i];
        t++;
        i++
    }
    while (j <= right) {
        temp[t] = arr[j];
        t++;
        j++
    }

    // 第三步，中转数据放回 arr
    t = 0;
    let tempLeft = left;
    while (tempLeft <= right) {
        arr[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

function mergeSort(arr: number[], left: number, right: number, temp: number[]) {
    if (left < right) {
        const mid = Math.floor((left + right) / 2);
        mergeSort(arr, left, mid, temp); // 向左递归
        mergeSort(arr, mid + 1, right, temp); // 向右递归
        // console.log(arr.slice(left, right + 1)); // 输入当前值

        merge(arr, left, mid, right, temp); // 合并
    }
}

window.onload = function main() {
    const arr = [8, 4, 5, 7, 1, 3, 6, 2];
    const temp = Array(arr.length).fill(0);
    mergeSort(arr, 0, arr.length - 1, temp);
    console.log(arr);
}

基数排序

基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献[1]。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

import getRandomNum from './getRandomNum.ts';

function radixSort(arr: number[]) {
    // 创建桶 0 ~ 9
    const bucket: number[][] = Array(10).fill(0).map(() => []);
    // 创建每个桶放入的个数
    const bucketElementCounts: number[] = Array(10).fill(0);

    // 第一步，找到最大的数，使用它的位数进行遍历
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }

    // 这里 max.toString().length 方便处理位数
    for (let i = 0, n = 1; i < max.toString().length; i++, n *= 10) {
        // 放入桶中
        for (let j = 0; j < arr.length; j++) {
            const digitOfElement = Math.floor(arr[j] / n) % 10; // 取当前位的值
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++
        }

        // 从桶中取出
        let index = 0;
        for (let k = 0; k < bucketElementCounts.length; k++) { // k 哪个桶
            if (bucketElementCounts[k] !== 0) { // 桶中数量不为0
                for (let l = 0; l < bucketElementCounts[k]; l++) { // 每个桶中的数据长度
                    arr[index++] = bucket[k][l];
                }
            }
            bucketElementCounts[k] = 0; // 重置每个桶的数量，方便下次继续往里面存
        }
    }
}

window.onload = function main() {
    const arr = [53, 3, 542, 748, 14, 214];
    radixSort(arr);
    console.log(arr);
}

下期预告

• 查找算法