目录：
1.冒泡排序
2.选择排序
3.插入排序
4.归并排序
5.快速排序
6.堆排序
冒泡排序
冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序。
function bubbleSort(arr){
var len = arr.length;
for(var i=0;i<len;i++){
for(var j=0;j<len-1-i;j++){ //内循环减去外循环中已跑过的次数，可以避免内循环中所有不必要的比较
if(arr[j]>arr[j+1]){
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
}
console.log(arr);
}
测试：
bubbleSort([9,8,7,6,5,4,3,2,1]); //[1,2,3,4,5,6,7,8,9]
时间复杂度：O(n²)
选择排序
选择排序算法是一种原址比较算法。选择排序的思路是：找到数据结构中最小值并将其放置在第一位，接着找到第二小的值将其放在第二位，依此类推。
function selectionSort(arr){
var len = arr.length;
var index = null;
for(var i = 0; i< len - 1;i++){
index = i;
for(var j = i;j<len;j++){
if(arr[index] > arr[j]){
index = j;
}
}
if(i != index){
[arr[i], arr[index]] = [arr[index], arr[i]];
}
}
console.log(arr);
}
测试：
selectionSort([2,1,3,5,8,6,7,3]); //[ 1, 2, 3, 3, 5, 6, 7, 8 ]
时间复杂度：O(n²)
插入排序
插入排序每次排一个数组项，以此方式构建最后的排序数组。假如第一项已经排序好了，接着，它和第二项进行比较，第二项是应该呆在原位置，还是插入到第一项之前呢？这样前两项就已正确排序，接着和第三项比较，依此类推。
function insertSort(arr){
var len = arr.length,
j,
temp;
for(var i = 1; i<len;i++){
j = i;
temp = arr[i];
while(j>0&&arr[j-1] > temp){
arr[j] = arr[j-1];
j--;
}
arr[j] = temp;
}
console.log(arr);
}
测试：
insertSort([1,3,2,7,5,9,2]); //[ 1, 2, 2, 3, 5, 7, 9 ]
时间复杂度：O(n²)
插入排序在排序小型数组时，比选择排序和冒泡排序的性能要好
归并排序
归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完成的大数组。
function mergeSort(arr){
mergeSortRec(arr)
}
function mergeSortRec(arr){
var len = arr.length;
if(len === 1){ //递归终止条件
return arr;
}
var mid = Math.floor(len / 2);
var left = arr.slice(0, mid);
var right = arr.slice(mid, len);
return merge(mergeSortRec(left), mergeSortRec(right));
}
function merge(left, right){
var res = [];
var le = 0;
var re = 0;
while(le<left.length && re<right.length){
if(left[le] < right[re]){
res.push(left[le++]);
}
else{
res.push(right[re++]);
}
}
while(le < left.length){
res.push(left[le++]);
}
while(re < right.length){
res.push(right[re++]);
}
console.log(res);
return res;
}
测试：
var array = [1,3,2,6,4,8,5];
mergeSort(array);
输出：
[2,3]
[1,2,3]
[4,6]
[5,8]
[4,5,6,8]
[1,2,3,4,5,6,8]
时间复杂度：O(nlogn)
快速排序
和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组。
(1)首先，从数组中选择中间一项作为主元；
(2)创建两个指针，左边一个指向数组的第一项，右边一个指向数组的最后一项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素。然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，比主元大的值都排在主元之后。这一步叫做划分操作。
(3)接着，算法对划分后的小数组重复之前的两个步骤，直至数组已完全排序。
function quickSort(arr){
quick(arr, 0, arr.length-1);
console.log(arr);
}
function quick(arr, left, right){
var index;
if(arr.length > 1){
index = partition(arr, left, right);
if(left < index-1){
quick(arr, left, index-1);
}
if(index < right){
quick(arr, index, right);
}
}
}
function partition(arr, left, right){
var p = arr[Math.floor((left+right) / 2)],
i = left,
j = right;
while(i <= j){
while(arr[i] < p){
i++;
}
while(arr[j] > p){
j--;
}
if(i <= j){
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
j--;
}
}
return i;
}
时间复杂度：O(nlogn)
理解了上面的代码，就可以看下面的简洁版了
function quickSort(arr,l,r){
if(l < r){
var i = l, j = r, x = arr[i];
while(i<j){
while(i<j && arr[j]>x)
j--;
if(i<j)
//这里用i++，被换过来的必然比x小，赋值后直接让i自加，不用再比较，可以提高效率
arr[i++] = arr[j];
while(i<j && arr[i]<x)
i++;
if(i<j)
//这里用j--，被换过来的必然比x大，赋值后直接让j自减，不用再比较，可以提高效率
arr[j--] = arr[i];
}
arr[i] = x;
quickSort(arr, l, i-1);
quickSort(arr, i+1, r);
}
}
堆排序
堆排序也是一种很高效的算法，它把数组当作二叉树来排序。它将数组当作二叉树来管理：
(1)索引0是树的根节点
(2)除根节点外，任意节点N的父节点是N/2
(3)节点L的左子节点是2L
(4)节点R的右子节点是2R+1
function heapSort(arr){
var heapSize = arr.length;
buildHeap(arr);
while(heapSize > 1){
heapSize--;
[arr[0], arr[heapSize]] = [arr[heapSize], arr[0]];
heapify(arr, heapSize, 0);
}
console.log(arr);
}
function buildHeap(arr){
var heapSize = arr.length;
for(var i = Math.floor(arr.length / 2); i >= 0; i--){
heapify(arr, heapSize, i);
}
}
function heapify(arr, heapSize, i){
var left = i*2 + 1,
right = i*2 + 2,
largest = i;
if(left < heapSize && arr[left] > arr[largest]){
largest = left;
}
if(right < heapSize && arr[right] > arr[largest]){
largest = right;
}
if(largest !== i){
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, heapSize, largest);
}
};
测试：
heapSort([2,4,1,3]); //[ 1, 2, 3, 4 ]
时间复杂度：O(nlogn)
转载自https://blog.csdn.net/q1312882392/article/details/99051748
网友评论