排序算法

- 冒泡排序

算法思想：重复走过将要排序的数列，一次比较两个元素，如果顺序错误就将他们交换，这个算法的名字由来是因为越小的元素会由交换“浮”到数列的顶端。（每一趟最大的一个数将到达数组末尾）

时间复杂度：O(n^2)

算法实现：

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

算法优化：设置一个flag，记录每趟是否会有数据交换，若本趟没有数据发生交换，则表明数组已经被排好序，可以直接返回。最理想时间复杂度O(n)

优化实现：

const bubbleSort = (nums) => {
    let temp;
    let flag;
    for (let i = 0; i < nums.length - 1; i++){
        flag = 0;
        for (let j = 0; j <= nums.length - i - 1; j++){
            if (nums[j] > nums[j + 1]) {
                flag = 1;
                temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
        if (!flag) return nums;
    }
    return nums;
}

- 选择排序

算法思想：选择排序是一种简单直观的排序算法，它将整个序列分为两部分：已排序序列和未排序序列，每次在未排序序列中选择最小的元素，将其放到已排序序列的末尾（将当前最小值与未排序的第一个数交换，并将已排序序列长度+1)。

时间复杂度：O(n^2)

算法实现：

const selectSort = (nums) => {
    for (let i = 0; i < nums.length - 1; i++){
        let minIndex = i;
        let min = nums[i];
        for (let j = i + 1; j <= nums.length - 1; j++){
            if (nums[j] < min) {
                min = nums[j];
                minIndex = j;
            }
        }
        if (minIndex != i) {
            nums[minIndex] = nums[i];
            nums[i] = min;
        }
    }
    return nums;
}

- 插入排序

算法思想：通过构建有序数列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度：O(n^2)

算法实现：

const insertSort = (nums) => {
    for (let i = 1; i <= nums.length - 1; i++){
        let insertNum = nums[i];
        let insertIndex = i;
        while (insertIndex > 0 && insertNum < nums[insertIndex-1]) {
            nums[insertIndex] = nums[insertIndex-1];
            insertIndex--;
        }
        nums[insertIndex] = insertNum;
    }
    return nums;
}

- 希尔排序

算法思想：简单的插入排序，当需要插入的数是比较小的数时，后移的次数明显增多，对效率产生影响，希尔排序是简单插入排序的改进版，又叫缩小增量排序。先将整个待排序的记录序列分割成若干子序列分别进行插入排序，然后逐步缩小增量，直到增量为1，则对整个数组进行插入排序，这样能有效减少小数据前移的次数。

例：增量=5，即待排序数列每隔五个数字为一组进行插入排序，若小数据前移一位，相当于在原有数列上前移五位。

时间复杂度：O(n^1.3)

算法实现：

const shallSort = (nums) => {
    //选择增量的值，每次/2
    for (let gap = Math.floor(nums.length / 2); gap > 0; gap = Math.floor(gap / 2)){
        for (let i = gap; i <= nums.length - 1; i++){
            let insertIndex = i;
            let insertNum = nums[insertIndex];
            while (insertIndex >= gap && insertNum < nums[insertIndex - gap]) {
                nums[insertIndex] = nums[insertIndex - gap];
                insertIndex -= gap;
            }
            nums[insertIndex] = insertNum;
        }
    }
    return nums;
}

- 快速排序

算法思想：在一个无序数组中取一个数key，每一趟排序的最终目的是让key左边的所有数小于key，key右边的都大于key；排序思路：取区间中最左或最右边的元素为key，定义两个变量p,q，q从区间的最右边向左走，找到比key小的就停下；p从左向右走，找到比key大的就停下，然后交换p和q指向的元素；重复以上过程，直到pq相遇，交换key和pq相遇的元素。

时间复杂度：O(nlog2n)

算法实现：

const quickSort = (nums, left, right) => {
    if (left >= right) return ;
    let l = left;
    let r = right;
    let key = l;
    while (l < r) {
        while (l < r && nums[r] >= nums[key]) {
            r--;
        }
        while (l < r && nums[l] <= nums[key]) {
            l++;
        }
        let temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }
    let temp = nums[l];
    nums[l] = nums[key];
    nums[key] = temp;
    quickSort(nums, left, l - 1);
    quickSort(nums, l + 1, right);

}
const nums = [1, 4, 2, 5, 7, 3, 12, 4, 6, 2, 1, 0];
quickSort(nums, 0, nums.length - 1);
console.log(nums);

- 归并排序

算法思想：将待排序的数列逐层折半分组，然后从最小分组开始排序，合并成一个大的分组，最终使所有元素均有序。

时间复杂度：O(nlog2n)

算法实现：

const sort = (nums, l = 0, r = nums.length - 1) => {
    if (l >= r) return;

    let mid = Math.floor((l + r) / 2);
    sort(nums, l, mid);
    sort(nums, mid + 1, r);
    merge(nums, l, mid, r);
}

const merge = (nums,l,mid,r) => {
    let arr = [];
    let i = l, j = mid+1, index = 0;
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) {
            arr[index++] = nums[i++];
        } else {
            arr[index++] = nums[j++];
        }
    }//选两列数中较小的数依次加入结果数列
    while (i <= mid) {
        arr[index++] = nums[i++];
    }
    while (j <= r) {
        arr[index++] = nums[j++];
    }//将两列中剩余的数加入数列

    for (let k = 0; k <= arr.length - 1; k++){
        nums[k + l] = arr[k];
    }//将归并结果覆盖原数组
}
let nums = [1, 0, 0, 2, 3, 5, 7, 4, 2, 3, 5, 67, 0];
sort(nums);
console.log(nums);

- 堆排序（学完结构后回来补

算法思想：根据堆的特性（大根堆：左右孩子<父亲；小根堆：左右孩子>父亲），创建堆->调整堆->选取最值->再次调整堆（比如将待排序数字构建为大根堆，要求从小到大排序，每次交换根节点与当前的末节点，这样最大节点、次大节点会逐步换到后面，实现排序）

算法实现：

const swap = (arr, i, j) => {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
//调整大根堆
const heapify = (arr, i, end) => {
    let current = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < end && arr[current] < arr[left]) {
        current = left;
    }
    if (right < end && arr[current] < arr[right]) {
        current = right;
    }
    if (current != i) {
        swap(arr, i, current);
        heapify(arr, current, end);
    }
}
//建立大根堆
const buildHeap = (arr) => {
    let length = arr.length;
    let mid = Math.floor(length / 2) - 1;
    //因为要取mid的左右儿子，所以循环从length/2开始
    for (let i = mid; i >= 0; i--) {
        heapify(arr, i, length);
    }
}

let arr = [3, 5, 1, 4, 2, 8, 7, 6]

const heapSort = (arr) => {
    buildHeap(arr);
    for (let i = arr.length - 1; i >= 0; i--) {
        swap(arr, 0, i);
        heapify(arr, 0, i);
    }
    return arr;
}
console.log(heapSort(arr))