数组排序在日常编程中用到的其实还是比较多的，比如把一组数据按时间排序，按首字母排序，按大小排序等等，那么就让我们一起来了解下常见的数组排序方法有哪些。
一说到数组排序，很多人脑子里第一时间蹦出来的可能就是sort()方法。那我们就从这个原生的排序方法sort()开始讲起。
语法：arrayObject.sort(sortby)
这里的sortby是一个参数，规定排序的顺序，必须是函数。
sort()的返回值是对该数组的引用，这里要注意的是，该排序方法会在原数组上直接进行排序，并不会生成一个排好序的新数组。
还要注意的是：如果没有使用参数sortby，那么排序的时候将会按字母的顺序对数组中的元素进行排序，说精确点是按照字符编码的顺序进行排序。如果要实现这一点，首先应该把数组的元素都转化成字符串，以便进行比较。
如果想按照其他标准排序，那么就要传入参数sortby，即提供比较函数。该函数要比较两个值，然后返回一个用于说明这两个值的相对顺序的数字。比较参数应该具有两个参数a和b，其返回值如下：
若a小于b，在排序后的数组中，a应该出现在b之前，则返回一个小于0的值
若a=b，则返回0
若a大于b，则返回一个大于0的值
我们先来看两个例子，第一个不传入参数sortby，代码如下：
var arr = ["Zhangsan", "Lisi", "Wangwu", "Hanmei", "Chendu"];
var res = arr.sort();
console.log(res);
// 打印结果为["Chendu", "Hanmei", "Lisi", "Wangwu", "Zhangsan"]
那么如果数组元素是数字呢？看如下代码：
var arr = [524, 684, 5, 69, 15];
var res = arr.sort();
console.log(res);
// 打印结果为[15, 5, 524, 684, 69]
由上面的代码可以看到，如果数组元素为数字的话，排序并不会按大小顺序排，而是会按数字的第一个字符排序。
如果我们想要这组数字按从小到大，或者从大到小的顺序排列的话，那么我们就需要传入参数sortby，即上文所说的比较函数。
function sortNum(a, b) {
return a - b;
}
var arr = [524, 684, 5, 69, 15];
var res = arr.sort(sortNum);
console.log(res);
// 打印结果为[5, 15, 69, 524, 684]
上面代码中的sortNum就是一个比较函数，我们传入a,b两个值，然后返回a-b的值，跟据返回值进行大小排序，如果想要从大到小排序，只需要return b-a即可。
这里额外提一下reverse()这个方法，这个方法用于颠倒数组中元素的顺序。这里要注意，只是颠倒，并不是按从大到小的顺序，因此我认为它算不上是排序方法。
语法：arrayObject.reverse()
demo代码如下：
var arr = [524, 684, 5, 69, 15];
var res = arr.reverse();
console.log(res);
// 打印结果为[15, 69, 5, 684, 524]
除了我们常用的sort()方法，其实还有其他很多方法可以实现排序：
冒泡排序
快速排序
插入排序
希尔排序
选择排序（坑未填）
归并排序（坑未填）
堆排序（坑未填）
一、冒泡排序
冒泡排序就是遍历数组里面的元素，一次比较两个元素，如果它们的顺序错误，就把它们交换过来，直到没有需要交换的两个元素为止。它是一种稳定排序算法。
冒泡排序算法的运作如下：（从后往前）
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
——引用自百度百科《冒泡排序》
function bubbleSort(arr) {
for(var i = 0; i < arr.length; i++) {
for(var j = 0; j < arr.length; j++) {
if(arr[i] < arr[j]) {
var temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
return arr;
}
var arr = [524, 684, 5, 69, 15];
bubbleSort(arr); // 结果为[5, 15, 69, 524, 684]
上面的代码就是一个很好理解的冒泡排序写法，采用两个for循环，当i=0的时候，将arr[0]与数组里面的每一项比较，如果arr[0]小于某一项，则替换它们的位置，以此类推。
二、快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的过程大致分三步：
在数据集之中，选择一个元素作为"基准"（pivot）。
所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
——引用自阮一峰博客《快速排序的JavaScript实现》
封装代码如下：
function quickSort(arr) {
if(arr.length <= 1) {
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
// splice()返回的是被删除元素组成的数组
var lef = [];
var rig = [];
for(var i = 0; i < arr.length; i++) {
if(arr[i] < pivot) {
lef.push(arr[i]);
}
else {
rig.push(arr[i]);
}
}
return quickSort(lef).concat(pivot, quickSort(rig)); // 递归
}
var arr = [524, 684, 5, 69, 15];
quickSort(arr); // 结果为[5, 15, 69, 524, 684]
三、插入排序
已知一个已有序的数据序列，需要插入一个数据，要求插入数据后这个序列依然有序，那么这个时候就需要使用插入排序。
插入排序把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
用生活中比较好理解的事物就是斗地主，你手里的牌已经排好序了，摸一张新牌，要将其插入进去，小的牌会往前插，大的牌会往后插。
封装代码如下：
function insertSort(arr) {
for(var i = 1; i < arr.length; i++) {
if(arr[i] < arr[i - 1]) {
var temp = arr[i];
var j = i -1;
arr[i] = arr[j];
while(j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
}
var arr = [524, 684, 5, 69, 15];
insertSort(arr);
console.log(arr); // 结果为[5, 15, 69, 92, 524, 684]
如果你是需要在现有的已排好序的数组中插入新的元素，并且新数组也依然排好序，那么上面的代码就需要修改一下：
function insertSort(arr, a) {
for(var i = 1; i < arr.length; i++) {
if(arr[i] >= a) {
for(var j = arr.length; j > i; j--) {
arr[j] = arr[j - 1];
}
arr[i] = a;
break;
}
}
return arr;
}
var arr = [5, 15, 69, 524, 684];
insertSort(arr, 92); // 结果为[5, 15, 69, 92, 524, 684]
对于小型数组的排列，插入排序要比前两种排序方法性能更好。
四、希尔排序
希尔排序是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
——引用自百度百科《希尔排序》
封装代码如下：
function shellSort(arr) {
var gap = Math.ceil(arr.length / 2);
while(gap > 0) {
for(var k = 0; k < gap; k++) {
var tagArr = [];
tagArr.push(arr[k]);
for(var i = k + gap; i < arr.length; i = i + gap) {
var temp = arr[i];
tagArr.push(temp);
for(var j = i - gap; j > -1; j = j - gap) {
if(arr[j] > temp) {
arr[j + gap] = arr[j];
}
else {
break;
}
}
arr[j + gap] = temp;
}
}
gap = parseInt(gap / 2);
}
return arr;
}
var arr = [524, 684, 5, 69, 15];
shellSort(arr); // 结果为[5, 15, 69, 92, 524, 684]
网友评论