排序算法总结

 

稳定：如果a原本排在b前面，排序后依旧如此，则稳定。 口诀："插泡归基稳" 一、快速排序 思想： 1、选择一个元素作为"基准"（pivot）。 2、所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。 3、对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 代码：

 

var quickSort=function(arr){ //如果数组<=1,则直接返回 if(arr.length<=1){return arr;} var index=Math.floor(arr.length/2); //找基准，并把基准从原数组删除 var value=arr.splice(index,1)[0]; //定义左右数组 var left=[],right=[]; //比基准小的放在left，比基准大的放在right for(var i=0;i<arr.length;i++){ if(arr[i]<=value){ left.push(arr[i]); }else{ right.push(arr[i]); } } //递归 return quickSort(left).concat(value,quickSort(right)); }

效率： 时间复杂度O(nlgn) 二、冒泡排序 思想： 1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。 2.第一轮的时候最后一个元素应该是最大的一个。 3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。 代码：

var bubbleSort=function(arr){ if (!arr||arr.length<=1) { return arr; } for (var i = 0; i < arr.length; i++) { for (var j = i+1; j < arr.length; j++) { if (arr[i]>arr[j]) { var temp=arr[j]; arr[j]=arr[i]; arr[i]=temp; } } } return arr; }

效率： 时间复杂度O(n^2) 三、插入排序 思想： 1、从第一个元素开始，该元素可以认为已经被排序 2、取出下一个元素，在已经排序的元素序列中从后向前扫描 3、如果该元素（已排序）大于新元素，将该元素移到下一位置 4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 5、将新元素插入到下一位置中 6、重复步骤2 代码：

var insertSort=function(arr){ if (!arr||arr.length<=1) { return arr; } //假定第0个元素是一个有序的数组，从第一个元素开始排序 for (var i = 1; i < arr.length; i++) { //升序 if (arr[i]<arr[i-1]) { var current=arr[i]; //取出无序数列的第一个元素 var j=i-1; //记下有序数列的最后一个位置 while (j>=0&¤t<arr[j]) { arr[j+1]=arr[j]; //将有序数列的容量扩大一个 j--; } arr[j+1]=current; } } return arr; }

效率： 时间复杂度O(n^2) 四、选择排序 思想： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置； 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 以此类推，直到所有元素均排序完毕。 代码：

var selectSort=function(arr){ if (!arr||arr.length<=1) { return arr; } for (var i = 0; i < arr.length; i++) { var minIndex=i; for(var j=i+1;j<arr.length;j++){ if (arr[j]<arr[minIndex]) { minIndex=j; //记下最小的位置 } } var temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } return arr; }

效率： 时间复杂度O(n^2) 五、归并排序 思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 代码：

var mergerSort=function(arr){ if (!arr||arr.length<=1) { return arr; } var mid=Math.floor(arr.length/2); var left=arr.slice(0,mid); var right=arr.slice(mid); return merger(mergerSort(left),mergerSort(right)); } var merger=function(left,right){ var result=[]; while (left.length&&right.length) { //left和right都不为空时 if (left[0]<=right[0]) { result.push(left.shift()); }else{ result.push(right.shift()); } } while (left.length) { //right为空时 result.push(left.shift()); } while (right.length) { //left为空时 result.push(right.shift()); } return result; }

效率： 时间复杂度O(nlgn)