排序算法的简介和性能特点

排序算法简单介绍

选择排序

不断地选择剩余元素之中的最小者

• 找到数组中最小的那个元素，将它和数组的第一个元素交换位置（如果最小就是第一个元素，和自己交换）
• 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置
• 往复至将整个数组排好序

插入排序

插入排序所需时间取决于输入中元素的初始顺序。

• 从索引1的位置开始第一个循环遍历
• 从第一个循环遍历的当前索引往索引位置为0开始第二个循环遍历
• 第二个循环中，如果j位置不小于j-1时，退出循环（前面位置数据都不大于j位置，所以前面是有序的）。否则，将j与j-1位置交换

冒泡排序

如名称冒泡一样，比较小的数会逐渐的冒出来。
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

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

希尔排序

是为了加快速度简单地改进了插入排序。
核心思想是使数组中任意间隔为h的元素都是有序的。

• h计算方法：初始值1，在不大于数组长度/3的时候，取序列1/2(3^K-1)最大值

  例：
  int h =1 
  while (h < N/3) h = 3*h + 1;

• 从索引h的位置开始第一个循环遍历
• 从第一个循环遍历的当前索引往索引位置为h开始第二个循环遍历
• 第二个循环中，如果j位置不小于j-h时，退出循环（前面位置数据都不大于j位置，所以前面是有序的）。否则，将j与j-h位置交换

归并排序

将两个有序的数组归并成一个更大的有序数组，从而使整个数组有序

归并方法

• 在开始前需声明一个与待排序数组同样长度的数组aux
• 将lo到hi所有元素复制到aux数组
• 通过4个条件判断进行归并
  • 左半边用尽，取右半边元素
  • 右半边用尽，取左半边元素
  • 右半边的当前元素小于左半边的当前元素，取右半边元素
  • 右半边的当前元素大于等于左半边的当前元素，取左半边元素
• 归并完成后会得到一个有序数组

自顶向下的归并排序

• 取中间索引（int mid = lo + (hi - lo)/2;）
• 对左半边递归排序
• 对右半边递归排序
• 归并左右有序数组

自底向上的归并排序

• 从长度为1的数组开始两两归并，然后是四四归并，然后是八八归并，一直下去直到越界

快速排序

将一个数组分成两个子数组，将两部分独立地排序

• 将数组元素顺序打乱
• 将数组进行切分
  • 取切分数组第一个元素
  • 从左右边界遍历数组
  • 左侧，如果元素大于第一个元素，与右侧第一个小于第一个元素交换索引（小于放左边，大于放右边，相等保持不动）
  • 将第一个元素缩影与右侧数组右边界-1交换
• 将切分后左侧数组继续切分
• 将切分后右侧数组继续切分

在对小数组的快速排序可以切换到插入排序

快速排序（三向切分）

对快速排序算法的改进，数组中有大量重复数据时表现好
将原先左右两部分换成，大于等于小于三个部分

• 将数组元素顺序打乱
• 定义指针lt = lo，i = lo + 1,gt = hi,v = a[lo]
• 当i <= gt时，遍历
• a[i] 小于v，交换lt与i的元素，将lt和i加一
• a[i] 大于v，交换gt与i的元素，将gt减一
• a[i] 等于v，将i加一
• 递归左侧数组 lo, lt -1
• 递归右侧数组 gt+1, hi
• 中间数组（lt,gt）已经有序，不用再递归排序

堆排序

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

插入元素：将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置
上浮：通过交换节点和它的父节点来实现上浮，如果节点比父节点大，进行交换

private void swim(int k){
  while (k > 1 && less(k/2, k)){ // k/2即为父节点的索引
      exch(k/2, k); // 交换
      k = k/2;  // 把索引换成父节点，并继续循环比较父节点与它的父节点
  }
}

删除最大元素：从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置
下沉：将节点向下一段直到它的子节点都比它更小或是到达了堆的底部

private void sink(int k){
  while (2*k <= N){
      int j = 2*k;
      if (j < N && less(j, j+1)) j++;  //使用子节点中比较大的那个
      if (!less(k, j)) break; // 如果比子节点大，退出
      exec(k, j); // 与子节点中比较大的那个交换
      k = j; // 使用交换后的索引继续下沉
  }
}

堆排序就是通过下沉排序完成
堆排序算法：

public static void sort(Comparable[] a){
  int N = a.length;
  for (int k = N/2; k >= 1; k--){ // 从拥有子节点的节点开始做sink操作，直到根节点
     sink(a, k, N); // 将数组构造为堆
  }

  while(N>1){
    exch(a, 1, N--); // 把根节点与堆最后一个节点进行交换
    sink(a, 1, N); // 进行下沉排序
  }
}

排序算法性能特点

稳定性：如果一个排序算法能够保证数组中重复元素的相对位置则可以被称为是稳定的。

原地排序：基本上不需要借助额外的数据结构就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。

算法	是否稳定	是否为原地排序	时间复杂度	空间复杂度	备注
选择排序	否	是	N^2	1
插入排序	是	是	介于N和N^2之间	1	取决于输入元素的排列情况
希尔排序	否	是	NlogN? N^6/5?	1
快速排序	否	是	NlogN	lgN
三向快速排序	否	是	介于N和NlogN之间	lgN	运行效率由概率提供保证，同时也取决于输入元素的分布情况
归并排序	是	否	NlogN	N
堆排序	否	是	NlogN	1