数据结构 —— 排序算法总结

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

本文记录了几种经典的排序算法，并对排序算法的性能进行了总结，如果有哪里写的不妥的，还请大家指正批评。同时，也欢迎大家提供更简单有效的算法。

排序算法的性能评估

  • 稳定性（假设记录 a 和记录 b 都位于待排序的序列中）
    （1）稳定：如果 a 本来就在 b 前面，且 a = b，排序之后 a 仍然在 b 前面；
    （2）不稳定：如果 a 本来就在 b 前面，且 a = b，排序之后 a 可能出现在 b 后面；
  • 待排序的记录是否全部被放置在内存中
    （1）内排序：在整个排序过程中，待排序的所有记录全部被放置在内存中；（文中的所有排序算法都属于内排序）
    （2）外排序：由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行；
  • 时间复杂度：排序算法的时间开销
  • 空间复杂度：排序算法所需的存储空间
  • 算法本身的复杂度

排序算法（7 种）

下面，将根据 程杰的《大话数据结构》 ，从易到难对7种排序算法进行整理归纳

1、冒泡排序（Bubble Sort）

基本思想： 两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。
（1）初级版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bubbleSort0(arr){
	console.time("冒泡排序初级版");
    var len = arr.length;
    for(var i = 0; i < len; i ++){
        for(var j = i + 1; j < len; j ++){
            if(arr[i] > arr[j]){
                swap(arr,i,j);
            }
        }
    }
    console.timeEnd("冒泡排序初级版");
    return arr;
}
// 交换两个元素
function swap(arr,i,j){
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(BubbleSort0(num));        // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

上面代码中，每一次外循环，都是将第 i 个位置的记录， 与它后面的记录进行比较。如果大，则进行交换，这样一次大循环之后，第 i 个位置的记录与后面位置的记录相比就是最小的。

（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
function bubbleSort1(arr){
    console.time('冒泡排序正宗版耗时');
    var len = arr.length;
    for(var i = 0; i < len; i ++){
        // j 从后往前循环
        for(var j = len - 1; j >= i; j --){
            if(arr[j-1] > arr[j]){     // 进行两两相邻比较
                swap(arr, j-1, j);
            }
        }
    }
    console.timeEnd('冒泡排序正宗版耗时');
    return arr;
}
// 交换元素
function swap(arr,i,j){
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(bubbleSort1(num));    // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

每执行一次外循环，会从排序数组末尾开始两两比较，把较小的记录交换到前面，知道找到最小值放在第 i 个位置。这样在寻找最小值的过程中，也会把较小值移到排序数组的前面，显然这一点要由于冒泡排序初级版。

（3）优化版

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
console.time('冒泡排序优化版耗时');
	var len = arr.length;
	var flag = true;    // flag用来作为标记
	for(var i = 0; i < len && flag; i ++){    // 当flag = false时，退出循环
		flag = false;    // flag初始化为false
		for(var j = len - 1; j >= i; j --){
			if(arr[j-1] > arr[j]){
				swap(arr, j-1, j);
				flag = true;     // 如果发生数据交换，则flag = true
			}
		}
	}
	console.timeEnd('冒泡排序优化版耗时');
	return arr;
}
// 交换元素
function swap(arr, i, j){
	var tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(bubbleSort2(num));      // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

假设待排序的序列为 {2,1,3,4,5,6,7,8,9} ， 除了第一和第二个记录需要交换外，其他都已经是正确的顺序了。也就是说，后面的记录其实不需要进行交换，也不需要进行比较。这里设置 flag 变量作为标记，每次外循环的时候判断前一次循环中的内循环是否进行数据交换。如果没有进行数据交换，则退出外循环，说明后面已经是有序的了，不需要再进行比较。

经过这样的改进，冒泡排序在性能上就有了一定的提升，可以避免因已经有序的情况下的无意义循环判断。

这只是冒泡排序算法的一种改进，网上还有很多其他的改进算法，可以参考十大经典排序算法的JS 版。

冒泡排序性能评估

  • 稳定性：不稳定；
  • 待排序的记录是否全部被放置在内存中：内排序；
  • 时间复杂度
    （1）最好的情况：O(n)——已经是正序的；
    （2）最坏的情况：O(n^2)——正好是逆序的；
    （3）平均的情况：O(n);
  • 空间复杂度：O(1);
  • 算法本身的复杂度：简单;

2、选择排序（Selection Sort）

基本思想： 每一趟通过 n-i 次关键字之间的比较，从 n-i+1 个记录中选出关键字最小的记录，并和第 i 个记录进行交换；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function selectionSort(arr){
  var len = arr.length;
  for(var i = 0; i < len; i ++){
    var min = i;              // 让最小值的最初索引等于当前的i
    for(var j = i + 1; j < len; j ++){      
      if(arr[j] < arr[min]){      // 如果有小于当前最小值的关键字
        min = j;              // 将次关键字的索引赋给min
      }
    }
    if(i != min){     // 如果min发生改变，则交换元素
      swap(arr,i,min);
    }
  }
  return arr;
}
function swap(arr,i,j){
  var tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(selectionSort(num));

选择排序性能评估

  • 时间复杂度：无论最好最差，都是 O(n^2)；
  • 空间复杂度：O(1)；
  • 算法本身复杂度：简单；
  • 性能略优于冒泡排序，因为交换移动次数比较少；

3、插入排序（Insertion Sort）

基本思想： 将未排序的无序表中的一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function insertionSort(arr){
    var len = arr.length;
    for(var i = 1; i < len; i ++){
    	if(arr[i] < arr[i-1]){
    		var tmp = arr[i];     // 备份
    		// 遍历有序列表，满足条件的记录后移
    		for(var j = i-1; arr[j] > tmp; j --){
    			arr[j+1] = arr[j];
    		}
    		arr[j+1] = tmp;   // 插入到正确的位置
    	}
    }
    return arr;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(insertionSort(num));

插入排序性能评估

  • 时间复杂度
    （1）最好的情况：O(n)——已经是正序的，比较 n-1 次，没有移动；
    （2）最坏的情况：O(n^2)——正好是逆序的；
    （3）平均的情况：O(n^2)；
  • 空间复杂度：O(1)
  • 算法本身的复杂度：简单
  • 插入排序比冒泡和选择排序的性能要好一些

4、希尔排序（Shell 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
function shellSort(arr){
	var len = arr.length;
	// 对“增量”进行初始化（等于数组的长度）
	var increment = len;     
	do{
		increment = Math.floor(increment / 3 + 1);
		for(var i = increment + 1; i < len; i ++){
		    // 进行跳跃式比较
			if(arr[i] < arr[i - increment]){
				// 需要将arr[i]插入有序增量子表
				var tmp = arr[i];   // 备份
				// 记录跳跃式后移
				for(var j = i - increment; j > 0 && arr[j] > tmp; j -= increment){
					arr[j + increment] = arr[j];
				}
				arr[j + increment] = tmp;    // 插入正确位置
			}
		}
	}while(increment > 1)
	return arr;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(shellSort(num));     // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

希尔排序性能评估

  • 稳定性：不稳定（跳跃式比较并移动）；
  • 时间复杂度：O(n^(3/2))，优于插入排序的O(n^2)；
  • 空间复杂度：O(1)；
  • 算法本身的复杂度：较前面三种排序算法稍复杂；

5、堆排序（Heap Sort）

—— 基于选择排序进行改进的算法

堆是具有下列性质的完全二叉树： 每个节点的值都大于或等于其左右孩子的节点的值，称为 大顶堆；或者每个节点的值都小于或蒸鱼其左右孩子的值，称为 小顶堆；

基本思想：（假设利用大顶堆） 将待排序的序列构成一个大顶堆。此时，整个序列的最大值就是对顶的根结点，将它移步（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 堆排序函数
function heapSort(arr){
	var len = arr.length;
	// 由于按层序遍历二叉树得到的序列索引从1开始，所以这里我们手动在数组开头加上一个0元素
	arr.unshift(0);
	// 第一步：将无序数列构建成一个大顶堆
	for(var i = Math.floor(len / 2); i > 0; i --){
		heapAdjust(arr,i,len);   
	}
	// 第二步：将每个最大值的根结点与末尾元素进行交换，并再次调整其成为大顶堆
	for(var i = len; i > 1; i --){
		swap(arr,1,i);    // 交换
		heapAdjust(arr,1,i-1);    // 重新调整
	}
	// 排好序后，将数组开头的元速度删除
	arr.shift();
	return arr;
}
// 堆调整函数：调整arr[s],使arr[s]-arr[m]成为一个大顶堆
function heapAdjust(arr,s,m){
	var tmp = arr[s];   // 备份
	// 从下到上，从左往右，调整每一个子树
	for(var j = 2 * s; j <= m; j *= 2){
		// 先判断该结点的俩孩子，j为值较大的下标
		if(j < m && arr[j] < arr[j + 1]){
			++ j;
		}
		// 再判断该结点与较大孩子的大小
		// 若大于等于，则无需交换；若小于，则交换两者的位置
		if(tmp >= arr[j]){
			break;
		}
		arr[s] = arr[j];
		s = j;
	}
	arr[s] = tmp;
}
// 交换元素
function swap(arr,i,j){
	var tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(heapSort(num));    // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

堆排序性能评估

  • 稳定性：不稳定；
  • 时间复杂度：无论最好、最坏情况，时间复杂度都是：O(nlogn)；
  • 空间复杂度：O(1)；
  • 算法本身的复杂度：复杂；

6、归并排序（Merging Sort）

“归并”： 在数据结构中，指的是将两个或两个以上的有序表组合成一个新的有序表；

基本思想： 假设初始序列含有 n 个记录，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 x （一个不小于 n/2 的整数）个长度为 2 或 1 的有序子序列，再两两归并，……，如此重复，直至的代一个长度为 n 的有序序列为止；

（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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function mergingSort1(arr){
	var len = arr.length;
	var result = mSort(arr,arr,0,len-1);
	return result;
}
// 先拆分，后合并
function mSort(SR,TR1,s,t){
	// 将SR先进行拆分，然后再合并成有序序列
	var TR2 = [];
	if(s == t){
		TR1[s] = SR[s];
	}else{
		var m = Math.floor((s+t)/2);     // 取中间下标
		// 递归调用
		mSort(SR,TR2,s,m);    // 对前半段进行操作
		mSort(SR,TR2,m+1,t);   // 对后半段进行操作
		merge(TR2,TR1,s,m,t);
	}
	return TR1;
}
// 合并成有序序列
function merge(SR,TR,i,m,n){
	// j为SR后半段的索引，i为SR前半段的索引，k为TR的索引
	for(var j = m+1, k = i; i <= m && j <= n; k ++){
		// 将前半段和后半段一一进行比较，谁小就添加到TR中，同时索引后移，直到其中一段全部被添加到TR中
		if(SR[i] < SR[j]){
			TR[k] = SR[i ++];
		}else{
			TR[k] = SR[j ++];
		}
	}
	// 将另一段剩余部分也添加到TR中
	if(i <= m){
		for(var l = 0; l <= m-i; l ++){
			TR[k + l] = SR[i + l];
		}
	}
	if(j <= n){
		for(var l = 0; l <= n-j; l ++){
			TR[k + l] = SR[j + l];
		}
	}
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(mergingSort1(num));      // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

归并排序性能分析

  • 稳定性：两两比较，不存在跳跃，稳定；
  • 时间复杂度：无论最好、最坏情况，时间复杂度都是：O(nlogn)；
  • 空间复杂度：O(n+logn)；
  • 算法本身的复杂度：复杂；
  • 归并排序是一种比较占内存，但却效率高且稳定的算法；

（2）非递归实现 （不太明白，后期再加上）

7、快速排序（Quick 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
31
32
33
34
35
36
37
38
39
40
41
42
43
function quickSort(arr){
	var len = arr.length;
	var result = qSort(arr,0,len-1);
	return result;
}
function qSort(arr,low,high){
	if(low < high){
		// 将 arr 一分为二
		var pivot = partition(arr,low,high);    // 计算出枢轴值
		qSort(arr,low,pivot-1);    // 对pivot左边进行递归排序
		qSort(arr,pivot+1,high);   // 对pivot右边进行递归排序
	}
	return arr;
}
// 计算枢轴值
function partition(arr,low,high){
	var pivotkey = arr[low];   // 用子表的第一个记录做枢轴记录
	while(low < high){
		// 元素从后往前与枢轴元素进行比较，大的话索引递减；小的话进行交换
		while(low < high && arr[high] >= pivotkey){
			high --;
		}
		swap(arr,low,high);    // 将比枢轴小的记录换到低端
		// 元素从前往后与枢轴元素进行比较，小的话索引递增；大的话进行交换
		while(low < high && arr[low] <= pivotkey){
			low ++;
		}
		swap(arr,low,high);   // 将比枢轴大的记录换到高端
	}
	return low;    // 返回枢轴所在的位置
}
// 交换元素
function swap(arr,i,j){
	var tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}
var num = [2,12,4,56,11,7,21,9,34,16];
console.log(quickSort(num));    // [2, 4, 7, 9, 11, 12, 16, 21, 34, 56]

快速排序性能评估

  • 稳定性：不稳定（关键字的比较和交换都是跳跃进行的）
  • 时间复杂度
    （1）最好的情况：O(nlogn)；
    （2）最坏的情况：O(n^2)；
    （3）平均的情况：O(nlogn)；
  • 空间复杂度：O(nlogn)；
  • 算法本身的复杂度：复杂；

以上代码只是最基本的快速排序法，书中还记录了 4 种优化方案，分别为：优化选取枢轴、优化不必要的交换、优化小数组时的排序方案、优化递归操作，这里不一一详细展开，如果有需要，可以查询《大话数据结构》P422 “快速排序优化” 一节。

排序算法总结

分类

以上 7 种排序算法均属于内排序，本文不涉及外排序；

按照借助的主要操作，可以进行如下分类：
排序分类

性能对比

排序方式 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(n^2) O(1) 稳定
插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
希尔排序 O(nlogn)~O(n^2) O(n^(3/2)) O(1) O(1) 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
快速排序 O(nlogn) O(nlogn) O(n^2) O(logn)~O(n) 不稳定
  • 从平均情况来看，最后 3 种改进算法要胜过希尔排序，并远远超过前 3 种简单算法；
  • 从最好情况来看，冒泡和插入排序算法要比其他算法更胜一筹，也就是说如果待排序的序列基本有序，则可以选择这两种排序算法；
  • 从最坏情况来看，堆排序和归并排序要由于快速排序以及其他简单排序；
  • 从空间复杂度来看，除了归并排序和快速排序之外，其余算法对辅助空间的要求一致，都是 O(1)；如果排序过程中，对空间复杂度有要求，则建议选前面的 5 种排序算法；
  • 从稳定性来看，改进算法中，只有归并排序是稳定的，而简单排序都是稳定的；
  • 从待排序的记录的个数看，如果待排序的个数 n 越小，则采用简单排序算法比较合适；如果待排序的个数 n 越大，则采用改进排序算法更合适。
您的支持将鼓励我继续创作！