排序算法

发表于 | 阅读次数

什么是算法

高德纳《计算机程序设计艺术》里对算法的归纳：

输入：一个算法必须有零个或以上输入量
输出：一个算法应有一个或以上输出量
明确性：算法的描述必须无歧义，实际运行结果是确定的
有限性：必须在有限个步骤内结束
有效性：又称可行性。能够被执行者实现

定义问题

数组 array 含有 N 个正整数，输入量为array， array 中的数字从小到大排列，输出量为排好序的数组。

列如

1
var array = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
2
function sort(){
3
  你的代码
4
}
5
sort(array) == [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

不会做

遇到思路障碍怎么办？

1.将抽象的问题转化为具体的问题
2.将没见过的问题转化为见过的问题

冒泡排序

教官双手算法：较高的往后站

Javascript代码实现：

1
function bubbleSort(array){
2
  var i;
3
  var j;
4
  for (i = 0; i < array.length; i++) {
5
    for (j = 0; j < array.length - 1 - i;j++){
6
      if(array[j] > array[j+1]){
7
        swap(array,j,j+1);
8
      }
9
    }
10
  }
11
  return array;
12
}
13
function swap(array,a,b){
14
  var temp = array[a];
15
  array[a] = array[b];
16
  array[b] = temp;
17
}
18
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
19
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

冒泡排序动图演示：

冒泡排序.gif

选择排序

教官一指算法：最矮到前面来

Javascript代码实现：

1
function selectionSort(array){
2
  var i;
3
  var j;
4
  var indexOfMin;
5
  for(i=0;i<array.length;i++){
6
    indexOfMin = i;
7
    for(j=i+1;j<array.length;j++){
8
      if(array[j] < array[indexOfMin]){
9
        indexOfMin = j
10
      }
11
    }
12
    if(indexOfMin !== i){
13
      swap(array,i,indexOfMin)
14
    }
15
  }
16
  return array;
17
}
18
function swap(array,a,b){
19
  var temp = array[a];
20
  array[a] = array[b];
21
  array[b] = temp;
22
}
23
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
24
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

选择排序动图演示：

选择排序.gif

插入排序

起牌算法

Javascript代码实现：

1
function insertionSort(array){
2
    for(var i =1;i < array.length;i++){
3
      var key = array[i];
4
      var j = i - 1;
5
      while (j >= 0 && array[j] > key){
6
        array[j + 1] = array[j];
7
        j--;
8
      }
9
      array[j + 1] = key;
10
    }
11
    return array;
12
}
13
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
14
console.log(insertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

插入排序动图演示：

插入排序.gif

归并排序

领导算法

Javascript代码实现：

1
function mergeSort(arr) {  //采用自上而下的递归方法
2
    var len = arr.length;
3
    if(len < 2) {
4
        return arr;
5
    }
6
    var middle = Math.floor(len / 2),
7
        left = arr.slice(0, middle),
8
        right = arr.slice(middle);
9
    return merge(mergeSort(left), mergeSort(right));
10
}
11
12
function merge(left, right){
13
    var result = [];
14
    while (left.length && right.length) {
15
        if (left[0] <= right[0]) {
16
            result.push(left.shift());
17
        } else {
18
            result.push(right.shift());
19
        }
20
    }
21
22
    while (left.length){
23
        result.push(left.shift());
24
    }
25
    while (right.length){
26
        result.push(right.shift());
27
    }  
28
    return result;
29
}
30
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
31
console.log(mergeSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

归并排序动图演示：

归并排序.gif

快速排序

自私算法：我前面的都比我矮，我后面的都比我高

Javascript代码实现：

1
function quickSort(arr) {
2
　　if (arr.length <= 1) { return arr; }
3
　　var pivotIndex = Math.floor(arr.length / 2);
4
　　var pivot = arr.splice(pivotIndex, 1)[0];
5
　　var left = [];
6
　　var right = [];
7
　　for (var i = 0; i < arr.length; i++){
8
　　　　if (arr[i] < pivot) {
9
　　　　　　left.push(arr[i]);
10
　　　　} else {
11
　　　　　　right.push(arr[i]);
12
　　　　}
13
　　}
14
　　return quickSort(left).concat([pivot], quickSort(right));
15
};
16
17
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
18
console.log(quickSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

快速排序动图演示：

快速排序.gif

随机化快速排序

我的运气不可能那么差

Javascript代码实现：

1
function split(array, low, high) {
2
    var i = low;
3
    var x = array[low];
4
    for(var j = low + 1; j <= high; j++) {
5
        if(array[j] <= x) {
6
            i ++;
7
            if(i != j) {
8
                var temp = array[i];
9
                array[i] = array[j];
10
                array[j] = temp;
11
            }
12
        }
13
    }
14
    temp = array[low];
15
    array[low] = array[i];
16
    array[i] = temp;
17
    return i;
18
}
19
function rquicksort(array, low, high) {
20
    if(low < high) {
21
        var v = parseInt(Math.random()*(high-low+1) + low);
22
        var tmp = array[low];
23
        array[low] = array[v];
24
        array[v] = tmp; 
25
        var w = split(array, low, high);
26
        rquicksort(array, low, w -1);
27
        rquicksort(array, w +1, high);
28
        return array;
29
    }
30
}
31
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
32
arr = rquicksort(arr, 0, arr.length-1);
33
console.log(arr);//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

随机化快速排序动图演示：

随机化快速排序.gif

排序算法演示