ShiningDan的博客

排序算法入门

发表于 | 分类于 | | 阅读次数

最近又整理了一下常用的排序算法，并且都用 JavaScript 实现了一次。

参考链接：

八大排序算法
常见排序算法小结
JS中可能用得到的全部的排序算法

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常用的内部排序如下：

不同的算法效果总结：

插入排序-直接插入排序

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

算法的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort(arr) {
	for (let i = 1; i < arr.length; i++) {
		let val = arr[i];
		let j = i;
		while (arr[j-1] > val && j > 0) {
			arr[j] = arr[j-1];
			j--;
		}
		arr[j] = val;
	}
	return arr;
}

let a = [3,1,5,7,2,4,9,-4, -7, -5];
insertSort(a);

时间复杂度

O(n^2)

插入排序-希尔排序

希尔排序又叫缩小增量排序

基本思想

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

先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

一般增量的选择从 n/2 减少到 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function shellInsertSort(arr) {
	let len = Math.floor(arr.length/2);
	while (len > 0) {
		for (let i = 0; i < len; i++) {
			let j = i+len;
			while(j < arr.length) {
				let k = j;
				while(k >= len && arr[k-len] > arr[k]) {
					let tmp = arr[k];
					arr[k] = arr[k-len];
					arr[k-len] = tmp;
					k -= len;
				}
				j += len;
			}
		}
		len = Math.floor(len/2);
	}
	return arr;
}
let a = [3,1,5,7,2,4,9,-4, -7, -5];
shellInsertSort(a);

时间复杂度

最好情况：由于希尔排序的好坏和步长d的选择有很多关系，因此，目前还没有得出最好的步长如何选择(现在有些比较好的选择了，但不确定是否是最好的)。所以，不知道最好的情况下的算法时间复杂度。

最坏情况下：O(N*logN)，最坏的情况下和平均情况下差不多。

平均情况下：O(N*logN)

交换排序-冒泡排序

基本思想

通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。

!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(a) {
	for (var i = a.length - 1; i > 0; i--) {
		for (let j = 0; j < i; j++) {
			if (a[j] > a[j+1]) {
				let tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
	}
	console.log(a)
}
let a = [3,1,5,7,2,4,9,-4, -7, -5];
bubbleSort(a);

时间复杂度

平均情况：O(N*N)

最好情况下：正序有序，则只需要比较n次。故，为O(n)

最坏情况下: 逆序有序，则需要比较(n-1)+(n-2)+……+1，故，为O(N*N)

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程：

设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function bubbleSort(a) {
	let i = a.length-1;
	let pos;
	while (i>0) {
		pos = i-1;
		for (let j = 0; j < i; j++) {
			if (a[j] > a[j+1]) {
				let tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
				pos = j;
			}
		}
		i = pos;
	}
	return a;
}
let a = [3,1,5,7,2,4,9,-4, -7, -5];
bubbleSort(a);

交换排序-快速排序

基本思想

它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。

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
function quickSort(a, start, end) {
	if (start < end) {
		let i = start, j = end;
		let key = a[i];
		while (i !== j) {
			while (i < j) {
				if (a[j] < key) {
					a[i] = a[j];
					i++;
					break;
				}
				j--;
			}
			while (i < j) {
				if (a[i] > key) {
					a[j] = a[i];
					j--;
					break;
				}
				i++;
			}
		}
		a[i] = key;
		quickSort(a, start, i-1);
		quickSort(a, i+1, end);
	}
	console.log(a);
}
let a = [3,1,5,7,2,4,9,-4, -7, -5];
quickSort(a, 0, a.length-1);

时间复杂度

最好的情况下：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(N*logN)

最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较NN次，故为O(NN)

平均情况：O(N*logN)

选择排序-简单选择排序

基本思想

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectSort(a) {
	for (let i = 0; i < a.length; i++) {
		let index = i;
		for (let j = i+1; j < a.length; j++) {
			if (a[index] > a[j]) {
				index = j;
			}
		}
		let tmp = a[i];
		a[i] = a[index];
		a[index] = tmp;
	}
	return a;
}
let a = [3,1,5,7,2,4,9,-4, -7, -5];
selectSort(a);

时间复杂度。

最好情况下：交换0次，但是每次都要找到最小的元素，因此大约必须遍历NN次，因此为O(NN)。减少了交换次数！

最坏情况下，平均情况下：O(N*N)

选择排序-堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想

堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。

若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

(a) 大顶堆序列：（96, 83,27,38,11,09)

(b) 小顶堆序列：（12，36，24，85，47，30，53，91）

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到 n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

  1. 如何将 n 个待排序的数建成堆；
  2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

对 n 个元素初始建堆的过程。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

  1. n 个结点的完全二叉树，则最后一个结点是第 Math.floor(length/2) 个结点的子树。
  2. 筛选从 Math.floor(length/2) 第个结点为根的子树开始，该子树成为堆。
  3. 之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）

调整小顶堆的方法

  1. 设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
  2. 将根结点与左、右子树中较小元素的进行交换。
  3. 若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.
  4. 若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.
  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
34
35
36
37
// 调整队列为堆
/**
 * 本堆调整算法是小根堆
 * @param {Array} heap // 需要进行堆调整的队列
 * @param {int} i // 本次堆调整的 root 节点位置
 * @param {int} length // 队列的长度
 */
function heapAdjust(heap, i, length) {
    let left = 2 * i + 1, right = 2 * i + 2;
    let rootValue = heap[i], smallest = i;
    if (heap[smallest] > heap[left] && left < length) {
        smallest = left;
    }
    if (heap[smallest] > heap[right] && right < length) {
        smallest = right;
    }
    if (smallest !== i) {
        heap[i] = heap[smallest];
        heap[smallest] = rootValue;
        heapAdjust(heap, smallest, length);
    }
}

let heap =  [49, 38, 65, 97, 76, 13, 27, 49];
for (let i = Math.floor(heap.length/2)-1; i >= 0; i--) {
    heapAdjust(heap, i, heap.length); 
}

console.log(heap);

let result = [];
for (let i = heap.length-1; i >=0; i--) {
    result[heap.length-1-i] = heap[0];
    [heap[0], heap[i]] = [heap[i], heap[0]];
    heapAdjust(heap, 0, i-1);x
}
console.log(result);

时间复杂度

时间复杂度是 O(nlog(n))

归并排序（Merge Sort）

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

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
function merge(left, right) {
    let i = 0, j = 0, index = 0;
    let result = [];
    while(i < left.length && j < right.length) {
        result[index++] = left[i] < right[j] ? left[i++] : right[j++];
    }
    if (i !== left.length) {
        result = result.concat(left.slice(i, left.length));
    } 
    if (j !== right.length){
        result = result.concat(right.slice(j, right.length));
    }
    return result;
}

function mergeSort(array) {
    if (array.length < 2) {
        return array;
    }

    let left = array.slice(0, Math.floor(array.length/2));
    let right = array.slice(Math.floor(array.length/2));
    return merge(mergeSort(left), mergeSort(right));
}

let array = [49, 38, 65, 97, 76, 13, 27, 49];
console.log(mergeSort(array));