数组排序在日常编程中用到的其实还是比较多的,比如把一组数据按时间排序,按首字母排序,按大小排序等等,那么就让我们一起来了解下常见的数组排序方法有哪些。
一说到数组排序,很多人脑子里第一时间蹦出来的可能就是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]