排序算法

将一系列的值按照顺序进行排列的方法

冒泡排序（Bubble Sort）

介绍

  1. 依次比较相邻的两个数，如果不符合排序规则，则调换两个数的位置。这样一遍比较下来，能够保证最大（或最小）的数排在最后一位。
  2. 再对最后一位以外的数组，重复前面的过程，直至全部排序完成。
  3. 需要比较的项越多，成本会变的很高。

假定一组数[3,2,1,4]，根据冒泡法进行排序，结果为升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
第一轮
3,2,1,4 位置一和位置二进行比较 =》 2,3,1,4
2,3,1,4 位置二和位置三进行比较 =》 2,1,3,4
2,1,3,4 位置三和位置四进行比较 =》 2,1,3,4
第二轮
2,3,1,4 位置一和位置二进行比较 =》 2,3,1,4
2,3,1,4 位置二和位置三进行比较 =》 2,1,3,4
第三轮
2,1,3,4 位置一和位置二进行比较 =》 1,2,3,4

Javascript实现算法

  1. 定义交换函数，用于交互两个不同位置的值。

    1
    2
    3
    4
    5
    var swap = function (arr,a,b) {
      var temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
    }

  2. 定义冒泡函数，用于实现冒泡排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    var bubbleSort = function (arr) {
      var len = arr.lenghth,
          i,
          j,
          stop;
      
      for (var i=0; i<len - 1; i++) {
        for (var j=0,stop=len-1-i; j<stop; j++) {
          if (arr[j] > arr[j+1]) {
            swap(arr,arr[j],arr[j+1])
          }
        }
      }
      
      return arr;
    }

    ​

选择排序（Selection Sort）

介绍

  1. 依次比较相邻的两个数，一轮比较完毕，找到最大值（或最小值）之后，该位置的数放在正确位置。
  2. 再对放置正确位置以外的数组，重复前面的过程，直至全部排序完成。

假定一组数[3,2,1,4]，根据选择法进行排序，结果为升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
第一轮
假定第一位3为最小值，与第二位2比较 =》 最小值是第二位2
最小值2，与第三位1比较， 最小值是第三位1
最小值1，与第四位4比较， 最小值不变
第一位与第三位互换位置 =》 1,2,3,4
第二轮
假定第二位2为最小值，与第三位3比较，最小值不变
最小值2，与第四位4比较，最小值不变
第二位不变 =》 1,2,3,4
第三轮
假定第三位3位最小值，与第四位4比较，最小值不变
第三位不变 =》 1,2,3,4

Javascript实现算法

  1. 定义交换函数，用于交互两个不同位置的值。

    1
    2
    3
    4
    5
    var swap = function (arr,a,b) {
      var temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
    }

    ​

  2. 定义选择函数，用于实现选择排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    var selectionSort = function (arr) {
      var len = arr.length,min;
      
      for (var i=0; i<len; i++) {
        min = i; // 将当前位置设为最小值
        
        // 检查数组其余部分是否更小
        for (var j=i+1; j<len; j++) {
          if (arr[j]<arr[min]) {
            min = j;
          }
        }
        
        // 如果当前位置不是最小值，将其换为最小值
        if (i != min) {
          swap(arr,i,min);
        }
      }
      
      return arr;
    }

插入排序（insertion sort）

介绍

  1. 将数组分成“已排序”和“未排序”两部分，一开始的时候，“已排序”的部分只有一个元素，然后将它后面一个元素从“未排序”插入“已排序”中正确位置，从而“已排序”部分增加一个元素，“未排序”部分减少一个元素。
  2. 再从剩余的“未排序”部分抽调一个元素到“已排序”中，重复这一过程，直至全部排序完成。

假定一组数[3,2,1,4]，根据插入法进行排序，结果为升序。

1
2
3
4
分成两个部分：[3]和[2,1,4]
抽调未排序部分的第一个数，这个2和已排序部分的最后一位3比较，小于。分成这样[2,3]和[1,4]。
抽调未排序部分的第一个数，这个1和已排序部分的最后一位3比较,小于，就再与前一个2比较，小于。分成这样[1,2,3]和[4]。
抽调未排序部分的第一个数，这个4和已排序部分的最后一位3比较,大于。分成这样[1,2,3,4]。

Javascript实现算法

  1. 定义插入函数，用于实现插入排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    var insertionSort = function (arr) {
      // current - 当前比较的值，i - 未排序部分的当前位置，j - 已排序部分的当前位置
      var len = arr.length,current,i,j;
      
      for (i=0; i<len; i++) {
        current = arr[i];
        
        /*
         * 当已排序部分的当前元素大于value，
         * 就将当前元素向后移一位，再将前一位与value比较
         */
        for (j=i-1; j>-1 && arr[j]>current; j--) {
          arr[j+1] = arr[j];
        }
        
        arr[j+1] = current;
      }
      
      return arr;
    }

合并排序（Merge sort）

介绍

  1. 可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例，步骤如下：

1
2
3
4
5
6
7
8
9
10
11
将数组分成[3, 2, 4]和[5, 1]两部分。
将[3, 2, 4]分成[3, 2]和[4]两部分。
将[3, 2]分成[3]和[2]两部分，然后合并成[2, 3]。
将[2, 3]和[4]合并成[2, 3, 4]。
将[5, 1]分成[5]和[1]两部分，然后合并成[1, 5]。
将[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。

Javascript实现算法

  1. 定义合并函数，用于实现合并排序。

    1
    2

快速排序（quick sort）

介绍

  1. 确定“支点”（pivot）。虽然数组中任意一个值都能作为“支点”，但通常是取数组的中间值。
  2. 建立两端的指针。左侧的指针指向数组的第一个元素，右侧的指针指向数组的最后一个元素。
  3. 左侧指针的当前值与“支点”进行比较，如果小于“支点”则指针向后移动一位，否则指针停在原地。
  4. 右侧指针的当前值与“支点”进行比较，如果大于“支点”则指针向前移动一位，否则指针停在原地。
  5. 左侧指针的位置与右侧指针的位置进行比较，如果左侧指针的位置大于等于右侧指针的位置，则本次排序结束；如果左侧指针的位置小于右侧指针的位置，左侧指针的值与右侧指针的值互 相交换。
  6. 对左右两侧重复第2至5步。

对于数组[4, 2, 6, 5, 3, 9]的步骤说明，来自[Computer science in JavaScript: Quicksort][1]

[1]:http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/

快速排序图示1

快速排序图示2

Javascript实现算法

  1. 定义交换函数，用于交互两个不同位置的值。

    1
    2
    3
    4
    5
    var swap = function (arr,a,b) {
      var temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
    }

  2. 定义partition函数，用于完成一轮排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    var partition = function(arr,left,right) {
      // 步骤1，通常取中间值
      var pivot = arr[Math.floor((left + right) / 2)],i=left,j=right;
      
      while (i <= j) {
        // 步骤3
        while (arr[i] < pivot) {
          i++;
        }
        
        // 步骤4
        while (arr[j] > pivot) {
          j++;
        }
        
        // 步骤5
        if (i <= j) {
          swap(arr,i,j);
          i++;
          j--;
        } 
      }
      
      return i;
    }

    ​

  3. 定义快速函数，递归上面的过程，完成整个排序。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    var quickSort = function (arr,left,right) {
      if (arr.length < 2) {
        return arr;
      }
      
      // 步骤2
      left = (typeof left !== "number" ? 0 : left);
      right = (typeof right !== "number" ? arr.length - 1 : right);
      
      var index = partition(arr,left,right);
      
      if (left < index - 1) {
        quickSort(arr,left,index-1);
      }
      
      if (index < right) {
        quickSort(arr,index,right);
      }
      
      return arr;
    }

    ​