js数组中的各种排序方法
冒泡排序
思路：重复遍历数组中的元素，依次比较两个相邻的元素，如果前一个元素大于后一个元素，就依靠第三个变量将它们换过来，直到所有元素遍历完。
function bubbleSort(arr){
for(let i = 0; i < arr.length - 1; i ++){
for(let j = 0; j < arr.length - 1 - i; j ++){
if(arr[j] > arr[j+1]){
let tem = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tem;
}
}
}
console.log(arr);
}
bubbleSort([2,5,6,1,2,9,4,6,3]); // output：[1, 2, 2, 3, 4, 5, 6, 6, 9]
选择排序
思路：每一次从数组中选出最小的一个元素，存放在数组的起始位置，然后，再从剩余未排序的数组中继续寻找最小元素，然后放到已排序序列的末尾。直到全部数据元素排完。
function selectSort(arr){
let min = 0; // 用来保存数组中最小的数的索引值
for(let i = 0; i < arr.length - 1; i ++){
min = i;
for(let j = i + 1; j < arr.length; j ++){
if(arr[j] < arr[min]){
min = j;
}
}
if(min != i){
swap(arr,i,min);
}
}
console.log(arr);
};
function swap(arr,index1,index2){
let tem = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tem;
}
selectSort([7,5,1,2,6,4,8,3,2]); // output： [1, 2, 2, 3, 4, 5, 6, 7, 8]
插入排序
插入算法的工作原理就是对已排序数据序列从后向前扫描，将未排序数据找到对应的位置并插入。
思路：
（1）从第一个元素开始，该元素可以被认为已经被排序了；
（2）取出下一个元素，在已经排好序的序列中从后往前扫描；
（3）直到找到小于或等于该元素的位置；
（4）将该位置后面的所有已排序的元素从后往前依次向后移一位；
（5）将该元素插入到该位置；
（6）重复步骤 2-5；
function insertSort(arr){
for(let i = 1; i < arr.length; i ++){
let j = i, key = arr[j];
while( --j > -1 ){
if(arr[j] > key){
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = key;
}
console.log(arr);
}
insertSort([12,25,41,2,3,15]); // output：[2, 3, 12, 15, 25, 41]
希尔排序
希尔排序是插入排序的一种，又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。
思路：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个数据列恰好被分成一组，算法便终止。
function shellSort(arr){
let gaps = [5, 3, 1];
for (let g = 0; g < gaps.length; ++g) {
for (let i = gaps[g]; i < arr.length; ++i) {
let temp = arr[i];
j = i；
for (j; j >= gaps[g] && arr[j - gaps[g]] > temp; j -= gaps[g]) {
arr[j] = arr[j - gaps[g]];
}
arr[j] = temp;
}
}
console.log(arr);
}
shellSort([12,21,32,14,15,18]); output：[12, 14, 15, 18, 21, 32]
归并排序
归并排序是建立在归并操作上的一种有效排序算法，该算法是采用分治法的一个非常典型的应用。即先进行划分，然后再进行合并。
思路：假设对一个数组 C 进行归并排序，步骤如下
（1）先将 C 划分为两个数组 A 和 B（即把数组 C 从中间分开）
（2）再分别对数组 A、B 重复步骤1的操作，逐步划分，直到不能再划分为止（每个子分组只剩下一个元素），至此划分结束。
（3）然后从下层往上层不断合并数组，每一层合并相邻的两个子数组。合并的过程是每次从待合并的两个子数组中选取一个最小的元素，然后把这个元素放到合并后的数组中，不断重复直到把两个子数组的元素都放到合并后的数组为止。
（4）以此类推，直到合并到最上层结束，这时数据的排序已经完成。
function merge(left, right) {
let result = [];
while(left.length > 0 && right.length > 0) {
if(left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
/* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
return result.concat(left).concat(right);
}
function mergeSort(arr){
if(arr.length == 1){
return arr;
};
let mid = Math.floor( arr.length/2 );
let left_arr = arr.slice(0, mid),
right_arr = arr.slice( mid );
return merge( mergeSort(left_arr), mergeSort(right_arr) );
}
console.log(mergeSort([12,20,30,21,15,33,26,19,40,25])); output：[12, 15, 19, 20, 21, 25, 26, 30, 33, 40]
快速排序
对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都比另一部分的所有数据小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
思路：
（1）找基准（一般以中间项为基准）
（2）遍历数组，小于基准的放在 left，大于基准的放在 right
（3）递归
function quickSort(arr){
if(arr.length<=1){return arr;} //如果数组<=1,则直接返回
let pivotIndex = Math.floor(arr.length/2);
let pivot = arr.splice(pivotIndex,1)[0]; //找基准，并把基准从原数组删除
let left=[], right=[]; //定义左右数组
for(let i=0; i<arr.length; i++){ //比基准小的放在left，比基准大的放在right
if(arr[i] <= pivot){
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot],quickSort(right)); //递归
}
console.log(quickSort([5,3,4,8,6,9,12])); // output：[3, 4, 5, 6, 8, 9, 12]
效率比较：
