【学习】排序算法 - 初级排序算法

排序算法是学习算法时十分重要的部分，尤其是在大量数据处理方面扮演十分重要的角色。在对排序算初次探索时，我们先介绍两种初级排序算法（选择排序、插入排序）以及其中一种的变体（希尔排序）。

0. 排序算法模板

在大多数情况下，排序算法只会通过两个方法操作数据： less() 方法对元素进行比较， exch() 方法将元素交换位置。而我们会将排序代码放在 sort() 方法中，使用上面两个辅助方法进行数据操作。

// 排序算法模板
public class Example 
{ 
    public static void sort(Comparable[] a){
        // 排序算法
    }
    
    // 比较两个元素
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w) < 0;  
    }
    
    // 交换两个元素位置
   	private static void exch(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;  
    }
    
    // 判断数组元素是否有序
   	public static boolean isSorted(Comparable[] a){
      	for (int i = 1; i < a.length; i++) 
         	if (less(a[i], a[i-1]))  return false;
        return true; 
   }
}

这个类展示的是数组排序实现的框架。对于我们学习的每种排序算法，我们都会为这样一个类实现一个 sort() 方法。

1. 选择排序

1.1 概述

不断地选择剩余元素之中的最小者，这种方法叫做选择排序。

这是一种最简单的排序算法。首先，找到数组中最小的元素与第一个元素交换位置，然后在剩下的元素中找最小的元素与第二个元素交换位置。如此往复，直到将整个数组排序。

1.2 选择排序算法实现

public static void sort(Comparable[] a){
  int length = a.length;
    for (int i = 0; i < length; i++){
        // 找到剩下数组最小的那个元素
        int min = i;
        for(int j = i; j < length; j++){
            if (less(a[j], a[i])){
                min = j;
            }
        }
        // 将它和当前索引的元素交换
        exch(a, i, min);
    }
}

1.3 选择排序算法分析

选择排序内循环只是在比较当前元素与已知最小元素，而交换元素在外循环，每次交换都能排定一个元素。因此，交换的总次数是固定的N，所以算法效率取决于比较的次数。

根据排序轨迹来看，选择排序需要大约 (N^2)/2 次比较和 N 次交换。

总结：

运行时间和输入无关。无论数组内元素的排序如何，所需的时间都是一样的。

移动次数最少。选择排序只用了 N 次排序，是其他排序算法都不具备的特征。

2. 插入排序

2.1 概述

将元素插入到已经有序的元素中的适当位置，这种方法叫做插入排序。

与选择排序一样，当前索引左边的所有元素都是有序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。但是当索引到达数组的右端时，数组排序就完成了。

2.2 插入排序算法实现

public static void sort(Comparable[] a){
  int length = a.length;
    for (int i = 1; i < length; i++){
        // 将元素插入到合适的地方
        for (int j = i; j >= 0 && less(a[i], less[j-1]); j--){
            exch(a, i, j-1);
        }
    }
}

2.3 插入排序算法分析

在插入排序中，为了给要插入的元素腾出空间，需要将其余的所有元素向右移动一位。因此，插入排序所需的时间取决于输入数组中元素的原始顺序。

平均情况下插入排序需要大约 (N^2)/4 次比较和 (N^2)/4 次交换。最坏的情况下需要 (N^2)/2 次比较和 (N^2)/2 次交换。最好的情况下需要 N-1 次比较和 0 次交换。

总结：

运行时间与输入有关。例如，对元素已经有序的数组排序要比对逆序的数组排序要快得多。

在实际应用中，插入排序适合处理非随机数组很有效。例如，正如刚才所说的，用插入排序对一个有序的数组排序时，插入排序能够立即发现每一个元素都已经在合适的位置上了，它的运行时间也是线性的（而选择排序的运行时间时平方级别的）。

改进：

要大幅提高插入排序的速度并不难，只需要在内循环中将较大的元素都向右移动而不总是交换两个元素（这样访问数组的次数就能减半）。

3. 希尔排序

3.1 概述

为了解决插入排序对乱序数组的效率低的问题，而产生的插入排序变体，这种方法就是希尔排序。

因为插入排序对于接近有序的数组和小数组更加高效，所以希尔排序的核心思想就是将大数组分为若干个小数组进行排序，使得大数组逐渐的变得有序，最后使用插入排序对大数组进行排序。

希尔排序将间隔为 h 的元素为一个小数组，这样元素的移动距离由 插入排序的 1 变为 h。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。

3.2 希尔排序算法实现

public static void sort(Comparable[] a){
  int length = a.length;
  int h = 1;
  while (h < N/3) h = 3*h + 1; // 1, 4, 13, 40, 121, 364, 1093, ... 
  while(h >= 1){
        for (int i = h; i < length; i++){
        	// 将元素插入到合适的地方
        	for (int j = i; j >= 0 && less(a[i], less[j-h]); j -= h){
            	exch(a, i, j-h);
        	}
    	}
        h = h / 3;
    }
}

3.3 希尔排序算法分析

对于希尔排序，我们很难去计算它的平均比较次数和交换次数。但是，希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。

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

总结：

大量的实验证明平均每个增幅所带来的比较次数约为 N 1/5 ，但只有在 N 很大的时候这个增长幅度才会变得明显。这个性质似乎也和输入无关。

在处理中等大小的数组时，通常会选择希尔排序。除了数组非常的大时，更高级的排序只比希尔排序快两倍（可能还不到）。

参考文献：算法（第四版） —— 人民邮电出版社