常见的十个排序算法
发表 更新 算法 11 分钟读完 (大约5272个字) 0次访问

常见的十个排序算法

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是指数据记录在内存中进行排序，而外部排序是指因排序的数据量很大，一次不能在内存种中容纳全部的排序记录，因而在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

通过比较元素的大小来决定元素间相对次序的排序也称为比较类排序，如经典的插入排序。由于这类排序时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。而非比较类排序则可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序，如计数排序。

常见十大排序算法

冒泡排序 (Bubble Sort)

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

算法描述

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 重复步骤 1~3，直到排序完成。

动图演示

冒泡排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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]) {
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
      }
    }
  }
  return arr;
}

复杂度分析

时间复杂度最坏的情况是反序序列，要比较 n(n-1)/2 次，时间复杂度为 O(n^2)，最好的情况是正序，只进行 (n-1) 次比较，不需要移动，时间复杂度为 O(n)，而平均的时间复杂度为 O(n^2)。冒泡排序是一种稳定的排序算法，元素较少时效率比较高。

选择排序 (Selection-sort)

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

算法描述

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第 2 步，直到所有元素均排序完毕。

动图演示

选择排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function selectionSort(arr) {
  const len = arr.length;
  let minIndex;
  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;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

复杂度分析

表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n^2) 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

插入排序 (Insertion Sort)

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，有一种优化算法，叫做拆半插入。

算法描述

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤 2~5。

动图演示

插入排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function insertionSort(arr) {
  const len = arr.length;
  let preIndex, 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;
}

复杂度分析

插入排序的时间复杂度最好的情况是已经是正序的序列，只需比较 (n-1) 次，时间复杂度为 O(n)，最坏的情况是倒序的序列，要比较 n(n-1)/2 次，时间复杂度为 O(n^2)，平均的话要比较时间复杂度为 O(n^2)。插入排序是一种稳定的排序方法，排序元素比较少的时候很好，大量元素便会效率低下。

希尔排序 (Shell Sort)

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

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

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

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法描述

  • 选择一个增量序列 t1, t2, …, tk，其中 ti > tj, tk = 1；
  • 按增量序列个数 k，对序列进行 k 趟排序；
  • 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

例如：

算法图解

动图演示

希尔排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

复杂度分析

希尔排序的时间复杂度最好的情况是已经是正序的序列，只需比较 (n-1) 次，时间复杂度为 O(n)，最坏的情况是倒序的序列，时间复杂度为 O(nlogn)，平均时间复杂度为 O(nlogn)。

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比 O(n^2) 好一些。

归并排序 (Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。

算法描述

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

动图演示

归并排序动图演示(自下而上)

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function mergeSort(arr) {
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  const middle = Math.floor(len / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length) {
    result.push(right.shift());
  }
  return result;
}

复杂度分析

归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

快速排序 (Quick Sort)

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

  • 从数列中挑出一个元素，称为 “基准” (pivot);
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
  • 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

动图演示

快速排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function quickSort(arr, left, right) {
  const len = arr.length;
  left = typeof left == 'number' ? left : 0;
  right = typeof right == 'number' ? right : len - 1;
  if (left < right) {
    const pivot_pos = partition(arr, left, right);
    quickSort(arr, left, pivot_pos - 1);
    quickSort(arr, pivot_pos + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[left];
  while (left < right) {
    for (; left < right && arr[right] > pivot; --right) {}
    arr[left] = arr[right]
    for (; left < right && arr[left] <= pivot; ++left) {}
    arr[right] = arr[left]
  }
  arr[left] = pivot;
  return left;
}

复杂度分析

相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。

当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(n^2)，比如说顺序数列的快排。但它的平均时间复杂度是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

堆排序 (Heap Sort)

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

算法描述

  • 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆；
  • 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端；
  • 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

动图演示

堆排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

let len;

function heapify(arr, i) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [arr[largest], arr[i]] = [arr[i], arr[largest]];
    heapify(arr, largest);
  }
}

function heapSort(arr) {
  len = arr.length;
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i);
  }
  for (let i = len - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    len--;
    heapify(arr, 0);
  }
  return arr;
}

复杂度分析

构建初始堆经推导复杂度为 O(n)，在交换并重建堆的过程中，需交换 n-1 次，而重建堆的过程中，根据完全二叉树的性质，[log(n-1), log(n-2), ..., 1] 逐步递减，近似为 nlogn。所以堆排序时间复杂度一般认为就是 O(nlogn) 级。

计数排序 (Counting Sort)

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法描述

  1. 统计数组中每个值为 i 的元素出现的次数，存入数组 bucket 的第 i 项；
  2. 对所有的计数累加；
  3. 反向填充目标数组。

动图演示

计数排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function countSort(arr) {
  const bucket = []
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i]
    bucket[num] >= 1 ? bucket[num]++ : (bucket[num] = 1);
  }
  let index = 0;
  for (let i = 0; i < bucket.length; i++) {
    while (bucket[i] > 0) {
      arr[index++] = i;
      bucket[i]--;
    }
  }
  return arr
}

复杂度分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0~k 之间的整数时，时间复杂度是 O(n+k)，空间复杂度也是 O(n+k)，其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

桶排序 (Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。

为了使桶排序更加高效，我们需要做到这两点：

  • 在额外空间充足的情况下，尽量增大桶的数量；
  • 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

算法描述

  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列，并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。

示意图

元素分布在桶中：

然后，元素在每个桶中排序：

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

function bucketSort(arr, num = 10) {
  function swap(arr, i, j) {
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
  const len = arr.length
  const max = Math.max(...arr)
  const min = Math.min(...arr)
  const buckets = []
  const bucketsSize = Math.floor((max - min) / num) + 1
  for (let i = 0; i < len; i++) {
    const index = Math.floor((arr[i] - min) / bucketsSize)
    if (!buckets[index]) {
      buckets[index] = []
    }
    buckets[index].push(arr[i])
    for (let l = buckets[index].length; l > 0; l--) {
      if (buckets[index][l] < buckets[index][l - 1]) {
        swap(buckets[index], l, l - 1)
      }
    }
  }
  let wrapBuckets = []
  for (let i = 0; i < buckets.length; i++) {
    if (buckets[i]) {
      wrapBuckets = wrapBuckets.concat(buckets[i])
    }
  }
  return wrapBuckets
}

复杂度分析

桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

基数排序 (Radix Sort)

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法描述

  • 取得数组中的最大数，并取得位数；
  • arr 为原始数组，从最低位开始取每个位组成 radix 数组；
  • 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）。

动图演示

基数排序动图演示

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

function radixSort(arr) {
  const max = Math.max(...arr)
  const counter = [];
  for (let i = 0, mod = 10, dev = 1; i < max; i++, dev *= 10, mod *= 10) {
    for (let j = 0; j < arr.length; j++) {
      const bucket = Math.floor((arr[j] % mod) / dev);
      if (counter[bucket] == null) {
        counter[bucket] = [];
      }
      counter[bucket].push(arr[j]);
    }
    let pos = 0;
    for (let j = 0; j < counter.length; j++) {
      let value = null;
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value;
        }
      }
    }
  }
  return arr;
}

复杂度分析

基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要 O(n) 的时间复杂度，而且分配之后得到新的关键字序列又需要 O(n) 的时间复杂度。假如待排数据可以分为 d 个关键字，则基数排序的时间复杂度将是 O(d*2n) ，当然 d 要远远小于 n，因此基本上还是线性级别的。

基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k，因此额外空间需要大概 n 个左右。

参考

常见的十个排序算法

https://blog.imaple.net/posts/algorithm_sort/

作者

iMaple

发布于

2020-04-18

更新于

2020-05-10

许可协议

CC BY-NC 4.0

#

评论

关注我

分类

标签

algorithm 1
certificate 1
don't ask 1
git 1
hugo 1
mail 1
minecraft 1
nginx 1
sqlite 1
teamspeak3 1
tls 3
workflow 2

最新文章

归档

链接

订阅更新

Powered by Google feedburner

×