【JS】几种常见的排序方法（JS实现）

前言

就几种常见的排序算法用js语言实现： 冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，桶排序。

排序总结
【JS】几种常见的排序方法（JS实现）

下面就来进入主题吧

冒泡排序

思想：每次都在未排序的序列中找到最大（小）元素，放在末尾：方法是与相邻元素比较，决定是否交换。
时间复杂度：O(nn) ，因为两个for循环：O(n）O(n)

var  bubbleSort = function(arr){
for(let i=0; i < arr.length-1; i++){ //i表示趟数
for(let j=0; j < arr.length-1-i; j++){ //还未排序的数量
if(arr[j+1] < arr[j]){  //与相邻元素比较
[arr[j],arr[j+1]] = [arr[j+1], arr[j]]      // ES新特性
}
}
}
return arr
}

选择排序

思想：从未排序的序列中找到最大（小）元素放在排序序列的末尾，作为已排序的一员。然后接着找当前未排序元素的最大（小）

var selectSort = function (arr) {
for(let i = 0; i < arr.length-1; i++){ //趟数
let min  = arr[i]
let curIndex = i    //  保存要交换位置的索引值
for( let j = i; j < arr.length ; j++ ){
if( arr[j] < min ){
min = arr[j]
curIndex = j
}
}
[arr[curIndex], arr[i]] = [arr[i], arr[curIndex]] //交换
}
return arr
}

插入排序

思想：分为两组：左边为有序，右边为无序，在右边序列里每找到一个，跟左边已排序部分倒序地进行比较，把它插入到前面已排序的组中

var insertSort = function(arr){
var preIndex =0  //当前访问的元素的前一个索引
for(var i=1; i<arr.length; i++){
var temp = arr[i]
preIndex = i-1
while(preIndex >= 0 && temp < arr[preIndex] ) { //若当前值小于前面的值，则交换，继续向前比较。这时候不能再用arr[i],应该用temp
arr[preIndex+1] = arr[preIndex]
preIndex -= 1
}
arr[preIndex+1] = temp  //找到了要插入的位置
}
return arr;
}

希尔排序

思想：是变形的插入排序，利用插入排序在基本有序的情况下时间复杂度低。

var shellSort = function(arr){
var len =arr.length, temp, gap =1;
while(gap< len/3){
gap=gap*3  +  1
}  //确定gap，根据arr的长度
for( gap; gap>0; gap =Math.floor(gap/3)){
/**
* 可以替换掉下面这个for循环
*  for(var i= gap; i<len; i++){
*      temp = arr[i]
*      for(var preIndex = i-gap ;preIndex >=0 && arr[preIndex]> temp ; preIndex -=gap){
*          arr[preIndex + gap]= arr[preIndex]
*      }
*      arr[preIndex +gap]= temp
*  }
*/
for(var i =gap; i<len; i++){
temp = arr[i]
preIndex =i -gap
while(preIndex >=0 && arr[preIndex]> temp){
arr[preIndex + gap]= arr[preIndex]
preIndex -= gap
}
arr[preIndex +gap]= temp
}
}
return arr
}

快排

//令人头疼，知道思路，但是写起来确实有点费事，这个方式跟阮一峰老师的有点差别，这是就地排序，没有占用其他空间。
//递归算法
var quickSort = function (arr, left, right ) {
let target = arr[left]
let i =left ,j =right;  //
if(left > right){  //特别注意这点
return;
}
while( i !== j){
while(arr[j]>= target && i<j){
j--
}
while(arr[i]<= target && i<j){
i++
}
if(i<j){
[arr[i],arr[j]] = [arr[j],arr[i]]
}
}
arr[left] =arr[i]
arr[i]= target
// 这里的left和下面的right
quickSort(arr,left,i-1)
quickSort(arr,i+1,right)
return arr
}

归并排序

思想：先将数组拆分成几个小的组，然后合在一起

var merge = function(left, right) {  //合并两个有序数组
var result = [];
while(left.length && right.length){
if(left[0] > right[0]){ //每次选取left和right数组中最小的元素进入result
result.push(right.shift()) //做了两个操作1.删除right中最小的元素 2.将最小的元素放入result中
} else{
result.push(left,shift())
}
}
return result.concat(right,left)  //将left或者right中剩下的元素一起放入result中
}
var mergeSort = function(arr){
//判断长度
if(arr.length<=1){
return arr
}
var mid = Math.floor(arr.length/2)
var left = arr.slice(0,mid)
var right = arr.slice(mid)
return merge(mergeSort(left),mergeSort(right))
}

桶排序

思想：如有10个数字在1-100以内，设置10个桶，每个桶所能容纳的范围分别为1-10，11-20，...... ,91-100。
将这10个数字放在相应的桶中，放入同一个桶时采用插入排序，这样保证桶内也是有序的。整体桶也是有序，直接合并就行

var bucketSort1 = function (arr) {
var min = arr[0]
var max = arr[0]
var len = arr.length;
var sum = len;
var size = 0
var index;
for (var i = 0; i < len; i++) {
if (arr[i] > max) {
max = arr[i]
} else if (arr[i] < min) {
min = arr[i]
}
}
// 边界条件判断 ： min是否等于max，若等于，则无需排序
if (max != min) {
var bucket = new Array(len)
for (var i = 0; i < sum; i++) {  //把数组中的数分到各个桶中
index = Math.floor((arr[i] - min) / (max - min) * (sum - 1))
bucket[index] = new Array()  //这句定义数组。不能省略
bucket[index].push(arr[i])  //这个地方可以换位插入排序或者其他排序
}
for (var i = 0; i < sum; i++) {
if (bucket[i].length > 1) {
bucketSort1(bucket[i])
}
for (var j = 0; j < bucket[i].length; j++) {
arr[size++] = bucket[i][j]
}
}
}
return arr
}

参考

各种排序算法总结：https://www.jianshu.com/p/f5b...

以上是 【JS】几种常见的排序方法（JS实现） 的全部内容， 来源链接： utcz.com/a/98583.html

回到顶部