排序算法是将一列数据按照从小到大，或从大到小的顺序有序排列；更准确地说，是按照某个关键字进行排序
冒泡排序（Bubble Sort）
思想：两个相邻的元素进行比较，若要求数据从小到大排列，如果前一个元素大于后一个元素则两者交换位置，反之不变
假设现在有一组数据[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 冒泡排序
function sort(arr){
for(var i = 0; i < arr.length - 1; i++){
var changeFlag = false;
for(var j = 0; j < arr.length - i - 1; j++){
if(arr[j] > arr[j+1]){
swap(j, j+1, arr);
changeFlag = true;
}
}
if(!changeFlag){
break;
}
}
return arr;
}
function swap(a, b, arr){
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
console.log(sort(arr));
排序结果：
选择排序
思想：首先将第1位数与它右边的所有数比较，得到最小（大）的数就放在第1位；接下来将第2位数与它右边的所有数比较，得到最小（大）的数就放在第1位......以此类推，当第n-1位数与第n位数比较好之后，将较小（大）者放在第n-1位即可，此时选择排序完成
假设现在有一组数据[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 选择排序
function sort(arr){
for(var i = 0; i < arr.length - 1; i++){
var min = i;
for(var j = i+1; j < arr.length; j++){
if(arr[min] > arr[j]){
min = j;
}
}
if(i !== min){
swap(i, min, arr);
}
}
return arr;
}
function swap(a, b, arr){
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
console.log(sort(arr));
排序结果：
插入排序
思想：与取扑克牌的原理相同。取第1张牌，无需排序；取第2张牌，与第1张比较，若比第1张小则将牌放在第1张前面，1挪到了2的位置；取第3张牌，与第2张比较，若比第2张小则将第2张牌放右挪1位，若比第1张还小，则将第1张也往右挪1位，插入到第1张的位置......以此类推，当取到第n张时，将与它前面的牌相比较，比前面的小就往前挪，插入适当的位置即可，此时插入排序完成
假设现在有一组数据[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 插入排序
function sort(arr){
for(var i = 1; i < arr.length; i++){
var current = arr[i];
for(var j = i-1; j >= 0; j--){
if(current < arr[j]){
arr[j+1] = arr[j];
arr[j] = current;
}else {
arr[j+1] = current;
break;
}
}
}
return arr;
}
console.log(sort(arr));
排序结果：
归并排序
思想：跟公司管理人员的思想类似，以一个部门为例，部门总监将手头任务派给部门经理，部门经理再将任务分配给各个小组的组长，组长再将任务派给组员，组员之间合作完成，等任务完成汇总再汇报给总监。该算法是采用分治法的一个非常典型的应用，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并（先递归的分解数列，再合并数列）
假设现在有一组数据[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 归并排序
function sort(arr){
var n = arr.length;
if(n < 2){
return arr;
}
var i = Math.ceil(n/2);
var arr1 = arr.slice(0, i);
var arr2 = arr.slice(i);
return mergeArr(sort(arr1), sort(arr2));
}
function mergeArr(arr1, arr2){
var arr = [];
while(arr1.length > 0 && arr2.length > 0){
if(arr1[0] <= arr2[0]){
arr.push(arr1.shift());
}else {
arr.push(arr2.shift());
}
}
while(arr1.length > 0){
arr.push(arr1.shift());
}
while(arr2.length > 0){
arr.push(arr2.shift());
}
return arr;
}
console.log(sort(arr));
排序结果：
快速排序
思想：在数列中选一个元素作为基准，将比基准小的元素放在基准左侧，比基准大的元素放在基准右侧，再分别对基准左侧和右侧的数列以同样的方法排序，最后再将基准左侧的有序列表和基准右侧的有序列表整合到一起排序即可。快速排序每次都以第一个元素作为基准，随机快速排序则随机选取基准
假设现在有一组数据[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// 快速排序
function sort(arr, left, right){
var n = arr.length;
var left = typeof left === 'number' ? left : 0;
var right = typeof right === 'number' ? right : n - 1;
var pivorIndex = 0;
if(left < right){
pivorIndex = setPart(arr, left, right);
sort(arr, left, pivorIndex);
sort(arr, pivorIndex+1, right);
}
return arr;
}
function setPart(arr, left, right){
var pivor = arr[left];
var index = left+1;
for(var i = index; i <= right; i++){
if(arr[i] < pivor){
swap(index, i, arr);
index ++;
}
}
swap(index-1, left, arr);
return index-1;
}
function swap(a, b, arr){
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
console.log(sort(arr));
排序结果：
计数排序
思想：是一种稳定的排序算法。使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对有确定范围的整数进行排序
假设现在有一组数据[2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
// 计数排序
function sort(arr){
var min = max = arr[0];
var c = [];
for(var i = 0; i < arr.length; i++){
if(min > arr[i]){
min = arr[i];
}
if(max < arr[i]){
max = arr[i];
}
c[arr[i]] = c[arr[i]] ? c[arr[i]] + 1 : 1;
}
var result = [];
for(var j = min; j <= max; j++){
if(c[j]){
for(var k = 0; k < c[j]; k++){
result.push(j);
}
}
}
return result;
}
console.log(sort(arr));
排序结果：
基数排序
思想：按照数的高低位排序，先按低位进行排序，然后收集；再按高位排序，然后收集；依次类推，直到最高位。
假设现在有一组数据[3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127]，对其排序，从小到大
排序过程：
JavaScript 代码如下：
var arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127];
// 基数排序
function sort(arr){
var max = arr[0];
var len = 0;
var result = [];
for(var i = 0; i < arr.length; i++){
if(max < arr[i]){
max = arr[i];
}
}
console.log(max);
while(max/10 >= 1){
len ++;
max = max/10;
}
console.log(len);
for(var m = 0; m <= len; m++){
for(var n = 0; n < arr.length; n++){
var point = parseInt(arr[n]%Math.pow(10, m+1)/Math.pow(10, m));
if(result[point] == null){
result[point] = [];
}
result[point].push(arr[n]);
}
var pos = 0;
for(var k = 0; k < result.length; k++){
var value = null;
if(result[k] != null){
while((value = result[k].shift()) != null){
arr[pos] = value;
pos++;
}
}
}
}
return arr;
}
console.log(sort(arr));
排序结果：
