总结下用js实现排序的几种普遍方法：
1. 冒泡排序
原理：
依次比较相邻的两个元素，如果后一个小于前一个，则交换，这样从头到尾一次，就将最大的放到了末尾。
平均时间复杂度：O(n^2)。
function bubbleSort(arr) {
var temp;
if(arr.length == 0 || arr == null) {
return arr;
}
// [1, 545, 55, 33, 23, 21, 3]
for(var i = 0; i < arr.length - 1; i++ ) {
for(j = 0; j < arr.length - i - 1; j++) {
if(arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
//bubbleSort([1,34,23,34543,12,544,2])
//[1, 2, 12, 23, 34, 544, 34543]
2. 选择排序
原理：
每次找一个最大或者最小的数排在最开始，让其他数与之比较，进而选择是否交换位置。
平均时间复杂度：O(n^2)。
function selectSort (arr) {
var length = arr.length,
i,
j,
k,
temp;
if( length === 0 || arr === null ) {
return arr;
}
for(i = 0; i < length - 1; i++) {
k = i; //标记最小数
for(j = i + 1; j < length; j++) {
if(arr[k] > arr[j]) {
k = j;
}
temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
}
return arr;
}
//selectSort([1,43,2,324,23,534,2])
//[1, 2, 2, 23, 43, 324, 534]
3. 插入排序
原理：
将元素插入到有序序列中，一般将第一个元素视为有序序列，插入元素视为待排序列，与第一个元素进行比较插入。
平均时间复杂度：O(n^2)。
function insertionSort (arr) {
var length = arr.length,
i,
j,
k,
preIndex, //当前元素的前一个元素的下标
current; //当前待排元素
if( length === 0 || arr === null ) {
return;
}
for(i = 1; i < length; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && current < arr[preIndex]) {
arr[preIndex+1] = arr[preIndex]; // 比current大的元素后移
preIndex--;
}
arr[preIndex+1] = current;//将current插入到数组中
}
return arr;
}
//insertionSort([23,34,2,43,3423,23,1123,3])
//[2, 3, 23, 23, 34, 43, 1123, 3423]
4. 快速排序
原理：
选择一个基准，将比基准小的，放在基准左边，将比基准大的，放在基准右边；一般选择中间的作为基准，之后两边再用递归的方法不断重复上述过程。
平均时间复杂度：O(nlog(n))。
function quickSort (arr) {
if( arr.length <= 1 ) {
return arr;
}
var left = [],
right = [],
i,
j,
k,
pivotIndex, // 参考点下标
pivot; //参考点
pivotIndex = Math.floor(arr.length / 2);
pivot = arr.splice(pivotIndex, 1)[0];//截取参考点
for(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)); //递归进行上述规则排序 最后返回数组
}
//quickSort([12,3,2,434,21,32,23,11])
//[2, 3, 11, 12, 21, 23, 32, 434]
未完待续
