什么是算法
高德纳在《计算机程序设计艺术》里对算法的归纳：
书籍推荐：《数据结构与算法分析》
- 输入：一个算法必须有零个或以上输入量
- 输出：一个算法应有一个或以上的输出量
- 明确性：算法的描述必须无歧义，实际运行结果是确定的
- 有限性：必须在有限个步骤内结束
- 有效性：又称可行性。能过被执行者实现
排序算法可视化网站推荐： https://visualgo.net/zh/sorting
问题
数组 array 含有 N 个正整数,
输入量为 array,
请将 array 中的数字从小到大排列，
输出量为排好序的数组。
例如
var array = [5, 2, 4, 6, 8]
function sort(){
// body
}
sort(array) == [2, 4, 5, 6, 8]
冒泡排序(Bubble Sort)
第一个数字开始，每一个数字与自身相邻的后一位数字比较，如果后一位数字较小，则互换位置，否则不换，第一次所有数字都比较完毕后（比较 n-1 次即可完成），最后一位数字是最大的，依此类推（第二次比较 n-2 次），直到完成排序（最后剩余2个数字比较1次即可）
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
排序步骤如下：
第i 9 次 5,2,6,8,3,1,4,0,7,9 // 第一轮比较结束后，较大的互换位置，9最大，在最后面，比较次数8次
第i 8 次 2,5,6,3,1,4,0,7,8,9 // 第二轮比较结束后8最大，较大的互换位置，在最后面，比较次数7次，依次类推
第i 7 次 2,5,3,1,4,0,6,7,8,9
第i 6 次 2,3,1,4,0,5,6,7,8,9
第i 5 次 2,1,3,0,4,5,6,7,8,9
第i 4 次 1,2,0,3,4,5,6,7,8,9
第i 3 次 1,0,2,3,4,5,6,7,8,9
第i 2 次 0,1,2,3,4,5,6,7,8,9
第i 1 次 0,1,2,3,4,5,6,7,8,9
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(bubbleSort(arr));
function bubbleSort(array){
var temp; // 获取临时参数
// 最外层比较 i 次
for(var i = array.length - 1; 0 < i; i--){
// 确定内层循环边界
for(var j = 0; j < i; j++){
// 如果后一个数字较小，则调换位置
if (array[j] > array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
console.log('第j ' + i + ' ' + j + ' 次 ' + array)
}
console.log('第i ' + i + ' 次 ' + array)
}
return array;
}
选择排序(Select Sort)
第一个数字开始（开始时认为第一个数字为最小数字），第一个数字与所有的数字比较，获得数组中最小的数字，最小的数字与第一个数字互换位置，则最小的在第一个，然后第二个数字开始，重复第一次的流程，直到剩余最后一个数字，则剩余的数字为最大的数字而且出现在末尾，最小的数字在第一个，排序完成
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步骤如下：
第i 0 次 8,5,2,6,9,3,1,4,0,7 // 第一轮比较结束后，0最小，与8互换位置
第i 1 次 0,5,2,6,9,3,1,4,8,7 // 第二轮比较结束后，1最小，与5互换位置
第i 2 次 0,1,2,6,9,3,5,4,8,7
第i 3 次 0,1,2,6,9,3,5,4,8,7
第i 4 次 0,1,2,3,9,6,5,4,8,7
第i 5 次 0,1,2,3,4,6,5,9,8,7
第i 6 次 0,1,2,3,4,5,6,9,8,7
第i 7 次 0,1,2,3,4,5,6,9,8,7
第i 8 次 0,1,2,3,4,5,6,7,8,9
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(selectSort(arr));
function selectSort(array){
var temp,
minIndex,
minValue;
for(var i = 0; i < array.length - 1; i++){
minIndex = i;
minValue = array[minIndex];
for(var j = i + 1; j < length; j++){
// 如果当前最小值大于数组中的数字，则数组中的数字为最小，获取其下标和值
if(minValue > array[j]){
minIndex = j;
minValue = array[minIndex];
}
// console.log('第j ' + j + ' 次 ' + array);
}
console.log('第i ' + i + ' 次 ' + array);
// 将最小值和当前开始比较多数字位置互换
temp = array[i];
array[i] = minValue;
array[minIndex] = temp;
}
return array;
}
插入排序(Insertion Sort)
类似于扑克牌摸牌，得到一个数字，大于此数字放在右侧，小于此数字放在左侧，如果左侧或者右侧有多个数字，则依次进行比较，直到找到合适位置，依次类推，以下面示例代码中数组为例：
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步骤如下
[ 5, 8, 2, 6, 9, 3, 1, 4, 0, 7 ] // 第一轮比较结束后，5和8互换位置
[ 2, 5, 8, 6, 9, 3, 1, 4, 0, 7 ] // 第二轮比较结束后，2小于5、8，所以与5、8分别互换位置
[ 2, 5, 6, 8, 9, 3, 1, 4, 0, 7 ] // 第三轮比较结束后，6大于5，小于8，所以与8互换位置，依次类推
[ 2, 5, 6, 8, 9, 3, 1, 4, 0, 7 ]
[ 2, 3, 5, 6, 8, 9, 1, 4, 0, 7 ]
[ 1, 2, 3, 5, 6, 8, 9, 4, 0, 7 ]
[ 1, 2, 3, 4, 5, 6, 8, 9, 0, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 8, 9, 7 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(inserterSort(arr));
function inserterSort(array) {
//
var temp;
for (var i = 1; i < array.length; i++) {
for (var j = i; j > 0; j--) {
// 如果前一个比当前数字大，则交换位置
if (array[j-1] > array[j]) {
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
// 如果前一个比当前数字小，不做变动，退出循环
} else {
break;
}
}
}
return array
}
归并排序(Merge Sort)
领导算法，得到一个数组时，将数组一分为二（一直分半，直到剩余1个或者2个数字），对其分别排序，然后再放到一起排序，直到完成，以下面示例代码中的数组为例：
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7]
排序步骤如下
第一次划分：[8, 5, 2, 6, 9]; [3, 1, 4, 0, 7]
第二次划分：[8, 5, 2]; [6, 9]; [3, 1,4]; [0, 7]
第三次划分：[8, 5]; [2]; [6, 9]; [3, 1]; [4]; [0, 7]
第一次排序：[5, 8]; [2]; [6, 9]; [1, 3]; [4]; [0, 7]
第二次排序：[2, 5, 8]; [6, 9]; [1, 3, 4]; [0, 7]
第三次排序：[2, 5, 6, 8, 9]; [0, 1, 3, 4, 7]
第三次排序：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(mergeSort(arr));
function mergeSort(arr){
if(arr.length <= 1){
return arr;
}
var pivot = Math.floor(arr.length / 2); // 每次获取中间位置为基准位置
var left = arr.slice(0, pivot); // 将原有数组一分为二
var right = arr.slice(pivot);
function merge(left, right){
var result = [];
while (left.length > 0 && right.length > 0) {
// 重复对比，小的放到数组前面
if(left[0] < right[0]){
result.push(left.shift());
} else {
result.push(right.shift());
}
}
console.log('result ' + result);
// 将结果合并返回
return result.concat(left, right);
}
console.log(arr);
// 重复一分为二
return merge(mergeSort(left), mergeSort(right));
}
快速排序(Quick Sort)
得到一个数组，获取中间位置的数字作为基准，比基准位置数字小的都到放到其前面，比基准数字大的都放到其后面，然后左右两边再分别找到基准位置，分别排序，直到完成。
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
排序步骤如下:
第一次划分：[2, 1, 0]; [8, 5, 6, 9, 4, 7]
第二次划分：[0]; [2]; [5, 4]; [8, 9, 7]
第三次划分：[0]; [2]; [5, 4]; [8, 7]
第一次排序：[0, 1, 2]; [4, 5]; [7, 8, 9]
第二次排序：[0, 1, 2, 3]; [4, 5, 6, 7, 8, 9]
第三次排序：[0, 1, 2, 3，4, 5, 6, 7, 8, 9]
此处写的较为模糊，以下面代码为基准写的排序步骤，建议参考文章开头的可视化网站理解
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(quickSort(arr));
function quickSort(arr){
if(arr.length <= 1){
return arr;
}
var pivotInedx = Math.floor(arr.length / 2); // 每次选择中间位置作为基准位置
var pivot = arr.splice(pivotInedx, 1)[0]; // 选择基准位置上的数字
console.log(pivot);
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]);
}
console.log(arr)
}
// 重复调用，并将得到的数组拼接在一起，完成为止
return quickSort(left).concat([pivot],quickSort(right));
}
随机快速排序(Random Quick Sort)
原理同快速排序，只是基准位置为数组中随机数字，某些情况下排序的速度快于快速排序
var arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7];
console.log(quickSort(arr));
function quickSort(arr){
if(arr.length <= 1){
return arr;
}
var pivotInedx = Math.floor(Math.random() * arr.length); // 随机选择基准位置
var pivot = arr.splice(pivotInedx, 1)[0]; // 选择基准位置上的数字
console.log(pivot);
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]);
}
console.log(arr)
}
// 重复调用，并将得到的数组拼接在一起，完成为止
return quickSort(left).concat([pivot],quickSort(right));
}
