本文将介绍几个比较简单的排序算法，并基于JavaScript实现，全文分为一、二部分。
插入类排序的思想是：在一个已排好序的序列区内，对待排序的无序序列中的记录逐个进行处理，每一步都讲待排序的记录和已排好的序列中的记录进行比较，然后有序的插入到该序列中，直到所有待排序的记录全部插入为止。
思想：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数，然后把第二个数按大小插入到有序表中；
第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；
依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
效率：
时间复杂度：平均O(n^2)，不适合对于数据量比较大的排序应用。
空间复杂度：O(1)
稳定性：稳定
js代码：
function sort(elements){ for(var i = 1; i < elements.length; i++){ if(elements[i] < elements[i-1]){ var guard = elements[i]; var j = i - 1; elements[i] = elements[j]; while(j >= 0 && guard < elements[j]){ elements[j+1] = elements[j]; j--; } elements[j+1] = guard; } } }思想：折半插入排序是对直接插入排序的简单改进，其过程是在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。
效率：
时间复杂度：平均O(n^2)，折半查找只是减少了比较次数，但是元素的移动次数不变。
空间复杂度：附加空间O(1)
稳定性：稳定
js代码：
function pushArrayWithIndex(arr, index, value) { // 将元素添加到数组的指定位置 var temArr = arr.slice(0, index); temArr.push(value); return temArr.concat(arr.slice(index)); } function BiInsertSort(arr) { // 折半插入排序 var temArr = []; // 临时数组，存储已排序项 function getSortTmpIndex(subArr, num) { var len = subArr.length; if(0 == len) return 0; // 当数组为空时，返回最开始位置 var cpmIndex = Math.ceil(len / 2); // 计算中间元素所在位置 if(cpmIndex > len - 1) cpmIndex = len - 1; if(num == subArr[cpmIndex]) { // 相等时直接返回 return cpmIndex; } if(num > subArr[cpmIndex]) { // 向后折半查找 cpmIndex++; return cpmIndex + getSortTmpIndex(subArr.slice(cpmIndex), num); } if(num < subArr[cpmIndex]) { // 向前折半查找 return getSortTmpIndex(subArr.slice(0, cpmIndex), num); } } for (var i in arr) { var index = getSortTmpIndex(temArr, arr[i]); //查找arr[i]在temArr中的位置 temArr = pushArrayWithIndex(temArr, index, arr[i]); //将元素插入到查找位置 } return temArr; } var arr = [3, 7, 6, 5, 9, 1, 2, 3, 1, 7, 4]; console.log("before:"+arr); arr = BiInsertSort(arr); console.log(" after:"+arr);思想：先将整个待排元素分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序时（增量足够小），再对全体元素进行一次直接插入排序。
过程：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；
然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量
dt=1(dt<dt-1…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 效率：
时间复杂度：平均 O(n^2) 空间复杂度：需要辅助空间 O(1)
稳定性：不稳定
js代码：
function ShellInsert(arr){ var len=arr.length; for(var i=Math.floor(len/2);i>0;i=Math.floor(i/2)){ for(var j=i;j<len;j++){ for(var k=j-i;k>=0 && arr[k]>arr[i+k];k-=i){ var temp=arr[k]; arr[k]=arr[i+k]; arr[i+k]=temp; } } } return arr; } var arr=[49,38,65,97,76,13,27,49,55,04]; console.log("before:"+arr); arr =ShellInsert(arr); console.log(" after:"+arr);选择类排序的基本思想是：对待排序记录的关键字进行两两比较，只有发现两个记录为逆序就进行交换，直到没有逆序为止。
思想：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
效率：
时间复杂度：平均 O(n)
空间复杂度：需要辅助空间 O(1)
稳定性：稳定
js代码：
function bubbleSort(arr) { var i = arr.length, j; var tempExchangVal; while (i > 0) { for (j = 0; j < i - 1; j++) { if (arr[j] > arr[j + 1]) { tempExchangVal = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tempExchangVal; } } i--; } return arr; } var arr = [3, 2, 4, 9, 1, 5, 7, 6, 8]; console.log("before: "+arr); var arrSorted = bubbleSort(arr); console.log(" after: "+arrSorted);思想：从待排序列中任意选择一个记录，以该记录的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移至该记录之前，反之，凡是关键字大于枢轴的记录均移至该记录之后。
快速排序采用了分治策略，而分治法的基本思想是：将原问题分解为若干规模更小但是结构与原问题相似的子问题，递归的解决这些问题，然后将这些子问题的解组合为原问题的解。
效率：
时间复杂度：平均 O(Nlog*2*N)
空间复杂度：需要辅助空间 O(log*2*N)
稳定性：不稳定
js代码：
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)); } var arr=[46,68,12,2,5,33,80,19,33]; console.log("before: "+arr); var arr=quickSort (arr); console.log(" after: "+arr);