对这几个基础排序算法进行梳理,便于以后查看。

/**
*
* 冒泡排序
* 从末尾开始相邻两数相互比较大小,满足条件就交换位置。循环每进行一次,即可确定第i位数的值。
*冒泡排序的时间复杂度为O(n^2)。
*
*/
function bubbleSort(arr){
if(arr == null || arr.length == 0) return;
for(var i =0 ; i < arr.length-1 ;i++){ //比较n-1次即可
for(var j = arr.length-1 ; j>i ;j--){
if(arr[j] < arr[j-1]){ var temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
console.log(arr);
} /**
*
*选择排序
*第i次循环,将arr[i]与后面的数比较,用它后面最小的数和它交换。
*选择排序的时间复杂度为O(n^2)
*/
function selectSort(arr){
if(arr == null || arr.length == 0) return;
for(var i = 0 ; i < arr.length-1 ;i++){
var minIndex = i;
for(var j = i + 1; j < arr.length ; j++){
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
if(minIndex !== i){
var temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp; }
}
console.log(arr);
} /**
*
*插入排序
*以第一个数为参照,将第i个数拿出,对第i个数前面的数整理好顺序后,将arr[i]插入正确位置。
*简单插入排序的时间复杂度也是O(n^2)。
*/ function insterSort(arr){
if(arr == null || arr.length == 0) return;
for(var i = 1; i < arr.length ; i++){
var j = i;
var target = arr[i]; //插入值
while(j > 0 && target < arr[j-1] ){
arr[j] = arr[j-1];
j --;
}
arr[j] = target;
}
console.log(arr);
}
/*
var a = [15,8,14,2,6];
insterSort(a);
运行过程
i = 1 8 15 14 2 6
i = 2 8 14 15 2 6
i = 3 target = 2
数组变化过程: 8 14 15 15 6
8 14 14 15 6
8 8 14 15 6
arr[0] = target 插入
2 8 14 15 6 i = 4 .....
*/ /**
*快速排序
*这是阮一峰的版本,很直观,感觉写得相当棒!
* (1)在数据集之中,选择一个元素作为"基准"(pivot)。
*
*  (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右
* 边。
*
*  (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素* 为止。
* 快速排序是不稳定的,其时间平均时间复杂度是O(nlgn)。
*/
var quickSort = function(arr) {if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right =[];
for(var i = 0; i < arr.length; i++){
if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
} //快排还有一种更简便的写法 function quicksort(arr)
{
if (arr.length == 0)
return []; var left = new Array();
var right = new Array();
var pivot = arr[0]; for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
} return quicksort(left).concat(pivot, quicksort(right));
}
05-07 15:15