排序的介绍
排序是算法最常用的一种运算之一，数据记录到数据库，都需要经过排序输出到客户端上。不然乱输出不规整的数据，是难以阅读的。
本文章介绍几种最常用见的排序方法：冒泡排序，选择排序，插入排序，归并排序和快速排序。
冒泡排序
冒泡排序是从运行时间的角度上来看，最差的一个。因为冒泡排序回比较任何两周相邻的项，如果第一个比第二个大，则交换它们。
选择排序
选择排序的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值放在第二位，以此类推。
插入排序
插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了，接着，它和第二项进行比较，第二项是应该待在原位还是插到第一项之前呢？这样，头两就已正常排序，接着和第三项比较（它是该插入到第一、第二还是第三位置呢？）以此类推。
归并排序
归并排序是第一个可以被实际使用的排序算法。而javascript中的array类的sort在firefox浏览器上 就是用这种排序的。归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，知道每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。
快速排序
快速排序也许是最常用的排序算法。和归并排序一样，快速排序也使用分治的方法，将原始数组分位较小的数组（但它没有像归并排序那样将它们分割开）。这个重点说下过程。
- 首先，从数组中选择中间一项作为主元。
- 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分操作。
- 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。
排序的算法实例
function createNonSortedArray(size){
var array = new ArrayList();for (var i = size; i> 0; i--){array.insert(i);}return array;
}function createRandomNonSortedArray(){
var array = new ArrayList();array.insert(3);array.insert(5);array.insert(1);array.insert(6);array.insert(4);array.insert(7);array.insert(2);return array;
}function printArray(array){
console.log(array.toString());
}function createNonSortedArrayAndPrint(size){
var array = createNonSortedArray(size);printArray(array);return array;
}var array = createNonSortedArrayAndPrint(5);
array.bubbleSort();//5,4,3,2,1array = createNonSortedArrayAndPrint(5);
array.modifiedBubbleSort();//5,4,3,2,1array = createNonSortedArrayAndPrint(5);
array.selectionSort();//5,4,3,2,1array = createNonSortedArrayAndPrint(5);
array.insertionSort();//5,4,3,2,1array = createNonSortedArrayAndPrint(8);
array.mergeSort();//8,7,6,5,4,3,2,1array = createRandomNonSortedArray();
array.quickSort();//1,2,3,4,5,6,7ES6排序完整实现代码：
let ArrayList = (function() {
class ArrayList {
constructor() {this.array = [];}insert(item) {this.array.push(item);}swap(array, index1, index2) {var aux = this.array[index1];this.array[index1] = this.array[index2];this.array[index2] = aux;}toString() {return this.array.join();}array() {return this.array;}bubbleSort() {var length = this.array.length;for(var i = 0; i < length; i++) {console.log('--- ');for(var j = 0; j < length - 1; j++) {console.log('compare ' + this.array[j] + ' with ' + this.array[j + 1]);if(this.array[j] > this.array[j + 1]) {console.log('swap ' + this.array[j] + ' with ' + this.array[j + 1]);this.swap(this.array, j, j + 1);}}}};modifiedBubbleSort() {var length = this.array.length;for(var i = 0; i < length; i++) {console.log('--- ');for(var j = 0; j < length - 1 - i; j++) {console.log('compare ' + this.array[j] + ' with ' + this.array[j + 1]);if(this.array[j] > this.array[j + 1]) {console.log('swap ' + this.array[j] + ' with ' + this.array[j + 1]);this.swap(j, j + 1);}}}};selectionSort() {var length = this.array.length,indexMin;for(var i = 0; i < length - 1; i++) {indexMin = i;console.log('index ' + this.array[i]);for(var j = i; j < length; j++) {if(this.array[indexMin] > this.array[j]) {console.log('new index min ' + this.array[j]);indexMin = j;}}if(i !== indexMin) {console.log('swap ' + this.array[i] + ' with ' + this.array[indexMin]);this.swap(i, indexMin);}}};insertionSort() {var length = this.array.length,j, temp;for(var i = 1; i < this.length; i++) {j = i;temp = this.array[i];console.log('to be inserted ' + temp);while(j > 0 && this.array[j - 1] > temp) {console.log('shift ' + this.array[j - 1]);this.array[j] = this.array[j - 1];j--;}console.log('insert ' + temp);this.array[j] = temp;}};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[j] = array[j - 1];j--;}this.array[j] = temp;}};mergeSort() {this.array = this.mergeSortRec(this.array);};mergeSortRec(array) {var length = array.length;if(length === 1) {console.log(array);return array;}var mid = Math.floor(length / 2),left = array.slice(0, mid),right = array.slice(mid, length);return this.merge(this.mergeSortRec(left), this.mergeSortRec(right));};merge(left, right) {var result = [],il = 0,ir = 0;while(il < left.length && ir < right.length) {if(left[il] < 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++]);}console.log(result);return result;};quickSort() {this.quick(this.array, 0, this.array.length - 1);};partition(array, left, right) {var pivot = array[Math.floor((right + left) / 2)],i = left,j = right;console.log('pivot is ' + pivot + '; left is ' + left + '; right is ' + right);while(i <= j) {while(array[i] < pivot) {i++;console.log('i = ' + i);}while(array[j] > pivot) {j--;console.log('j = ' + j);}if(i <= j) {console.log('swap ' + array[i] + ' with ' + array[j]);this.swap(array, i, j);i++;j--;}}return i;};quick(array, left, right) {var index;if(array.length > 1) {index = this.partition(array, left, right);if(left < index - 1) {this.quick(array, left, index - 1);}if(index < right) {this.quick(array, index, right);}}return array;};heapSort() {var heapSize = this.array.length;this.buildHeap(array);while(heapSize > 1) {heapSize--;console.log('swap (' + +array[0] + ',' + array[heapSize] + ')');this.swap(array, 0, heapSize);console.log('heapify ' + this.array.join());this.heapify(array, heapSize, 0);}};buildHeap(array) {console.log('building heap');var heapSize = array.length;for(var i = Math.floor(array.length / 2); i >= 0; i--) {this.heapify(array, heapSize, i);}console.log('heap created: ' + this.array.join());};heapify(array, heapSize, i) {var left = i * 2 + 1,right = i * 2 + 2,largest = i;if(left < heapSize && array[left] > array[largest]) {largest = left;}if(right < heapSize && array[right] > array[largest]) {largest = right;}console.log('Heapify Index = ' + i + ' and Heap Size = ' + heapSize);if(largest !== i) {console.log('swap index ' + i + ' with ' + largest + ' (' + +array[i] + ',' + array[largest] + ')');this.swap(array, i, largest);console.log('heapify ' + array.join());this.heapify(array, heapSize, largest);}};countingSort() {var i,maxValue = this.findMaxValue(),sortedIndex = 0,counts = new Array(maxValue + 1);for(i = 0; i < array.length; i++) {if(!counts[array[i]]) {counts[array[i]] = 0;}counts[array[i]]++;}console.log('Frequencies: ' + counts.join());for(i = 0; i < counts.length; i++) {while(counts[i] > 0) {array[sortedIndex++] = i;counts[i]--;}}};bucketSort(bucketSize) {var i,minValue = this.findMinValue(),maxValue = this.findMaxValue(),BUCKET_SIZE = 5;console.log('minValue ' + minValue);console.log('maxValue ' + maxValue);bucketSize = bucketSize || BUCKET_SIZE;var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;var buckets = new Array(bucketCount);console.log('bucketSize = ' + bucketCount);for(i = 0; i < buckets.length; i++) {buckets[i] = [];}for(i = 0; i < this.array.length; i++) {buckets[Math.floor((this.array[i] - minValue) / bucketSize)].push(this.array[i]);console.log('pushing item ' + this.array[i] + ' to bucket index ' + Math.floor((this.array[i] - minValue) / bucketSize));}this.array = [];for(i = 0; i < buckets.length; i++) {this.insertionSort_(buckets[i]);console.log('bucket sorted ' + i + ': ' + buckets[i].join());for(var j = 0; j < buckets[i].length; j++) {this.array.push(buckets[i][j]);}}};radixSort(radixBase) {var i,minValue = this.findMinValue(),maxValue = this.findMaxValue(),radixBase = radixBase || 10;// Perform counting sort for each significant digit), starting at 1var significantDigit = 1;while(((maxValue - minValue) / significantDigit) >= 1) {console.log('radix sort for digit ' + significantDigit);this.array = this.countingSortForRadix(this.array, radixBase, significantDigit, minValue);console.log(this.array.join());significantDigit *= radixBase;}};countingSortForRadix(array, radixBase, significantDigit, minValue) {var i, countsIndex,counts = new Array(radixBase),aux = new Array(radixBase);for(i = 0; i < radixBase; i++) {counts[i] = 0;}for(i = 0; i < array.length; i++) {countsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);counts[countsIndex]++;}for(i = 1; i < radixBase; i++) {counts[i] += counts[i - 1];}for(i = array.length - 1; i >= 0; i--) {countsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase);aux[--counts[countsIndex]] = array[i];}for(i = 0; i < array.length; i++) {array[i] = aux[i];}return array;};sequentialSearch(item) {for(var i = 0; i < this.array.length; i++) {if(item === array[i]) {return i;}}return -1;};findMaxValue() {var max = this.array[0];for(var i = 1; i < this.array.length; i++) {if(max < this.array[i]) {max = this.array[i];}}return max;};findMinValue() {var min = this.array[0];for(var i = 1; i < this.array.length; i++) {if(min > this.array[i]) {min = this.array[i];}}return min;};binarySearch(item) {this.quickSort();var low = 0,high = array.length - 1,mid, element;while(low <= high) {mid = Math.floor((low + high) / 2);element = this.array[mid];console.log('mid element is ' + element);if(element < item) {low = mid + 1;console.log('low is ' + low);} else if(element > item) {high = mid - 1;console.log('high is ' + high);} else {console.log('found it');return mid;}}return -1;};}return ArrayList;
})()