排序与搜索

排序算法(sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。

排序算法的一个指标是稳定性,稳定性即:如果只按照第一个数字排序的话,第一个数字相同而第二个数字不同的,第二个数字按照原有排序的就是稳定排序,不按照原有排序的就是不稳定排序。

算法复杂度

排序方法

时间复杂度(平均)

时间复杂度(最坏)

时间复杂度(最好)

空间复杂度

稳定性

冒泡排序

O(n2)O(n^2)

O(n2)O(n^2)

O(n)O(n)

O(1)O(1)

稳定

选择排序

O(n2)O(n^2)

O(n2)O(n^2)

O(n2)O(n^2)

O(1)O(1)

不稳定

插入排序

O(n2)O(n^2)

O(n2)O(n^2)

O(n)O(n)

O(1)O(1)

稳定

希尔排序

O(n1.3)O(n^{1.3})

O(n2)O(n^2)

O(n)O(n)

O(1)O(1)

不稳定

快速排序

O(nlog2n)O(nlog_2{n})

O(n2)O(n^2)

O(nlog2n)O(nlog_2{n})

O(nlog2n)O(nlog_2{n})

不稳定

归并排序

O(nlog2n)O(nlog_2{n})

O(nlog2n)O(nlog_2{n})

O(nlog2n)O(nlog_2{n})

O(n)O(n)

稳定

冒泡排序(Bubble Sort)

我们先来了解一下冒泡排序算法,虽然比较容易实现,但是比较慢。之所以称之为冒泡排序是因为使用这种排序算法时,像气泡一样从数组的一端冒到另一端。

实现原理

  • 每次比较,相邻的元素,如果第一个比第二个大,就交换两个元素的位置

  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

重复 1 - 5

代码

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

选择排序(Selection Sort)

选择排序是一种简单直观的排序算法。选择排序从数组的开头开始,将第一个元素和其他元素进行比较,检查完所有元素后最小的元素会被放到数组的第一个位置,然后从第二个元素开始继续。这个过程一直进行到数组的倒数第二个位置。

function selectionSort(arr) {
const len = arr.length;
let minIndex;
let temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 保存最小数的索引
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}

插入排序(Insertion Sort)

插入排序类似于按首字母或者数字对数据进行排序。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

function insertionSort(arr) {
const len = arr.length;
let preIndex;
let current;
for (let i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
// 大于新元素,将该元素移到下一位置
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}

希尔排序(Shell Sort)

希尔排序之所以叫希尔排序,因为它就希老爷子(Donald Shell)创造的。希尔排序对插入做了很大的改善。核心理念与插入排序的不同之处在于,它会优先比较距离较远的元素,而不是相邻的元素。当开始用这个算法遍历数据集时,所有元素之间的距离会不断减少,直到处理到数据的末尾。

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

快速排序(Quick Sort)

快速排序一般用来处理大数据集,速度比较快。快速排序通过递归的方式,将数据依次分为包含较小元素和较大元素的不同子序列。

实现原理

这个算法首先要在列表中选择一个元素作为基准值,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面。这个基准值一般有 4 种取法:

  • 无脑拿第一个元素

  • 无脑拿最后一个元素

  • 无脑拿中间的元素

  • 随便拿一个

下面的解法基于取最后一个元素实现:

function partition(arr, low, high) {
let i = low - 1; // 较小元素的索引
const pivot = arr[high];
for (let j = low; j < high; j++) {
// 当前的值比 pivot 小
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]
return i + 1;
}
function quickSort(arr, low, high) {
if (low < high) {
const pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
}
return arr;
}

归并排序(Merge Sort)

归并排序是把一系列排好序的子序列合并成一个大的完整有序序列。

实现原理

把长度为 n 的输入序列分成两个长度为 n / 2 的子序列,载 对这两个子序列分别采用归并排序,最后将两个排序好的子序列合并成一个最终的排序序列。

代码

function mergeSort(arr) {
const len = arr.length;
if (arr.length > 1) {
const mid = Math.floor(len / 2); // 对半分
const L = arr.slice(0, mid);
const R = arr.slice(mid, len);
let i = 0;
let j = 0;
let k = 0;
mergeSort(L); // 对左边的进行排序
mergeSort(R); // 对右边的进行排序
while (i < L.length && j < R.length) {
if (L[i] < R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++
}
k++;
}
// 检查是否有剩余项
while (i < L.length) {
arr[k] = L[i];
i++;
k++;
}
while (j < R.length) {
arr[k] = R[j];
j++;
k++;
}
}
return arr;
}

本章节将分为 3 个部分:

  • Part 1

    • 合并两个有序数组 🌟

    • 第一个错误的版本 🌟

    • 搜索旋转排序数组 🌟🌟

  • Part 2

    • 在排序数组中查找元素的第一个和最后一个位置 🌟🌟

    • 数组中的第K个最大元素 🌟🌟

    • 颜色分类 🌟🌟

  • Part 3

    • 前K个高频元素 🌟🌟

    • 寻找峰值 🌟🌟

    • 合并区间 🌟🌟

  • Part 4

    • 搜索二维矩阵 || 🌟🌟

    • 计算右侧小于当前元素的个数 🌟🌟