js数组排序⽅法总结
前⾔
这是第⼀次开通博客，写⼀些关于关于前端的知识总结，⽅便他⼈也⽅便⾃⼰忘的时候翻出来看看，希望⾃⼰可以⼀直坚持下去，如果⽂中有哪些不对的、需要改进的，欢迎⼤家批评指正
正⽂
⼀、冒泡排序
冒泡排序初级：
冒泡就是通过数组中相邻的两项进⾏⽐较，然后把数值⼤的项放到后⾯，从图⽰中可以看出从第⼀项开始⽐较⼀共⽐较了四次，也就是数组长度length-1，对应到代码就是解决两个问题：1.如何交换两个数组的值。2.确定for循环的次数。第⼀个问题我们通过设置⼀个中间媒介接收较⼤的值，第⼆个问题刚才已经讨论过了，就是数组长度的length-1，所以对应的代码如下：
// 设置⼀个中间值来保存较⼤的项的值
var medium = null;
for (var i = 0; i <= arr.length-1; i++) {
if (arr[i] > arr[i+1]) {
medium = arr[i];
arr[i] = arr[i+1];
arr[i+1] = medium;
}
}
但这只是从数组的第⼀项开始⽐较了⼀遍，后⾯还要从数组的第⼆项往后⽐较，然后是第三项，第四项，第五项就不需要在⽐较了，因为他是数组从第⼀项开始⽐较后的结果，已经是数组的最⼤值，所以这个循环还需要再嵌套⼀个循环中，循环次数即为数组长度的length-1对应的代码如下：
var medium = null;
for (var j = 0; j <= arr.length-1; j++) {
for (var i = 0; i <= arr.length-1; i++) {
if (arr[i] > arr[i+1]) {
medium = arr[i];
arr[i] = arr[i+1];
arr[i+1] = medium;
}
}
}
冒泡排序中级：
我们在对这个排序⽅法进⾏优化，看下⾯的图解：
这次⽐较中是从数组的第⼆项开始⽐较（第⼀项经过⽐较已经成为最后⼀项），这次⽐较的次数是3，对应的最外层循环是 j=1 ，再看下⾯，
这次⽐较是从数组的第三项开始⽐较，这次的⽐较次数是2，对应的外层循环是 j=2 ，所以不难发现内层循环对应的⽐较次数是 arr.length-1-j ，所以优化后代码如下：
var medium = null;
for (var j = 0; j <= arr.length-1; j++) {
for (var i = 0; i <= arr.length-1-j; i++) {
if (arr[i] > arr[i+1]) {
medium = arr[i];
arr[i] = arr[i+1];
arr[i+1] = medium;
}
}
}
冒泡排序⾼级版：
如果理解了上述两个⽅法，我们再来介绍⼀下终极版的冒泡排序，下⾯看⼀个数组的极端例⼦：
这已经是⼀个冒泡好的数组，在我们从⼈的思维来看，这个数组根本不需要排序，但计算机并不知道这个数组已经排好序了，在进⾏了内层循环的第⼀次后，我们是否可以给计算机⼀个判断条件让他去判断是否还要去进⾏外部的循环，所以我们做出⼀个假设，假设这个数组已经排好序了，然后我们让计算机去检测这个假设成不成⽴，如果数组排好序，那么必然有 arr[i+1]>arr[i] ，如果我们将数组遍历⼀遍不到推翻这个条件的例⼦，那么就可以⽴即结束外层循环，不必在进⾏下去，那么我们来看代码如何实现：
var medium = null;
for (var j = 0; j <= arr.length-1; j++) {
var flag = true;
for (var i = 0; i <= arr.length-1-j; i++) {
if (arr[i] > arr[i+1]) {
medium = arr[i];
arr[i] = arr[i+1];
arr[i+1] = medium;
flag = false
}
}
if (flag) {
break
}
}
⼆、快速排序
快速排序就是在数组中挑出中间项，然后定义两个空数组，让需要⽐较的数组⾥的项分别与这个中间项进⾏⽐较。把⼩于这个中间项的放到⼀个空数组⾥⾯，把⼤于这个中间项的放到⼀个空数组⾥⾯，然后使⽤递归重复这个过程。下⾯看代码的实现：
function quick(arr) {
if (arr.length<=1){return arr}
// 取数组的中间项的下标
var middleIndex = Math.floor(arr.length / 2);
// 取出数组的中间项，并把该项从数组中删除，且原数组受到影响
var middle = arr.splice(middleIndex,1)[0];
// 声明两个数组，分别⽤来存在⽐middle⼩和⼤的值
var leftArr = [];
var rightArr = [];
js数组方法总结
for (var i = 0; i < arr.length; i++) {
if (arr[i] <= middle) {
leftArr.push(arr[i])
} else if (arr[i] > middle) {
rightArr.push(arr[i])
}
}
// 使⽤递归，并把三个数组拼接起来
return quick(leftArr).concat([middle],quick(rightArr))
}
三、插值排序
插值排序，我个⼈感觉有些抽象，对象到现实中可以理解成打扑克牌，我们左⼿拿着已经排好的牌，右⼿去摸排，摸到的牌插到左⼿⾥⾯已经排好的牌，这次我们先上代码，然后我们在对应着代码按我理解的去解释，代码如下：
function insertSort(arr) {
//从第⼆个数开始，依次插⼊
for (var i = 1; i < arr.length; i++) {
//判断⽬标元素是否⼩于前⼀个元素
if (arr[i] < arr[i - 1]) {
var current = arr[i];
var j = i - 1;
//从有序数列从后往前对⽐，如果⽬标元素⼩于与之对⽐的当前元素，当前元素位置往后挪⼀位
while (j >= 0 && current < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
//插⼊
arr[j + 1] = current;
}
}
return arr;
}
⾸先是⼀个for循环，这⼀步的⽬的其实就是让数组整体从前往后开始⽐较，先看看数组的前⾯⼏项是不是是⼀个有序数组（就是你左⼿中的牌），在循环中我们突然到了⼀项，发现他⽐前⼀项要⼩，我们为了⽅便就管这⼀项取名为small，试想如果small加上前⾯的有序数组是不是就组成了⼀个⽆序数
组，所以我们就要想办法把这个small插⼊到这个有序数组⾥，让small在合适的位置与这个有序数组再次组成⼀个新的有序数组，那么这⾥就是对应到if()判断语句成⽴的条件，好的进⼊if循环，我们⽤⼀个变量也就是代码中的current去保存small的值，在⽤⼀个变量也就是j记录下来small前⼀项对应的下标，那我们就拿着这个current去和有序数组⾥⾯的每⼀个值去⽐较⽽且是从后往前⽐较，这⾥对应上了while循环体，只要有序数组⾥的项⽐⼤他就让这⼀项往后⼀移⼀位，即
arr[j + 1] = arr[j];
但也可以理解为没有后移，只不过是让后⾯⼀项等于了⾃⼰，然后我们还要继续从后往前⽐，所以 j-- ，直到出现small的值也就是current⼤于有序数组⾥的⼀项时。我们终于到了small要插⼊的位置，跳出while循环体，把small插到这⼀项的后⾯也就是 arr[j + 1] = current ，然后继续进⾏for循环，重复这个过程。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。