几种基本的排序算法总结

准备函数

var arr = [] function swap(arr, a, b) { //交换函数 var temp = arr[a] arr[a] = arr[b] arr[b] = temp } function random_arr (){ //生成随机数组的函数 let long = Math.floor(Math.random()*100+1) for(var x = 0; x < long; x++) { arr.push(Math.floor(Math.random()*100)) } console.log(arr) } random_arr()

冒泡排序

算法思路:

遍历数组, 将相邻两个数之间两辆比较, 如果前面的数比后面的数大, 就交换位置, 然后继续将这个数跟后面相邻的数比较如果前面的数比后面的数小, 就用下一个数跟后面相邻的数继续比较

function bubble(arr) { for(var i = arr.length-1; i >= 0; i--) { for(var j = 0; j <= i; j++) { if(arr[j] > arr[j+1]) { swap(arr, j, j+1) } } } console.log(arr) } bubble(arr)

选择排序

算法思路:

将第一个数与后面的没一个数进行比较, 如果有存在比第一个数小的数, 则交换位置, 然后用这个较小数继续之前的位置向后比较, 经过一圈遍历后, 数组第一位的数就是跟个数组的最小值, 然后在用第二个数跟后面的所有数一次比较进行上述操作

function chose(arr) { for(var i = 0; i<arr.length; i++) { for(var j = i+1; j<arr.length; j++) { if(arr[i] > arr[j]) { swap(arr, i, j) } } } console.log(arr) } chose(arr)

插入排序

算法思路:

遍历整个数组, 将遍历项与其之前的项从后往前做比较, 如果他前面的数大于遍历项, 则交换位置, 直到他前面的数小于遍历项为止

function fuck_sort(arr) { for(var i = 1; i < arr.length; i++) { for (var j = i; j > 0; j--) { if(arr[j]<arr[j-1]) { swap(arr, j, j-1) } } } console.log(arr) } fuck_sort(arr)

归并排序

算法思路:

将一个数组, 对半分割, 递归执行, 直到被分割后的数组只剩下一个数, 然后利用外排的方式将分割好的数组进行排序然后复写到原数组中

function guibing(arr,low,height) { var mid = low+Math.floor((height-low)/2) if(low === height) { return } guibing(arr, low, mid) guibing(arr, mid+1, height) sort(arr, low, height, mid) } function sort(arr, low, height, mid) { var temp = [] var p1 = low var p2 = mid+1 while (true){ if (arr[p1] >= arr[p2]) { temp.push(arr[p2++]) }else { temp.push(arr[p1++]) } if(p1 > mid) { for(var j = p2; j <= height; j++) { temp.push(arr[j]) } break } if(p2 > height) { for(var j = p1; j < mid+1; j++) { temp.push(arr[j]) } break } } for(var i = 0; i <= temp.length-1; i++) { arr[i+low] = temp[i] } } guibing(arr, 0, arr.length-1) console.log(arr)

或者

function guibing2(arr) { if(arr.length === 1) { return arr } var mid = Math.floor(arr.length/2) var left = arr.slice(0,mid) //slice()是数组截取方法 var right = arr.slice(mid, arr.length) return sort2(guibing2(left), guibing2(right)) } function sort2(left, right) { var temp = [] while(left.length > 0 && right.length > 0) { if(left[0] <= right[0]) { temp.push(left.shift()) }else { temp.push(right.shift()) } } return temp.concat(left).concat(right) //concat()是数组拼接方法 } console.log(guibing2(arr))

快速排序

算法思路:

在数组中随便找一个数做基准数, 将比这个基准数大的数放到这个数的右侧, 将比这个基准数小的数, 放到这个数的左侧, 然后在基准数的小于区和大于区继续递归执行上述操作

function range(arr, l, r) { var less = l - 1 var more = r while( l < more ) { if(arr[l] > arr[r]) { swap(arr, l, --more) }else if(arr[l] < arr[r]) { swap(arr, l++, ++less) }else { l++ } } swap(arr, r, more) return [less+1,more] } function quick(arr, l, r) { if(l < r) { var scale = range(arr, l, r) quick(arr, l, scale[0]-1) quick(arr, scale[1]+1, r) } } quick(arr, 0, arr.length-1) console.log(arr)

或者

function quick2(arr) { if(arr.length === 0 ) { return [] } var left = [] var right = [] var middle = [] var index =Math.round(Math.random()*(arr.length-1)) for(var i = 0; i<arr.length; i++) { if(arr[i] < arr[index]) { left.push(arr[i]) }else if(arr[i] > arr[index]) { right.push(arr[i]) }else { middle.push(arr[i]) } } return quick2(left).concat(middle).concat(quick2(right)) } console.log(quick2(arr))

堆排序

算法思路:

因为堆的结构就是一个完全二叉树, 所以我们可以把数组的结构也想象成一个完全二叉树, 首先将数组变成一个大根堆, 然后将数组的第一位与数组的最后一位进行交换, 将数组的遍历范围减少一位, 此时数组的最后一位就是最大值了, 然后再将二叉树的头节点, 跟其左右两孩子最大的那个作比较, 如果孩子节点大于父节点, 就交换位置, 然后利用原来的那个父节点继续跟左右孩子作比较,比较结束后, 又形成了一个大根堆, 继续将二叉树的头结点跟二叉树的倒数第二位作交换, 将数组的遍历范围再减少一位, 重复执行上述操作.

function dui_sort(arr) { dui(arr) var long = arr.length swap(arr, 0, --long) while(long > 0) { var j = 0 var left = j*2+1 while(left<long) { largest = left+1<long && arr[left+1] >arr[left] ? left+1 : left largest = arr[largest] > arr[j] ? largest : j if(largest === j) { break } swap(arr, largest, j) j = largest left = j*2+1 } swap(arr, 0, --long) } } function dui(arr) { for(var i = 0; i < arr.length; i++) { var j = i while (arr[j] > arr[Math.floor((j-1)/2)]) { swap(arr, j, Math.floor((j-1)/2)) j = Math.floor((j-1)/2) } } } dui_sort(arr) console.log(arr)