JavaScript简易排序算法及简易优化
JavaScript简易排序算法及简易优化
快速排序
原理:在待排序序列中选一个分割元素,将待排序序列分隔成独立的子序列,子序列1里的元素比分割元素元素都小(大),子序列2反之,递归进行此操作,以达到子序列都有序。最后将子序列用concat方法连接起来即是排序好的序列。
function quickSort(arr){ if(arr.length tmp){ arr[j] = arr[j-1]; --j; } arr[j] = tmp; } return arr;}console.log(insertSort([1,45,43,4,56,7,20,1]));//[1, 1, 4, 7, 20, 43, 45, 56]
优化:二分插入排序(在有序序列中使用二分查找法查找一个插入位置,减少元素比较次数)和希尔排序(把序列分为很多小序列,对小序列直接插入排序,最后再整个插入排序)(下面演示二分插入排序)
function binaryInsertSort(arr){ var len = arr.length; if(len = left; j--) { arr[j + 1] = arr[j]; } arr[left] = tmp; } return arr;}console.log(binaryInsertSort([1,45,43,4,56,7,20,1,2,3,4,56,3]));//[1, 1, 2, 3, 3, 4, 4, 7, 20, 43, 45, 56, 56]
选择排序
原理:在待排序序列中找到最小(大)元素,放在序列的起始位置,然后,再从剩余元素中寻找最小(大)元素,然后放到已排序序列的末尾。重复,直到所有元素均排序完毕。
Array.prototype.selectionSort = Array.prototype.selectionSort || function(){ var len = this.length; if(len = 0; i--) { maxHeapify(arr, i, arr.length); } } function sort(arr) { buildMaxHeap(arr); for (var i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); maxHeapify(arr, 0, i); } return arr; } return sort(arr);}console.log(heapSort([1,45,43,4,56,7,20,1,2,3,4,56,3]));//[1, 1, 2, 3, 3, 4, 4, 7, 20, 43, 45, 56, 56]
冒泡排序
原理:从第一个元素开始,一次比较两个元素,如果arr[n]大于arr[n+1],就交换。重复遍历直到没有再需要交换,排序完成。
function bubbleSort(arr){ var len = arr.length; if(len i ; j--) { if (arr[j-1] > arr[j]) { var temp = arr[j-1]; arr[j-1] = arr[j]; arr[j] = temp; bSwaped = true; } } // 如果上一次扫描没有发生交换,则说明数组已经全部有序,退出循环 if (!bSwaped){ break; } } return arr;} console.log(bubbleSort([1,45,43,4,56,7,20,1]));//[1, 1, 4, 7, 20, 43, 45, 56]
学习来源:常用排序算法 ; 堆排序 ; 冒泡优化
关键字:JavaScript, arr, var, 排序
版权声明
本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符,请点击 举报 进行投诉反馈!