排序与搜索

搜索文档…
排序与搜索
排序算法(sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法。
排序算法的一个指标是稳定性，稳定性即：如果只按照第一个数字排序的话，第一个数字相同而第二个数字不同的，第二个数字按照原有排序的就是稳定排序，不按照原有排序的就是不稳定排序。
算法复杂度
排序方法
时间复杂度(平均)
时间复杂度(最坏)
时间复杂度(最好)
空间复杂度
稳定性
冒泡排序
​O(n2)O(n^2)O(n2)
​
​O(n2)O(n^2)O(n2)
​
​O(n)O(n)O(n)
​
​O(1)O(1)O(1)
​
稳定
选择排序
​O(n2)O(n^2)O(n2)
​
​O(n2)O(n^2)O(n2)
​
​O(n2)O(n^2)O(n2)
​
​O(1)O(1)O(1)
​
不稳定
插入排序
​O(n2)O(n^2)O(n2)
​
​O(n2)O(n^2)O(n2)
​
​O(n)O(n)O(n)
​
​O(1)O(1)O(1)
​
稳定
希尔排序
​O(n1.3)O(n^{1.3})O(n1.3)
​
​O(n2)O(n^2)O(n2)
​
​O(n)O(n)O(n)
​
​O(1)O(1)O(1)
​
不稳定
快速排序
​O(nlog2n)O(nlog_2{n})O(nlog2​n)
​
​O(n2)O(n^2)O(n2)
​
​O(nlog2n)O(nlog_2{n})O(nlog2​n)
​
​O(nlog2n)O(nlog_2{n})O(nlog2​n)
​
不稳定
归并排序
​O(nlog2n)O(nlog_2{n})O(nlog2​n)
​
​O(nlog2n)O(nlog_2{n})O(nlog2​n)
​
​O(nlog2n)O(nlog_2{n})O(nlog2​n)
​
​O(n)O(n)O(n)
​
稳定
冒泡排序(Bubble Sort)
我们先来了解一下冒泡排序算法，虽然比较容易实现，但是比较慢。之所以称之为冒泡排序是因为使用这种排序算法时，像气泡一样从数组的一端冒到另一端。
实现原理
每次比较，相邻的元素，如果第一个比第二个大，就交换两个元素的位置
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
重复 1 - 5
​
代码
1
function bubbleSort(arr) {
2
  const len = arr.length;
3
  for (let i = 0; i < len - 1; i++) {
4
    for (let j = 0; j < len - 1 - i; j++) {
5
      if (arr[j] > arr[j+1]) {
6
        const temp = arr[j+1];
7
        arr[j+1] = arr[j];
8
        arr[j] = temp;
9
      }
10
    }
11
  }
12
  return arr;
13
}
Copied!
选择排序(Selection Sort)
选择排序是一种简单直观的排序算法。选择排序从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有元素后最小的元素会被放到数组的第一个位置，然后从第二个元素开始继续。这个过程一直进行到数组的倒数第二个位置。
1
function selectionSort(arr) {
2
  const len = arr.length;
3
  let minIndex;
4
  let temp;
5
  for (let i = 0; i < len - 1; i++) {
6
      minIndex = i;
7
      for (let j = i + 1; j < len; j++) {
8
        if (arr[j] < arr[minIndex]) { 
9
          minIndex = j; // 保存最小数的索引
10
        }
11
      }
12
      temp = arr[i];
13
      arr[i] = arr[minIndex];
14
      arr[minIndex] = temp;
15
  }
16
  return arr;
17
}
Copied!
插入排序(Insertion Sort)
插入排序类似于按首字母或者数字对数据进行排序。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
1
function insertionSort(arr) {
2
  const len = arr.length;
3
  let preIndex;
4
  let current;
5
  for (let i = 1; i < len; i++) {
6
    preIndex = i - 1;
7
    current = arr[i];
8
    // 大于新元素，将该元素移到下一位置
9
    while (preIndex >= 0 && arr[preIndex] > current) {
10
      arr[preIndex + 1] = arr[preIndex];
11
      preIndex--;
12
    }
13
    arr[preIndex + 1] = current;
14
  }
15
  return arr;
16
}
Copied!
希尔排序(Shell Sort)
希尔排序之所以叫希尔排序，因为它就希老爷子(Donald Shell)创造的。希尔排序对插入做了很大的改善。核心理念与插入排序的不同之处在于，它会优先比较距离较远的元素，而不是相邻的元素。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减少，直到处理到数据的末尾。
1
function shellSort(arr) {
2
  const len = arr.length;
3
  let gap = Math.floor(len / 2);
4
​
5
  while (gap > 0) {
6
    for (let i = gap; i < len; i++) {
7
      const temp = arr[i];
8
​
9
      let j = i;
10
      while (j >= gap && arr[j - gap] > temp) {
11
        arr[j] = arr[j - gap];
12
        j -= gap;
13
      }
14
      arr[j] = temp;
15
    }
16
    gap = Math.floor(gap / 2);
17
  }
18
  return arr;
19
}
Copied!
快速排序(Quick Sort)
快速排序一般用来处理大数据集，速度比较快。快速排序通过递归的方式，将数据依次分为包含较小元素和较大元素的不同子序列。
实现原理
这个算法首先要在列表中选择一个元素作为基准值，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面。这个基准值一般有 4 种取法：
无脑拿第一个元素
无脑拿最后一个元素
无脑拿中间的元素
随便拿一个
下面的解法基于取最后一个元素实现：
1
function partition(arr, low, high) {
2
  let i = low - 1; // 较小元素的索引
3
  const pivot = arr[high];
4
​
5
  for (let j = low; j < high; j++) {
6
    // 当前的值比 pivot 小
7
    if (arr[j] < pivot) {
8
      i++;
9
      [arr[i], arr[j]] = [arr[j], arr[i]] 
10
    }
11
  }
12
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]
13
  return i + 1;
14
}
15
​
16
function quickSort(arr, low, high) {
17
  if (low < high) {
18
    const pi = partition(arr, low, high) 
19
    quickSort(arr, low, pi - 1) 
20
    quickSort(arr, pi + 1, high) 
21
  }
22
  return arr;
23
}
Copied!
归并排序(Merge Sort)
归并排序是把一系列排好序的子序列合并成一个大的完整有序序列。
实现原理
把长度为 n 的输入序列分成两个长度为 n / 2 的子序列，载 对这两个子序列分别采用归并排序，最后将两个排序好的子序列合并成一个最终的排序序列。
代码
1
function mergeSort(arr) {
2
  const len = arr.length;
3
  if (arr.length > 1) {
4
    const mid = Math.floor(len / 2); // 对半分
5
    const L = arr.slice(0, mid);
6
    const R = arr.slice(mid, len);
7
​
8
    let i = 0;
9
    let j = 0;
10
    let k = 0;
11
​
12
    mergeSort(L); // 对左边的进行排序
13
    mergeSort(R); // 对右边的进行排序
14
​
15
    while (i < L.length && j < R.length) {
16
      if (L[i] < R[j]) {
17
        arr[k] = L[i];
18
        i++;
19
      } else {
20
        arr[k] = R[j];
21
        j++
22
      }
23
      k++;
24
    }
25
​
26
    // 检查是否有剩余项
27
    while (i < L.length) {
28
      arr[k] = L[i];
29
      i++;
30
      k++;
31
    }
32
​
33
    while (j < R.length) {
34
      arr[k] = R[j];
35
      j++;
36
      k++;
37
    }
38
  }
39
  return arr;
40
}
Copied!
本章节将分为 3 个部分：
Part 1
合并两个有序数组 🌟
第一个错误的版本 🌟
搜索旋转排序数组 🌟🌟
Part 2
在排序数组中查找元素的第一个和最后一个位置 🌟🌟
数组中的第K个最大元素 🌟🌟
颜色分类 🌟🌟
Part 3
前K个高频元素 🌟🌟
寻找峰值 🌟🌟
合并区间 🌟🌟
Part 4
搜索二维矩阵 || 🌟🌟
计算右侧小于当前元素的个数 🌟🌟
以前
实现数组的全排列和单词搜索
下一个
合并两个有序数组、第一个错误的版本和搜索旋转排序数组
最近更新 2yr ago
复制链接
内容