排序算法（Sort）
引言
我们平时对计算机中存储的数据执行的两种最常见的操作就是排序和查找，对于计算机的排序和查找的研究，自计算机诞生以来就没有停止过。如今又是大数据，云计算的时代，对数据的排序和查找的速度、效率要求更高，因此要对排序和查找的算法进行专门的数据结构设计，（例如我们上一篇聊到的二叉查找树就是其中一种），以便让我们对数据的操作更加简洁高效。
这一篇我们将会介绍一些数据排序的基本算法和高级算法并利用JavaScript来逐一实现，让大伙对计算机中常见的排序算法的思想和实现有基本的了解，起到一个抛砖引玉的作用。
关于排序算法的说明
在介绍各个算法之前，我们有必要了解一下评估算法优劣的一些术语：
稳定：如果a原本在b前面，当a=b时，排序之后a仍然在b的前面
不稳定：如果a原本在b的前面，当a=b时，排序之后a可能会出现在b的后面
内排序：所有排序操作都在内存中完成
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小
有想要了解更多，关于时间空间复杂度的，我推荐一篇文章，请戳这里
基本排序算法
基本排序算法的核心思想就是对一组数据按照一定的顺序重新排序，其中重排时一般都会用到一组嵌套的 for 循环，外循环会遍历数组的每一项元素，内循环则用于进行元素直接的比较。
1.冒泡排序（BubbleSort）
冒泡排序是比较经典的算法之一，也是排序最慢的算法之一，因为它的实现是非常的容易的。
冒泡排序的算法思想如下（升序排序）：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样最终最大数被交换到最后的位置
- 除了最后一个元素以外，针对所有的元素重复以上的步骤
- 重复步骤1~3，直到排序完成
下面我借用网上一张动图，来展示冒泡排序的过程：
排序时间比较
高级排序算法
4.希尔排序（Shell Sort）
我们首先要学习的就是希尔排序，又称缩小增量排序，这个算法是在插入排序的基础上做了很大的改善，与插入排序不同的是，它首先会比较位置较远的元素，而非相邻的元素。这种方案可以使离正确位置很远的元素能够快速回到合适的位置，当算法进行遍历时，所有元素的间距会不断的减小，直到数据的末尾，此时比较的就是相邻元素了。
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上有较大提高。
好吧，我还是用个案例来解释，这样会更清晰，我们以下面一组数据为例：
数据集
- 第一次 gap(增量) = 10 / 2 = 5 , 会按照下面进行分组得到五组数据（49，13）、（38，27）、（65，49）、（97，55）、（26，4），这样进行组内排序之后（13，49）、（27，38）、（49，65）、（55，97）、（4，26）
第一次分组
此时，数据会排成如下结构
第一次排序
- 第二次 gap = 5 / 2 = 2 , 此时可以得到两个分组，如下
第二次分组
再通过组内排序之后，可以得到
第二次排序
- 第三次 gap = 2 / 2 = 1 ， 即不用分组，进行排序后
第三次排序
- 第四次 gap = 1 / 2 = 0 ，即可得到排序完成的数组
排序完成
现在，可能对希尔排序有了一定得了解了，用JS实现如下：
//希尔排序
function shallSort(array) {
var increment = array.length;
var i
var temp; //暂存
do {
//设置增量
increment = Math.floor(increment / 3) + 1;
for (i = increment ; i < array.length; i++) {
if ( array[i] < array[i - increment]) {
temp = array[i];
for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
array[j + increment] = array[j];
}
array[j + increment] = temp;
}
}
}
while (increment > 1)
return array;
}
效果如下：
console.log( '原始数据:' + dataStore );
console.log( '希尔排序:' + shallSort( dataStore) );
// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希尔排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
5.归并排序（Merge Sort）
将两个的有序数列合并成一个有序数列，我们称之为"归并"，归并排序的思想就是将一系列排序好的子序列合并成一个大的完整有序的序列。
实现步骤如下：
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列
一张动图来说明归并排序的过程：
快速排序
具体实现如下：
//快速排序
function quickSort( arr ){
if ( arr.length == 0) {
return [];
}
var left = [];
var right = [];
var pivot = arr[0];
for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push( arr[i] );
} else {
right.push( arr[i] );
}
}
return quickSort( left ).concat( pivot, quickSort( right ));
}
测试结果如下：
console.log( '原始数据:' + dataStore );
console.log( '快速排序:' + quickSort( dataStore) );
// 原始数据:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 快速排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99
至此，我们已基本介绍过一些常见的排序算法的思想和具体实现（基数排序在之前的文章已经介绍过，想要了解戳这里），排序算法博大精深，我们不仅要学习理论，也要不断去实践，大家加油！
网友评论