最近遇到排序算法比较多，首先是快排，V8实现了一份快排，大部分的浏览器也是用快排的，快排是不稳定排序，而且最差的时间复杂度其实是o(n^2),好像归并排序也有被其他浏览器实现。然后上次一个面试官问我基本有序数组用什么排序，我想了一下，其实我可以写个提前终止的冒泡，嘿嘿。
1. 快速排序
快排的基础就是选择一个基准的元素，然后根据这个元素来划分数组，分成大于和小于这个元素的两部分,然后这个元素的位置就是确定的，然后再递归确定大于和小于这个元素的部分。
快排在基本有序的情况下，如果正序交换次数会比较少，但是感觉时间复杂度趋向于0(n^2)。
V8虽然是用快排，但是实现了插入排序，用来处理数组大小小于22的情况，
In-place QuickSort algorithm. For short (length <= 22) arrays, insertion sort is used for efficiency.
阮一峰实现了一份快排的代码，但是个人觉得他没有很好地利用快排空间复杂度的优势，甚至他用数组的函数的时候，其实也要考虑额外的复杂度，所以个人觉得时间复杂度也超了。所以我根据《算法导论》的思路实现了一份JavaScript版本，优点嘛，基本实现了没有额外空间复杂度，除了递归的O(log(n))。
function quick_sort(arr) {
function swap(i,j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function split(start,end) {
var cmp = arr[end];
var loc = start;
for(var i=start;i<end;i++){
if(arr[i]<cmp){
swap(loc,i);
loc++;
}
}
swap(loc, end);
return loc;
}
function helper(start,end) {
if(start<end){ //记得判断end要大于start
var q = split(start,end);
helper(start,q-1);
helper(q+1,end);
}
}
helper(0,arr.length-1);
return arr;
}
2. 归并排序
归并排序的思想也比较简单，主要是实现二路归并，但是归并算法是无法无视额外的空间复杂度的，也就是二路归并的时候，需要两个子数组，以及一个归并后的数组，他们是无法重合的。
上次面试官让我不用递归和栈来写一份归并，其实就是用for循环模拟，第一次写的时候，空间利用率并不是很高，现在给一份优化的版本，主要是把两个数组归并后生成的新数组去掉，然后用原始数组来存储新数组。
function merge_sort(arr) {
function merge(arr1,arr2,loc) {
var n1 = arr1.length;
var n2 = arr2.length;
var i=0,j=0;
arr1.push(Number.POSITIVE_INFINITY);
arr2.push(Number.POSITIVE_INFINITY);
while(i+j<n1+n2){
if(arr1[i]<arr2[j]){
arr[loc] = arr1[i];
i++;
}else{
arr[loc] = arr2[j];
j++;
}
loc++;
}
}
var nn = arr.length;
var merge_length = 1;
while(merge_length<nn) {
for (var i = 0; i + 2 * merge_length < nn; i = i + 2 * merge_length) {
merge(arr.slice(i,i+merge_length),arr.slice(i+merge_length,i+2*merge_length),i);
}
if(i+merge_length<nn){
merge(arr.slice(i,i+merge_length),arr.slice(i+merge_length,nn),i);
}
merge_length *=2;
}
return arr;
}
还有一种是用递归来实现，不过感觉没有严格按照递归的1，2，4这样的顺序进行合并，不过思路是差不离的。
function merge_sort(arr) {
function merge(arr1,arr2,loc) {
var n1 = arr1.length;
var n2 = arr2.length;
var i=0,j=0;
arr1.push(Number.POSITIVE_INFINITY);
arr2.push(Number.POSITIVE_INFINITY);
while(i+j<n1+n2){
if(arr1[i]<arr2[j]){
arr[loc] = arr1[i];
i++;
}else{
arr[loc] = arr2[j];
j++;
}
loc++;
}
}
function helper(start,end) {
if (start < end) {
var mid = Math.floor((start + end) / 2);
helper(start, mid);
helper(mid + 1, end);
merge(arr.slice(start, mid + 1), arr.slice(mid + 1, end+1), start);
}
}
helper(0,arr.length-1);
return arr;
}
