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, 排序

版权声明

本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符,请点击 举报 进行投诉反馈!

相关文章

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部