基本排序算法

一、冒泡排序

1、基本思路

1. 从第一个元素开始，将相邻的元素两两进行比较，若前一位比后一位大，则交换位置；小则不变
2. 一趟排序之后，最大值总是会移动到数组的最后面
3. 在下一轮的比较中，不再考虑最后一个位置的元素
4. 每轮比较结束后，需要排序的元素数量减一，直到没有需要排序的元素

2、命名的由来

因为最大的元素会通过交换慢慢“浮”到数组的尾端，故名冒泡排序

3、代码实现

function bubbleSort(arr: number[]): number[] {const n = arr.lengthfor(let i = 0; i < n; i++) {let swapped = falsefor(let j = 0; j < n - 1 - i; j++) {if(arr[j] > arr[j+1]) {[arr[j], arr[j+1]] = [arr[j+1], arr[j]]swapped = true}}if(!swapped) break}return arr
}

4、时间复杂度

1、最好的情况：O(n)

即待排序的序列是有序的

此时仅需要遍历一遍序列，不需要进行交换操作

2、最坏的情况：O(n^2)

即待排序的序列是逆序的

需要进行n-1 轮排序，每一轮中需要进行n-1-i 次比较和交换操作

3、总结：

冒泡排序的时间复杂度主要取决于数据的初始顺序，不适用于大规模数据的排序

二、选择排序

1、基本思想

1. 首先将未排序部分的第一个元素标记为最小值
2. 然后从未排序部分的第二个元素开始遍历，依次和已知的最小值进行比较
3. 如果找到了比最小值更小的元素，就更新最小值的位置
4. 直到该轮遍历结束后，将更新后的最小值与标记的最小值进行交换

2、代码实现

function selectionSor(arr: number[]): number[] {const n = arr.length// 外层循环的作用：经过多少轮的找最小值for(let i = 0; i < n - 1; i++) {let minIndex = i// 内层循环的作用：每次找到最小值for(let j = 1 + i; j < n; j++) {if(arr[j] < arr[minIndex]) {minIndex = j}}// 只有不相等时，才需要进行交换的操作if(i !== minIndex) {[arr[i], [arr[minIndex]] = [arr[minIndex], arr[i]]    }}return arr   
}

3、时间复杂度

1、最好的情况：O(n^2)

即待排序的序列是有序的

内层循环每次都需要比较n-1 次，因此比较次数为n(n-1)/2 ，交换次数为0

2、最坏的情况：O(n^2)

即待排序的序列是逆序的

内层循环每次都需要比较n-i-1 次，因此比较次数为n(n-1)/2 ，交换次数为n(n-1)/2

3、平均情况的时间复杂度：O(n^2)

每个元素在内层循环中的位置都是等概率的，因此比较次数和交换次数的期望值都是n(n-1)/4

4、总结：

选择排序适用于小规模数据的排序

三、插入排序

1、基本思路

1. 首先假设数组的第一个元素已经排好序了，然后从第二个元素开始，不断与前面的有序数组中的元素进行比较
2. 如果当前元素小于前面的有序数组的元素，则把当前元素插入到前面的合适位置
3. 如果当前元素比前面的有序数组中所有的元素都大，则当前数组为前面有序数组的最后一个元素，直接进入到下一个元素的比较

2、代码实现

function insertionSort(arr: number[]): number[] {const n = arr.lengthfor(let i = 1; i < n; i++) {const newNum = arr[i]let j = i - 1while(arr[j] > newNum && j >= 0) {arr[j+1] = arr[j]j--}    arr[j+1] = newNum}return arr
}

3、时间复杂度

1、最好的情况：O(n)

即待排序的序列是有序的

每个元素只需要比较一次，因此比较的次数为n-1，移动的次数为0

2、最坏的情况：O(n^2)

即待排序的序列是逆序的

每个元素都需要比较和移动i 次，其中i 是元素在数组中的位置

因此比较的次数为n(n-1)/2 ，移动的次数为n(n-1)/2

3、平均情况的时间复杂度：O(n^2)

4、总结：

如果数组部分有序，插入排序可以比冒泡排序和选择排序更快

如果数组完全逆序，则插入排序的时间复杂度比较高，不如快速排序和归并排序

四、归并排序

1、基本思想

1. 步骤一：分解。如果待排序的数组长度为1 ，则认为这个数组已经有序，直接返回；将待排序数组氛围两个长度相等的子数组，分别对这两个字数组进行递归排序；将两个排好序的子数组合并成一个有序数组，返回这个有序数组。
2. 步骤二：合并。使用两个指针i 和 j 分别只想两个字数组的开头，比较他们的元素大小，并将小的元素插入到新的有序数组中；如果其中一个字数组已经遍历完，就将另一个子数组的声誉部分直接插入到新的有序数组中；最后返回这个有序数组。
3. 步骤三：终止条件。归并排序使用低柜算法来实现分解过程，当子数组的长度为1 时，认为这个子数组已经有序，递归结束。

2、代码实现

function mergeSort(arr: number[]): number[]{// 递归的结束条件if(arr.length <= 1) return arr// 拆分数组const mid = Math.floor(arr.length / 2)const leftArr = arr.slice(0, mid)const rightArr = arr.slice(mid)// 递归拆分数组const newLeftArr = mergeSort(leftArr)const newRightArr = mergeSort(rightArr)// 定义双指针，合并数组const newArr: number[] = []let i = 0let j = 0while(i < newLeftArr.length && j < newRightArr.length) {if(newLeftArr[i] < newRightArr[j]) {newArr.push(newLeftArr[i])i++} else {newArr.push(newRightArr[j])j++    }}    // 判断是否某一个数组中还有剩余的元素if(i < newLeftArr.length) {newArr.push(...newLeftArr.slice(i))    }if(j < newRightArr.length) {newArr.push(...newRightArr.slice(j))}return newArr
}

3、时间复杂度

1、最好的情况：O(log n)

即待排序的序列是有序的

每个子数组都只需要合并一次，即只需要进行一次归并操作

2、最坏的情况：O(nlog n)

即待排序的序列是逆序的

每个子数组都需要进行多次合并

3、平均情况：O(nlog n)

4、总结：

归并排序的时间复杂度为O(nlog n)

五、快速排序

1、基本思想

快速排序是一种原地排序算法，不需要额外的数组空间

1. 首先选择一个基准元素，通常选择第一个或最后一个元素作为基准元素
2. 然后定义两个指针i 和 j，分别指向数组的左右两端（不包含基准元素）
3. 从右侧开始，向左移动j 指针，直到找到一个小于或等于基准元素的值；从左侧开始，向右移动i 指针，直到找到一个大于或等于基准元素的值。如果此时i 指针小于或等于j 指针，交换i 和j 指针所指向的元素
4. 重复步骤3，直到i 指针大于j 指针，并将基准元素与i 指针所指向的元素交换位置。此时数组分为两部分，左侧部分包含小于或等于基准元素的元素，右侧部分包含大于基准元素的元素
5. 然后对左右两部分分别递归调用快速排序，直到左右两部分只剩下一个元素，即为有序

2、代码实现

function quickSort(arr: number[]): number[] {partition(0, arr.length - 1)function partition(left: number, right: number) {// 递归结束条件if(left >= right) return // 取数组的最后一个元素作为基准元素const pivot = arr[right]// let i = leftlet j = right - 1while(i <= j) {while(arr[i] < pivot) {i++}while(arr[j] > pivot) {j--}if(i <= j) {[arr[i], arr[j]] = [arr[j], arr[i]]i++j--}}  [arr[i], arr[right]] = [arr[right], arr[i]]partition(left, j)  partition(i + 1, right)}return arr
}

3、时间复杂度

1、最好的情况：O(nlog n)

即基准元素位于数组的中间位置，此时递归的深度为O(log n)，每一层需要进行n 次比较

2、最坏的情况：O(n^2)

当每次划分后，其中一部分为空，即基准元素是数组中的最大或最小值，此时递归的深度为O(n)，每一层需要进行n 次比较

采用三数取中法或随机选择基准元素可以有效避免最坏情况的发生

3、平均情况：O(nlog n)

六、堆排序

1、基本思想

1. 首先需要构建最大堆。遍历待排序序列，从最后一个非叶子节点开始，依次对每个节点进行调整；假设当前节点的下标为i， 左子节点的下标为2i+1，右子节点的下标为2i+2，父节点的下标为(i-1)/2；对于每个节点i，比较它和左右子节点的值，找出其中最大的值，并将其与节点i进行交换；重复进行这个过程，直到节点i满足最大堆的性质；依次对每个非叶子节点进行上述操作，直到根节点，这样就得到了一个最大堆
2. 然后进行排序。将堆的根节点（也就是最大值）与堆的最后一个元素交换，这样最大值就被放在了正确的位置上；将堆的大小减小一，并将剩余的元素重新构建成一个最大堆；重复上述步骤，直到堆的大小为1，这样就得到了有序的序列

2、代码实现

function heapSort(arr: number[]): number[] {// 1.获取数组的长度const n = arr.length// 2.对arr 进行原地建堆// 从第一个非叶子节点开始进行下滤操作const start = Math.floor((n / 2) - 1)for(let i = start; i >= 0; i++) {// 进行下滤操作heapifyDowm(arr, n, i)}// 3.对最大堆进行排序的操作for(let i = n - 1; i > 0; i--) {swap(arr, 0, i )heapifyDown(arr, i, 0)}return arr
}
// 下滤操作函数
// arr：在数组中进行下滤操作；n：下滤操作的范围；index：哪一个位置需要进行下滤操作
function heapifyDown(arr: number[], n:number, index:number) {while(2 * index + 1 < n) {// 1.获取左右子节点的索引const leftChildIndex = 2 * index + 1const rightChildIndex = 2 * index + 2// 2.找出左右子节点较大的值let largerIndex = leftChildIndexif(rightChildIndex < n && arr[rightChildIndex] > arr[leftChildIndex]) {largerIndex = rightChildIndex}    // 3.判断index 位置的值比更大的子节点，直接breakif(arr[index] >= arr[largerIndex]) {break}// 4.和最大位置的进行交换操作swap(arr, index, largerIndex)index = largerIndex}
}

3、时间复杂度

1、时间复杂度：O(nlog n)

2、空间复杂度：O(1)

七、希尔排序

1、基本思想

改进版的插入排序，步长变化的插入排序

2、代码实现

function shellSort(arr: number[]): number[]{const n = arr.length// 选择不同的增量(步长/间隔)let gap = Math.floor(n/2)// 1. 不断改变步长的过程while(gap > 0) {// 获取到不同的gap，使用gap 进行插入排序// 2.找到不同的数列集合进行插入排序的操作for(let i = gap; i < n; i++) {let j = iconst num = arr[i]// 使用num 向前去找到一个比num 小的值// 3.对数列进行插入排序的过程while(j > gap - 1 && num < arr[j - gap]) {arr[j] = arr[j - gap]j = j - gap}arr[j] = num}gap = Math.floor(gap / 2)}return arr
}

3、时间复杂度

1、最坏的情况：O(n^2)

2、通常情况下都要好于O(n^2)