归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
2）算法描述和实现
具体算法描述如下：
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
JavaScript代码实现：
function mergeSort(array, p, r) { if (p < r) { var q = Math.floor((p + r) / 2); mergeSort(array, p, q); mergeSort(array, q + 1, r); merge(array, p, q, r); } } function merge(array, p, q, r) { var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0; for (var i = 0; i < n1; i++) { left[i] = array[p + i]; } for (var j = 0; j < n2; j++) { right[j] = array[q + 1 + j]; } left[n1] = right[n2] = Number.MAX_VALUE; for (var k = p; k <= r; k++) { if (left[m] <= right[n]) { array[k] = left[m]; m++; } else { array[k] = right[n]; n++; } } }
3）算法分析
最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
八、桶排序
1）算法简介
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
2）算法描述和实现
具体算法描述如下：
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
JavaScript代码实现：
/*方法说明：桶排序 @param array 数组 @param num 桶的数量*/ function bucketSort(array, num) { if (array.length <= 1) { return array; } var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0; num = num || ((num > 1 && regex.test(num)) ? num : 10); for (var i = 1; i < len; i++) { min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; } space = (max - min + 1) / num; for (var j = 0; j < len; j++) { var index = Math.floor((array[j] - min) / space); if (buckets[index]) { // 非空桶，插入排序 var k = buckets[index].length - 1; while (k >= 0 && buckets[index][k] > array[j]) { buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; } else { //空桶，初始化 buckets[index] = []; buckets[index].push(array[j]); } } while (n < num) { result = result.concat(buckets[n]); n++; } return result; }
3）算法分析
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
九、计数排序
1）算法简介
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
2）算法描述和实现
具体算法描述如下：
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
JavaScript代码实现：
function countingSort(array) { var len = array.length, B = [], C = [], min = max = array[0]; for (var i = 0; i < len; i++) { min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1; } for (var j = min; j < max; j++) { C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); } for (var k = len - 1; k >=0; k--) { B[C[array[k]] - 1] = array[k]; C[array[k]]--; } return B; }
3）算法分析