简单说一说排序算法

作为一名合格的程序员，还是要懂一些排序算法。

学习这个话题，通常都会先学冒泡排序，因为它在所有的排序算法中是最简单也是最**的。当然，简单是不会有好结果的。它的性能也是最差的。

冒泡排序通过比较任何两个相邻的项，如果第一个比第二个打，则交换它们。元素项向上移动至正确的顺序，就好像气泡从水中往上冒一样。冒泡因此得名。

具体实现代码：

function bubbleSort(array){ var length = array.length; for(var i = 0 ; i < length ; i++){ for(var j = 0 ; j < length - 1 ; j++){ //for(var j = 0 ; i < length - 1 - j ; j++) if(array[j] > array[j+1]){ var temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } }

上面代码注释部分是对冒泡算法的优化：通过从内循环中减去外循环中一跑过的轮数，避免内循环中所有不必要的比较。

第二种算法是选择排序，选择排序算法是一种原址比较排序算法。含义就是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

实现代码：

function selectionSort (array){ var length = array.length, indexMin; for(var i = 0 ; i < length - 1; i++){ indexMin = i; for(var j = i ; i < length ; j++){ if(array[indexMin] > array[j]){ indexMin = j; } } if(i !== indexMin){ var temp = array[i]; array[i] = array[indexMin]; array[indexMin] = temp; } } }

第三种排序算法是插入排序，插入排序比较好理解，现实生活中比较明显的例子就是插牌。你斗地主的时候，一手牌拿着，然后从第二张开始排列，跟前面的序列进行对比。如果比前面的小则插到前面。 实现代码：

function insertionSort (array){ var length = array.length, j , temp; for(var i = 1; i < length ; i++){ j = i; temp = array[i]; while(j > 0 && array[j-1] > temp){ array[i] = array[j-1]; j--; } array[j] = temp; } }

排序小型数组时，此算法比前面两个性能要好。

第四种排序算法是归并排序，这也是第一个可以被实际使用的排序算法。归并排序是一种分治算法，思路是将原始数组切分成比较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。归并排序应用的是递归的方式。

function mergeSort (array){ array = mergeSortRec(array); } var mergeSortRec = function(array){ var length = array.length; if(length === 1){ return array; } var mid = Math.floor(length / 2), left = array.slice(0 , mid), right = array.slice(mid , length); return merge(mergeSortRec(left) , mergeSortRec(right)); } var merge = function(left , right){ var result = [], il = 0, ir = 0; while(il < left.length && ir < right.length){ if(left[il] < right[ir] && ir < right.length){ if(left[i] < right[ir]){ result.push(left[il++]); }else{ result.push(right[ir++]); } } } while(il < left.length){ result.push(left[il++]); } while(ir < right.length){ result.push(right[ir++]); } return result; }

可以看到，算法首先将原始数组分割直至只有一个元素的子数组，然后开始归并。

第五种排序算法是快速排序，也是最常用的排序算法了。同样也是用了分治算法。

“快速排序”的思想很简单，整个排序过程只需要三步： 　　（1）在数据集之中，选择一个元素作为”基准”（pivot）。 　　（2）所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。 　　（3）对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 　　

function quickSort (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)); }

封装后的源代码

所有的排序算法就总结到这里，有想法的小伙伴欢迎评论区留言！