常见的几种排序算法总结

[HarleyWang93]

程序，了解一下

一个程序主要包括以下两方面的信息：

• 对数据的描述，在程序中要指定用到哪些数据类型以及这些数据的类型和数据的组织形式，这就是数据结构。

• 对操作的描述，即要求计算机进行操作的步骤，就是算法

• 对于程序设计人员来说，算法，数据结构，程序化设计方法和程序语言是其所应的知识，算法是灵魂，数据结构是加工对象，语言是工具。

几种常见排序

关于排序算法通常我们所说的往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

冒泡排序

介绍

冒泡排序它重复地走访过要排序的元素，一次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

代码实现

function swap(myArray, p1, p2){
  var temp = myArray[p1];
  myArray[p1] = myArray[p2];
  myArray[p2] = temp;
}
function bubbleSort(myArray){
  var len = myArray.length;
  
  for (var i = 0; i < len - 1; i++){
    for (var j = 0; j < len - 1 - i; j++){
      if (myArray[j] > myArray[j + 1]){
        swap(myArray, j, j + 1);
      }
    }
  }
  return myArray;
}
bubbleSort([1,2,4,5,3]) //[1,2,3,4,5]

选择排序

介绍

选择排序类似于冒泡排序，只不过选择排序是首先在未排序的序列中找到最小值（最大值），放到序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾，以此类推，直到所有元素均排序完毕。

代码实现

function swap(myArray, p1, p2){
    var temp = myArray[p1];
    myArray[p1] = myArray[p2];
    myArray[p2] = temp;
}
function selectionSort(myArray){
    var len = myArray.length;
    var min;
    for (var i = 0; i < len; i++){
        // 将当前位置设为最小值
        min = i;
        // 检查数组其余部分是否更小
        for (var j = i+1; j < len; j++){
            if (myArray[j] < myArray[min]){
                min = j;
            }
        }
        // 如果当前位置不是最小值，将其换为最小值
        if (i !== min){
            swap(myArray, i, min);
        }
    }
    return myArray;
}
selectionSort([1,2,4,5,3])  //[1,2,3,4,5]

插入排序

介绍

插入排序比冒泡排序和选择排序更有效率，插入排序类似于生活中抓扑克牌来。

插入排序具体算法描述，以数组[3, 2, 4, 5, 1]为例。

1. 将数组分成[3]和[2, 4, 5, 1]两部分，前者是已排序的，后者是未排序的。

2. 取出未排序部分的第一个元素“2”，与已排序部分最后一个元素“3”比较，因为2小于3，所以2排在3前面，整个数组变成[2, 3]和[4, 5, 1]两部分。

3. 取出未排序部分的第一个元素“4”，与已排序部分最后一个元素“3”比较，因为4大于3，所以4排在3后面，整个数组变成[2, 3, 4]和[5, 1]两部分。

4. 取出未排序部分的第一个元素“5”，与已排序部分最后一个元素“4”比较，因为5大于4，所以5排在4后面，整个数组变成[2, 3, 4, 5]和[1]两部分。

5. 取出未排序部分的第一个元素“1”，与已排序部分最后一个元素“5”比较，因为1小于5，所以再与前一个元素“4”比较；因为1小于4，再与前一个元素“3”比较；因为1小于3，再与前一个元素“2”比较；因为小于1小于2，所以“1”排在2的前面，整个数组变成[1, 2, 3, 4, 5]。

代码实现

function insertionSort(myArray) {
    var len = myArray.length,     // 数组的长度
        value,                      // 当前比较的值
        i,                          // 未排序部分的当前位置
        j;                          // 已排序部分的当前位置
    
    for (i=0; i < len; i++) {    
        // 储存当前位置的值
        value = myArray[i];        
        /*
         * 当已排序部分的当前元素大于value，
         * 就将当前元素向后移一位，再将前一位与value比较
         */
        for (j=i-1; j > -1 && myArray[j] > value; j--) {
            myArray[j+1] = myArray[j];
        }
        myArray[j+1] = value;
    }    
    return myArray;
}
 insertionSort([1,2,4,5,3]) // [1,2,3,4,5]

归并排序

介绍

前面三种排序算法只有教学价值，因为效率低，很少实际使用。

归并排序（Merge sort）则是一种被广泛使用的排序方法。

它的基本思想是，将两个已经排序的数组合并，要比从头开始排序所有元素来得快。因此，可以将数组拆开，分成n个只有一个元素的数组，然后不断地两两合并，直到全部排序完成。

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

1. 将数组分成[3, 2, 4]和[5, 1]两部分。

2. 将[3, 2, 4]分成[3, 2]和[4]两部分。

3. 将[3, 2]分成[3]和[2]两部分，然后合并成[2, 3]。

4. 将[2, 3]和[4]合并成[2, 3, 4]。

5. 将[5, 1]分成[5]和[1]两部分，然后合并成[1, 5]。

6. 将[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。

代码实现

function merge(left, right){
    var result  = [],
        il = 0,
        ir = 0;
    while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
    return result.concat(left.slice(il)).concat(right.slice(ir));
}
//上面的merge函数，合并两个已经按升序排好序的数组

• 有了 merge 函数，就可以对任意数组排序了。基本方法是将数组不断地拆成两半，直到每一半只包含零个元素或一个元素为止，然后就用 merge 函数，将拆成两半的数组不断合并，直到合并成一整个排序完成的数组。

function mergeSort(myArray){
    if (myArray.length < 2) {
        return myArray;
    }
    var middle = Math.floor(myArray.length / 2),
        left    = myArray.slice(0, middle),
        right   = myArray.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));
    
    // 在返回的数组头部，添加两个元素，第一个是0，第二个是返回的数组长度
    params.unshift(0, myArray.length);
	// splice用来替换数组元素，它接受多个参数，
	// 第一个是开始替换的位置，第二个是需要替换的个数，后面就是所有新加入的元素。
	// 因为splice不接受数组作为参数，所以采用apply的写法。
	// 这一句的意思就是原来的myArray数组替换成排序后的myArray
    myArray.splice.apply(myArray, params);
	// 返回排序后的数组
    return myArray;
}
mergeSort([1,2,4,5,3]) // [1,2,3,4,5]

快速排序

介绍

快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。

快速排序算法步骤：

1. 从序列中挑出一个元素，作为”基准”(pivot)。

2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基 准的后面（相同的数可以到任一边），这个称为分区(partition)操作。

3. 对每个分区递归地进行步骤1~3，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。

代码实现

// 部署一个swap函数，用于互换两个位置的值。
function swap(myArray, firstIndex, secondIndex){
    var temp = myArray[firstIndex];
    myArray[firstIndex] = myArray[secondIndex];
    myArray[secondIndex] = temp;
}

// 部署一个partition函数，用于完成一轮排序。
function partition(myArray, left, right) {
    var pivot = myArray[Math.floor((right + left) / 2)],
        i = left,
        j = right;
    while (i <= j) {
        while (myArray[i] < pivot) {
            i++;
        }
        while (myArray[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(myArray, i, j);
            i++;
            j--;
        }
    }
    return i;
}

// 递归上面的过程，完成整个排序。
function quickSort(myArray, left, right) {
	if (myArray.length < 2) return myArray;
	left = (typeof left !== "number" ? 0 : left);
	right = (typeof right !== "number" ? myArray.length - 1 : right);
	var index  = partition(myArray, left, right);
	 if (left < index - 1) {
            quickSort(myArray, left, index - 1);
     }
	 if (index < right) {
            quickSort(myArray, index, right);
      }
	 return myArray;
}
quickSort([1,2,4,5,3]) // [1,2,3,4,5]

推荐阅读

排序算法 - 阮一峰

常用排序算法总结