算法学习笔记之四 - 排序算法

2013-01-16 19:02

选择排序

基本原理

首先,找到数组中最小的元素, 其次, 将它和数组中第1个元素交换位置;再次,在剩下的元素中, 找到最小的元素,将它和数组中第2个元素交换位置, 如此直到将整个数组排序.

伪代码


for(数组中每一个下标i) {
  设j是从i到数组结束的所有元素中值最小的元素的下标
  交换i位置和j位置的元素
}

分析

交换元素的代码在内循环之外, 每次交换都能排定一个元素, 交换的次数为N, 算法的效率取决于比较的次数.

0到N-1的任意一个i都要进行一次交换和N-1-i次比较 选择排序大约需要N*N/2次比较和N次交换

复杂度

O(N*N)

特点

  • 运行时间和输入无关
  • 数据移动是最少的

代码


/*
 * select_sort.js
 * */

var swap = function (items, i, j) {
  var temp = items[i];
  items[i] = items[j];
  items[j] = temp;
};

var select_sort = function(data) {
  var N = data.length;
  var min;
  for (var i = 0; i < N; i += 1) {
    min = i;
    for (var j = i + 1; j < N; j += 1) {
      if(data[j] < data[min]) {
        min = j;
      }
    }
    swap(data, i, min);
  }
};
exports.select_sort = select_sort;

运行示例

[1,5,2,7,3,8,9,0]

每次循环后的结果:


[0,5,2,7,3,8,9,1] 最小的是0, 不变
[0,1,2,7,3,8,9,5] 最小的是1, 和5交换
[0,1,2,7,3,8,9,5] 最小的是2, 不变
[0,1,2,3,7,8,9,5] 最小的是3, 和7交换
[0,1,2,3,5,8,9,7] 最小的是5, 和7交换
[0,1,2,3,5,7,9,8] 最小的是7, 和8交换
[0,1,2,3,5,7,8,9] 最小的是8, 和9交换

插入排序

基本原理

插入排序逐个处理待排序的元素,将每个新元素与前面已排序的子序列中的元素进行比较, 将它插入到子序列的正确位置.

伪代码


for(数组中第2个元素开始的每个i) {
  将i和前面的元素进行比较,与每一个比它大的元素进行交换
}

分析

对于随机排列的长度为N且主键不重复的数组,平均情况下插入排序需要NN/4次比较以及 NN/4次交换.最坏情况下需要NN/2次比较和NN/2次交换,最好情况下需要N-1次比较和0次 交换.

复杂度

O(N*N)

特点

插入排序对于常见的某些类型的非随机数组很有效

代码


/*
 * insert_sort.js
 */

var swap = require('./util').swap;
var less = require('./util').less;

var insert_sort = function(data) {
  var N = data.length;
  for(var i = 1;i < N; i++) {
    for(var j = i; j > 0 && less(data[j], data[j-1]); j--) {
      swap(data, j, j-1);
    }
  }
};
exports.insert_sort = insert_sort;

运行示例

[1,5,2,7,3,8,9,0]


[1,5,2,7,3,8,9,0] 5比1大, 不变
[1,2,5,7,3,8,9,0] 2比5小, 和5交换位置; 比1大, 停止
[1,2,5,7,3,8,9,0] 7比5大, 不变
[1,2,3,5,7,8,9,0] 3比7小,和7交换; 比5小,和5交换; 比2大, 停止
[1,2,3,5,7,8,9,0] 8比7大, 不变
[1,2,3,5,7,8,9,0] 9比8大, 不变
[0,1,2,3,5,7,8,9] 0比9小, 和9交换, ... 一直将0移动到最前面

希尔排序

基本原理

希尔排序基于插入排序, 因为对于大规模的乱序数组, 插入排序很慢, 它只会交换相邻的元素, 因此元素只能一点一点的从数组的一端移动到另一端. 希尔排序为了加快速度, 简单的改进了插入排序, 交换不相邻的元素对数组进行局部排序, 并最终使用插入排序将局部有序的数组进行排序.

希尔排序需要一个递增序列, 来确定每次参与排序的元素的数目, 比如设置递增序列为0, 2, 4, 6, 8, 数组程度为16, 则希尔排序先将数组分成8个长度为2的子序列,然后将这个子序列排序, 然后再将数组 分成4个长度为4的子序列, 然后在排序, ... 直到将整个数组作为子序列在进行插入排序.

伪代码


while(递增序列h >= 1) {
  for(数组中每间隔h的元素) {
    将i和前面的元素进行比较,与每一个比它大的元素进行交换
  }
  将h按照约定的规则减小
}

分析

使用递增序列1, 4, 13, 40, 121, 364...的希尔排序所需的比较次数不会超出N的若干倍乘以递增序列的长度(不懂啊...)

复杂度

和递增序列的选择有关, 小于O(N*N), 大概为O(N的1.3次方)

特点

对于大型数组, 性能比插入排序和选择排序快很多

代码


/*
 * shell_sort.js
 */
var swap = require('./util').swap;
var less = require('./util').less;

var shell_sort = function(data) {
  var N = data.length;
  var h = 1;
  while(h < N/3) {
    h = 3 * h + 1;
  }
  while(h >= 1) {
    for(var i = h; i<N;i++) {
      for(var j=i; j>=h && less(data[j], data[j-h]); j -= h) {
        swap(data, j, j-h);
      }
    }
    h = parseInt(h / 3, 10);
  }
};
exports.shell_sort = shell_sort;

运行示例

[1,5,2,7,3,8,9,0]


这里选取的递增序列为1, 4, 13 ...
[1,5,2,0,3,8,9,7] h为4, 从第5个元素开始,和第5-i个元素排序, 下面就是普通的插入排序
[1,2,5,0,3,8,9,7] h为1, 5比2大,和2交换,2比1大,停止
[0,1,2,5,3,8,9,7] h为1, 0比5小, 交换, 比2小, 交换, 比1小, 交换
[0,1,2,3,5,8,9,7] h为1, 3比5小, 交换, 比2大, 停止
[0,1,2,3,5,8,9,7] h为1, 8比5大, 不动
[0,1,2,3,5,8,9,7] h为1, 9比8大, 不动
[0,1,2,3,5,7,8,9] h为1, 7比9小, 交换, 比8小, 交换, 比5大, 停止

归并排序

基本原理

归并是将2个有序的数组合并为1个更有大的有序数组,归并排序就是基于归并的简单的 递归排序算法.

伪代码

分析

原地归并的抽象方法

实现归并排序的一种直截了当的方法是将2个不同的有序数组归并到第三个数组中, 但是如果使用归并排序将一个大数组排序时,每次归并都创建新数组来存储排序结果 可能会带来问题.我们需要一种能够在原地归并的方法,这样就可以先将前半部分排序, 然后将后半部分排序,然后在数组中排序而不需要使用额外的空间.

复杂度

O(NlgN)

特点

归并排序和希尔排序非常接近,速度都非常快, 可以用于规模很大的数组.

代码

运行示例

快速排序

基本原理

伪代码

分析

复杂度

特点

代码

运行示例

堆排序

基本原理

伪代码

分析

复杂度

特点

代码

运行示例

冒泡排序

基本原理

伪代码

分析

复杂度

特点

代码

运行示例