常见排序算法

冒泡排序

冒泡排序是一种交换排序,基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

算法步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

动图演示

———— 动图来自《菜鸟教程》

说明:绿色表示当前正在比较的两个相邻元素;橘黄色表示已排完序的元素,不再参与后续的比较

代码实现(JS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function myBubbleSort(arr) {
var len = arr.length, temp;
for (var i = 0; i < len - 1; i++) { // 趟数
for (var j = 0; j < len - 1 - i; j++) { // 当前趟要比较的次数
if (arr[j] > arr[j+1]) { // 相邻元素两两比较
temp = arr[j]; // 元素交换
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}

代码与图片配合食用更加~


选择排序

选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

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

动图演示

代码实现(JS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function mySelectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) { // 第 i 轮选择
minIndex = i; // 每轮开始假设起始元素为最小值
for (var 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;
}

配图:


插入排序

插入排序的原理应该是最容易理解的,因为只要你打过扑克牌就应该能秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

算法步骤

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

动图演示

代码实现(JS)

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
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function myInsertSort(arr) {
var len = arr.length;
var insertItem; // 要插入的元素

// 从数组的第二个元素开始循环将数组中的元素插入
for (var i = 1; i < len; i++) {
insertItem = arr[i]; // 设置数组中的第2个元素为第一次遍历要插入的数据
var j = i - 1; // 已排序好数组的最后一个元素的索引

// 将已排好序的元素从最后一个往前依次与待插入元素比较,
while (j >= 0 && insertItem < arr[j]) {
// 如果要插入的元素小于第j个元素,就将第j个元素向后移动
arr[j + 1] = arr[j];
j--;
}
// 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
arr[j + 1] = insertItem;
}
return arr;
}
// 例如for循环中 i 等于 2 时,已排序完毕的元素为[3,44],进入for循环
// 待插入元素为 arr[2],也就是38;
// j=i-1也就是2-1等于1
// while循环比较,待插入元素38是小于arr[j](j=1)44 的 => 条件成立
// arr[j+1]要等于arr[j] => arr[2]要等于arr[1] => arr[2]=44 => 此刻数组前三个元素:[3,44,44]
// j-- => j=1-1也就是0
// 再来一轮while比较,待插入元素38现在不小于arr[j] 也就是arr[0]的3,所以直接退出while循环
// arr[j+1]=insertItem => arr[1]=38 => 数组前三排序完毕:[3,38,44]

希尔排序

希尔排序也是一种插入排序,它是简单插入排序的一个改进版,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

算法步骤(示例)

在此我们选择增量 gap=数组长度length/2,缩小增量继续以 gap = gap/2 的方式,这种增量选择我们可以用一个序列来表示:{n/2,(n/2)/2...1},称为增量序列。当然,希尔排序的增量序列有很多种,这里采用的是比较常用的一种作为示例:

在上面这幅图中:

初始时,有一个大小为 10 的无序序列。

在第一趟排序中,我们设 gap1 = 10 / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组。接下来,按照直接插入排序的方法对每个组进行排序。

在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。按照直接插入排序的方法对每个组进行排序。

在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。

注意:图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到,在排序过程中,两个元素位置交换了。
所以,希尔排序是不稳定的算法。

代码演示(JS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function myShellSort(arr) {
var gap = Math.floor(arr.length / 2);

while (1 <= gap) {
// 把距离为 gap 的元素编为一个组,扫描所有组
for (var i = gap; i < arr.length; i++) {
var j = 0;
var temp = arr[i];

// 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}

console.log(`gap = ${gap}`);
console.log(arr);
gap = Math.floor(gap / 2); // 减小增量
}
return arr;
}

归并排序

归并排序是利用归并的思想实现的排序方法,该算法采用经典的分治策略(分治法将问题分成一些小的问题然后递归求解,而治的阶段则将分的阶段得到的各答案”修补”在一起,即分而治之)。

可以看到这种结构很像一棵完全二叉树,下面的归并排序代码将会采用递归去实现(你也可采用迭代的方式去实现)。阶段可以理解为就是递归拆分子序列的过程,递归深度为logn。

算法步骤

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤 3 直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

图片演示

图片来自博客《图解排序算法之归并排序》

代码实现

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
32
33
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if (len < 2) return arr;

var middle = Math.floor(len / 2), // 将未排序数组拆分成两半分而治之
left = arr.slice(0, middle),
right = arr.slice(middle);

return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
var result = [];

while (left.length && right.length) {
// 两边的起始元素相互比较,始终将小的一方的头元素弹出,并push到准备好的容器result中
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;
}

快速排序

快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的元素均比另一部分记录的元素小,继而再分别对这两部分记录递归的进行同样的排序操作。

算法步骤

  1. 把数组中第一个元素当做一个基准值,称为“基准”(Pivot)
  1. 重新排序数列,把所有比基准值小的元素摆放在基准前面,所有比基准值大元素摆放在基准后面。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  1. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序;

分区(Partition)思路

首先把未排序数组的第一个(最左边)元素设置为基准,把它的位置叫做 l

然后依次向后查看所有元素,在查看过程中,不断的调整后面元素的位置,使得后面的元素分为两部分,一部分都小于 v ;一部分都大于 v 。

我们用 j 来不断记录这两部分的分割线位置。而 e 就是我们要判断的下一个元素,用索引 i 来表示,i 会遍历每一个元素,来看该如何调整这个元素。

在下图中,我们用 arr[l+1 ... j] 来表示小于 v 的橙色部分,用 arr[j+1 ... i-1] 来表示大于 v 的紫色部分。

接下来就要看如何来调整下一个元素 e 的位置。分情况讨论:

当 e 大于 v 时,我们直接让 e 融入大于 v 的部分,并让 i++

当 e 小于 v 时,我们让 e 和大于 v 部分的第一个元素交换位置。

把 e 融入到小于 v 的部分。此时就需要让分隔线的索引位置 j++ ,相应的,索引 i 的位置也要 i++ 以便查看下一个元素。

以这样的步骤我们就能遍历完整个数组,如下图所示

现在还差最后一个步骤,那就是把基准值 v ,与小于 v 部分的最后一个元素交换位置。此刻 v 左边都小于它,v 右边都大于它,而 j 指向的就是基准值所在的位置。这样我们就完成了分区(Partition)操作。

代码实现

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
32
33
34
35
36
37
38
39
40
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex, // 分区索引
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;

if (left >= right) return;

// 通过分区找到分隔点,再分别快排左右两部分
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
return arr;
}

function partition(arr, left, right) { // 分区操作
var v = left, // 设定基准值(pivot)
j = left; // arr[l+1...j] ; arr[j+1...i]
for (var i = j + 1; i <= right; i++) {
if (arr[i] < arr[v]) { // 当前要判断元素 小于 基准元素时
j++; // 分隔点右移
swap(arr, i, j); // 让 当前元素 与大于 v 部分的第一个元素交换位置
}
// 此处不用写 else ,因为当大于基准元素时,直接i++就好,
// 而i++,for循环已经帮我们做了
}
// 循环完毕后,交换基准值和小于v部分的最后一个元素的位置
swap(arr, v, j);
return j;
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

console.log(quickSort(arr, 0, arr.length));

计数排序

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

算法步骤

  1. 找出待排序的数组中最大和最小的元素;
  2. 统计数组中每个值为 i 的元素出现的次数,存入数组 Count 的第 i 项;
  3. 对所有的计数累加(从 Count 中的第一个元素开始,每一项和前一项相加);
  4. 反向填充目标数组:将每个元素 i 放在新数组的第 Count(i) 项,每放一个元素就将 Count(i) 减去1。

代码实现

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
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];

function countingSort(arr) {
var len = arr.length,
Result = [],
Count = [],
min = max = arr[0];

// 查找最大最小值,并将arr数置入Count数组中,统计出现次数
for (var i = 0; i < len; i++) {
min = min <= arr[i] ? min : arr[i];
max = max >= arr[i] ? max : arr[i];
Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1;
}

// 从最小值->最大值,将计数逐项相加
for (var j = min; j < max; j++) {
Count[j + 1] = (Count[j + 1] || 0) + (Count[j] || 0);
}
// Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据
for (var k = len - 1; k >= 0; k--) {
// Result[位置] = arr数据
Result[Count[arr[k]] - 1] = arr[k];
// 减少Count数组中保存的计数
Count[arr[k]]--;
}
return Result;
}

console.log(countingSort(arr));