排序算法

什么是算法？《数据结构和算法分析》（推荐）

高纳德在《计算机程序设计艺术》里对算法的归纳：
1.输入：一个算法必须有0个或者0个以上的输入量；
2.输出：一个算法应该 有1个或以上的输出量；
3.明确性：算法的描述必须无歧义，实际运行结果是正确的；
4.有限性：必须在有限的个步骤内结束；
5.有效性：能够被执行者实现。

什么是排序？

排序（Sorting）就是将一组对象按照规定的次序重新排列的过程，排序往往是为检索而服务的，它是数据处理中一种很重要也很常用的运算。例如我们日常学习中的查字典或者书籍的目录，这些都事先为我们排好序，因此大大降低了我们的检索时间，提高工作效率。

基本上，排序算法的输出必须遵守下列两个原则：

1. 输出结果为递增序列（递增是针对所需的排序顺序而言）
2. 输出结果是原输入的一种排列或是重组

稳定排序：

• 冒泡排序（Bubble Sort） — O(n²)
• 插入排序（Insertion Sort）— O(n²)
• 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
• 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
• 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
• 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
• 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间

不稳定排序:

• 选择排序（Selection Sort）— O(n²)
• 希尔排序（Shell Sort）— O(nlogn)
• 堆排序（Heapsort）— O(nlogn)
• 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大* 的、乱数串行一般相信是最快的已知排序

简单比较

image.png

冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序对 n个项目需要O( n²)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。
冒泡排序算法的运作如下：

• 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 3.针对所有的元素重复以上的步骤，除了最后一个。
• 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

function bubble_sort(array, length) {
   var i, j;
   for (i from 0 to length - 1) {
     for (j from 0 to length - 1 - i) {
       if (array[j] > array[j + 1])
         swap(array[j], array[j + 1])
     }
   }
 }

函数 冒泡排序 输入 一个数组名称为array 其长度为length 
    i 从 0 到 (length - 1) 
        j 从 0 到 (length - 1 - i) 
            如果 array[j] > array[j + 1] 
                交换 array[j] 和 array[j + 1] 的值 
            如果结束 
        j循环结束 
    i循环结束 
函数结束

JS实例

Array.prototype.bubble_sort = function() {
    var i, j, temp;
    for (i = 0; i < this.length - 1; i++)
        for (j = 0; j < this.length - 1 - i; j++)
            if (this[j] > this[j + 1]) {
                temp = this[j];
                this[j] = this[j + 1];
                this[j + 1] = temp;
            }
    return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];
num.bubble_sort();
for (var i = 0; i < num.length; i++)
    document.body.innerHTML += num[i] + " ";

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 1. 从第一个元素开始，该元素可以认为已经被排序
• 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
• 3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
• 4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
• 5. 将新元素插入到该位置后
• 6. 重复步骤2~5

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序

JS实例

Array.prototype.insertion_sort = function() {
  var i, j;
  for (i = 1; i < this.length; i++) {
    for (j = 0; j < i; j++) {
      if (this[j] > this[i]) {
        this.splice(j, 0, this[i]);
        this.splice(i + 1, 1);
      }
    }
  }
  return this;
};

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种[排序算法。在平均状况下，排列n个项目要O(n log n)次比较。在最坏状况下则需要O(n²)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他
算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
算法：
快速排序使用分治法策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：

• 1. 从数列中挑出一个元素，称为"基准"（pivot）
• 2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
• 3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
JS实例

Array.prototype.quick_sort = function() {
    var len = this.length;
    if (len <= 1)
        return this.slice(0);
    var left = [];
    var right = [];
    var mid = [this[0]];
    for (var i = 1; i < len; i++)
        if (this[i] < mid[0])
            left.push(this[i]);
        else
            right.push(this[i]);
    return left.quick_sort().concat(mid.concat(right.quick_sort()));
};

var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quick_sort();
for (i = 0; i < arr.length; i++)
    document.body.innerHTML += arr[i] + " ";
document.body.innerHTML += "<br>";

归并排序
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为O(n log n)，该算法是采用分治法的一个非常典型的应用，且各层分治递归可以同时进行。

递归法[
原理如下（假设序列共有 n个元素）：

1. 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
2. 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
3. 重复步骤2，直到所有元素排序完毕，即序列数为1

Array.prototype.merge_sort = function() {
    var merge = function(left, right) {
        var final = [];
        while (left.length && right.length)
            final.push(left[0] <= right[0] ? left.shift() : right.shift());
        return final.concat(left.concat(right));
    };
    var len = this.length;
    if (len < 2) return this;
    var mid = len / 2;
    return merge(this.slice(0, parseInt(mid)).merge_sort(), this.slice(parseInt(mid)).merge_sort());
};