一.什么是算法？
高德纳在《计算机程序设计艺术》里对算法的归纳：
- 输入： 一个算法必须有零个或以上的输入量
- 输出： 一个算法应该有一个或以上输出量
- 明确性：算法的描述必须无歧义，实际运行结果是确定的
- 有效性： 必须在有效步骤内结束
- 有效性：又称可行性。能够被执行者实现
二.算法
-
冒泡排序
（2）效果演示:
（1）原理： 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
冒泡排序.gif
（3）代码：
function sort(array){
var i, j;
for(i=0; i<array.length; i++){
for(j=0; j<array.length-1-i; j++){
if(array[j]<=array[j+1]){
}else{
swap(array, j, j+1)
}
}
}
return array;
}
function swap(array, a, b){
var temp = array[a]
array[a] = array[b]
array[b] = temp
}
console.log(sort([3,5,38,44,15,36,26,27,2,46,4,19,47,50,48])) // [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
-
选择排序
（2）效果演示：
（1）原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
优点：选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
选择排序.gif
（3）代码：
function sort(array){
var i
var j
var indexOfMin
for(i=0; i<array.length; i++){
indexOfMin = i
for(j=i+1; j<array.length; j++){
if(array[j]<array[indexOfMin]){
indexOfMin = j
}
}
if(indexOfMin !==i){
swap(array, i, indexOfMin)
}
}
return array;
}
function swap(array, a, b){
var temp = array[a]
array[a] = array[b]
array[b] = temp
}
console.log(sort([2,44,38,5,47,15,36,26,27,3,46,4,19,50,48])) //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
-
插入排序
（2）效果演示：
（1）原理：提取第一个元素，后一个元素与前一个元素对比，如果前一个元素大于后一个元素则，后一个元素向前移动一格，移动后再与前一个元素对比，直到前一个元素小于后一个元素为止。
插入排序.gif
（3）代码
function Sort(array) {
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
var length = array.length,
i,
j;
for (i = 1; i < length; i++) {
for (j = i; j > 0; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
} else {
break;
}
}
}
return array;
}
console.log(Sort([5,8,20,20,31,44,21,37,50,28,45,28,38,32])) //[5, 8, 20, 20, 21, 28, 28, 31, 32, 37, 38, 44, 45, 50]
-
归并排序
（2）效果演示：
（1）原理：把原始数组分成若干子数组,对每一个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组。
归并排序.gif
（3）代码：
function Sort(array) {
var len = array.length;
if(len < 2) {
return array;
}
var middle = Math.floor(len / 2),
left = array.slice(0, middle),
right = array.slice(middle);
return merge(Sort(left), Sort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
console.log(Sort([14,44,27,10,11,5,45,25,48,23,22,14,19,17])) //[5, 10, 11, 14, 14, 17, 19, 22, 23, 25, 27, 44, 45, 48]
-
快速排序
（2）效果演示：
（1）原理： 将第一个元素a依次与其他元素向对比，比a大的元素放在右边，比a小的放在左边。然后将左右两边分别选择一个a重复执行以上步骤，直到排完为止。
快速排序.gif -
随机快速排序
（2）效果演示：
（1）原理：该原理与快速排序相似，不同的是选择a不一定必须是第一个元素，是可以随机取到的。
随机快速排序.gif
(3)代码
function quickSort(array) {
if (array.length <= 1) {
return array;
}
var pivotIndex = Math.floor(array.length / 2);
var pivot = array.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < array.length; i++) {
if (array[i] < pivot) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
console.log(quickSort([44,40,40,31,30,36,22,49,6,48,16,49,19])) //[6, 16, 19, 22, 30, 31, 36, 40, 40, 44, 48, 49, 49]
