什么是算法
高德纳《计算机程序设计艺术》里对算法的归纳：
输入：一个算法必须有零个或以上输入量
输出：一个算法应有一个或以上输出量
明确性：算法的描述必须无歧义，实际运行结果是确定的
有限性：必须在有限个步骤内结束
有效性：又称可行性。能够被执行者实现
定义问题
数组 array 含有 N 个正整数，输入量为array， array 中的数字从小到大排列，输出量为排好序的数组。
列如
var array = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
function sort(){
你的代码
}
sort(array) == [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
不会做
遇到思路障碍怎么办？
1.将抽象的问题转化为具体的问题
2.将没见过的问题转化为见过的问题
冒泡排序
教官双手算法：较高的往后站
Javascript代码实现：
function bubbleSort(array){
var i;
var j;
for (i = 0; i < array.length; i++) {
for (j = 0; j < array.length - 1 - i;j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
}
}
}
return array;
}
function swap(array,a,b){
var temp = array[a];
array[a] = array[b];
array[b] = temp;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
冒泡排序动图演示：
冒泡排序.gif
选择排序
教官一指算法：最矮到前面来
Javascript代码实现：
function selectionSort(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;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
选择排序动图演示：
选择排序.gif
插入排序
起牌算法
Javascript代码实现：
function insertionSort(array){
for(var i =1;i < array.length;i++){
var key = array[i];
var j = i - 1;
while (j >= 0 && array[j] > key){
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
插入排序动图演示：
插入排序.gif
归并排序
领导算法
Javascript代码实现：
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(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;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
归并排序动图演示：
归并排序.gif
快速排序
自私算法：我前面的都比我矮，我后面的都比我高
Javascript代码实现：
function quickSort(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
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]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
快速排序动图演示：
快速排序.gif
随机化快速排序
我的运气不可能那么差
Javascript代码实现：
function split(array, low, high) {
var i = low;
var x = array[low];
for(var j = low + 1; j <= high; j++) {
if(array[j] <= x) {
i ++;
if(i != j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
temp = array[low];
array[low] = array[i];
array[i] = temp;
return i;
}
function rquicksort(array, low, high) {
if(low < high) {
var v = parseInt(Math.random()*(high-low+1) + low);
var tmp = array[low];
array[low] = array[v];
array[v] = tmp;
var w = split(array, low, high);
rquicksort(array, low, w -1);
rquicksort(array, w +1, high);
return array;
}
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
arr = rquicksort(arr, 0, arr.length-1);
console.log(arr);//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
随机化快速排序动图演示：
随机化快速排序.gif
