常用数组排序
本文主要汇总一维数组排序相关的方法，以升序为例。
一、冒泡排序
步骤： 1、两个for遍历，使用两个指针，外循环i指针，内循环j指针 2、对比两个指针指向的元素大小，如果i>j,则进行值交换
代码如下：
javascript
let bubbleSort = function (arr) {
//双指针
for(let i = 0; i<arr.length; i++) {
for(let j = i+1 ; j<arr.length;j++)
if(arr[i] > arr[j]){
let t = arr[i]
arr[i] = arr[j]
arr[j] = t
}
}
return arr
}let bubbleSort = function (arr) {
//双指针
for(let i = 0; i<arr.length; i++) {
for(let j = i+1 ; j<arr.length;j++)
if(arr[i] > arr[j]){
let t = arr[i]
arr[i] = arr[j]
arr[j] = t
}
}
return arr
}二、快速排序
步骤： 1、如果数组长度小于等于0则返回该数组 2、先提取中间值，把小于中间值的元素放在左数组，其他的放在右数组 3、递归重复第二步，用Array.prototype.concat合并数组
代码如下：
javascript
let quickSort = function (arr) {
if(arr.length <= 0 ) {
return arr
}
let midIdx = Math.floor(arr.length / 2)
let mid = arr.splice(midIdx, 1)[0]
let left = []
let right = []
for(let i = 0; i<arr.length; i++) {
if(arr[i] <mid){
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat([mid],quickSort(right))
}let quickSort = function (arr) {
if(arr.length <= 0 ) {
return arr
}
let midIdx = Math.floor(arr.length / 2)
let mid = arr.splice(midIdx, 1)[0]
let left = []
let right = []
for(let i = 0; i<arr.length; i++) {
if(arr[i] <mid){
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat([mid],quickSort(right))
}三、插入排序
步骤： 1、遍历数组 2、保存当前i指针指向的元素，用prev指针来遍历当前对象之前的元素 3、前一元素大于当前元素时，把较大值后移一个，与再前一项去对比，找到比当前元素小的元素时停止 4、将prev指针指向当前元素
代码如下：
javascript
let insertSort = function (arr) {
let current , prev
for(let i = 1; i<arr.length ; i++) {
current = arr[i]
prev = i -1
while(prev >= 0 && current<arr[prev]) {
arr[prev+1] = arr[prev]
//prev指针前移
prev--
}
arr[prev+1] = current
}
return arr;
}let insertSort = function (arr) {
let current , prev
for(let i = 1; i<arr.length ; i++) {
current = arr[i]
prev = i -1
while(prev >= 0 && current<arr[prev]) {
arr[prev+1] = arr[prev]
//prev指针前移
prev--
}
arr[prev+1] = current
}
return arr;
}四、es6方法
sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的UTF-16代码单元值序列时构建的。
要比较数字而非字符串，比较函数可以简单的以 a 减 b，如下的代码将会将数组升序排列
javascript
function sort(arr) {
if(arr.length <= 0){
return arr
}
return arr.sort((a,b)=>a-b)
}function sort(arr) {
if(arr.length <= 0){
return arr
}
return arr.sort((a,b)=>a-b)
}