复习一下排序算法

桶排序

简化版

假如有一个考试，满分10分。有5个同学分别考了5分、3分、5分、2分和8分，需要将分数进行排序。

首先需要申请一个大小为11的数组int a[11]，将a[0]~a[10]都初始化为0，表示这些分数还都没有人得过。例如，a[0]等于0就表示目前还没有人得过0分……

第一个人的分数是5分，就将相对应的a[5]的值在原来的基础上增加1，即a[5]=1，表示5分出现过了一次。第二个人的分数是3分，则a[3]=1。第三个人也是5分，因此这时a[5]=2。依次处理完所有分数。

最后再依次打印11个桶，没有出现过就不打印，出现了几次就打印几次。如从前往后打印，则最终输出“2 3 5 5 8”。代码如下：

#include <stdio.h>
int main()
{
  int a[11], i, j, t;
  for (i = 0; i <= 10; i++)
    a[i] = 0; // 初始化为0
  
  for (i = 0; i <= 5; i++) // 循环读入5个数
  {
    scanf("%d", &t);
    a[t]++;
  }
  
  for (i = 0; i <= 10; i++) // 依次判断
    for (j = 0; j < a[i]; j++) // 出现了几次就打印几次
      printf("%d ", i);
      
  getchar(); getchar();
  return 0;
}

这个算法的时间复杂度为O(M+N)，M为桶的个数，N为数的个数。这个算法是非常快的，但是，如果要求在对分数进行排序输出的同时，输出对应学生的名字，这个算法就无法做到。此外，如果待排序数的跨度非常大而数很少，那会导致浪费很多的桶。

标准版

标准的桶排序也是将数据表分割成多个桶，但是每个桶中可以放一个区间内的数据，而不只是一个单一的值。然后每个桶内再各自排序，可以用不同的排序算法，或者递归的使用桶排序，这是典型的分治策略。

基本流程：

1. 建立一堆桶
2. 遍历原始数据，并将数据放到各自的桶中
3. 对非空的桶进行排序
4. 按照顺序遍历这些桶并放回到原始数组中即可构成排序后的数组

代码如下：

public static final int BUCKET_COUNT = 10;

public static void bucketSort(int[] array) {
	List buckets = new ArrayList<ArrayList<Integer>>();
	for (int i = 0; i < BUCKET_COUNT; i++) {
		buckets.add(new ArrayList());
	}
	for (int i = 0; i < array.length; i++) {
		int idx = array[i] / BUCKET_COUNT; // 将每个数据分配到对应的桶中
		buckets.get(idx).add(array[i]);
	}
	for (List bucket : buckets) {
		Collections.sort(bucket); // 对每个桶进行排序
	}
	for (List bucket : buckets) {
		for (int a : bucket) {
			System.out.println(a);
		}
	}
}

桶排序的时间复杂度主要依赖于桶内比较排序算法的复杂度，最快为O(N*logN)。显然，可以通过减少桶内数据的数量来提高排序效率，因此可以：

• 尽量将数据平均分配到各个桶中
• 增加桶的数量，当达到极限情况，即每个桶内只有一个数据时，就是上面提到的简化版桶排序，这时的时间复杂度可以达到O(N)。但是这样会导致空间浪费严重。

冒泡排序

冒泡排序是最直接的排序算法了，基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换位置。

直接上代码：

public static void bubbleSort(AnyType[] array) {
  int tmp = 0;
  for (int i = array.length - 1; i > 0; --i) {
  	for (int j = 0; j < i; ++j) {
  		if (array[j].compareTo(array[j+1]) > 0) {
  			tmp = array[j];
  			array[j] = array[j+1];
  			array[j+1] = tmp;
  		}
  	}
  }
}

冒泡排序的时间复杂度为O(N*N)，比较慢，并且冒泡排序是稳定的。

插入排序

插入排序是最简单的排序算法之一。插入排序由N-1趟排序组成，对于p=1到N-1趟，每次都基于前面位置0到p-1上的元素已经排好序，将位置p的元素向前移动，插入到合适的位置。

public static void insertionSort(AnyType[] a)
{
  int j;
  
  for (int p = 1; p < a.length; ++p) {
    AnyType tmp = a[p];
    for (j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; --j)
      a[j] = a[j-1];
    a[j] = tmp;
  }
}

插入排序的平均时间复杂度为O(N^2)。如果输入数据已预先排序，那么时间花费为O(N)，或者数据几乎被排序过，那插入排序也很快。插入排序是一种稳定的排序算法。

希尔排序

希尔排序通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻的元素的最后一趟排序为止。因此，希尔排序有时也叫缩减增量排序。

希尔排序使用一个序列$h_1, h_2,\dots,h_t$，叫做增量序列。只要$h_1=1$，任何增量序列都是可行的，但是不同的增量序列对排序效率有所影响。每一趟对间隔为$h_k$的元素进行一次插入排序。

增量序列的一个流行（但是不好）的选择是使用Shell建议的序列：$h_t=\lfloor N/2\rfloor$和$h_k=\lfloor h_{k+1}/2\rfloor$。

public static void shellSort(AnyType[] a)
{
  int j;
  
  for (int gap = a.length/2; gap > 0; gap /= 2)
    for (int i = gap; i < a.length; ++i)
    {
      AnyType tmp = a[i];
      for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap)
        a[j] = a[j - gap];
      a[j] = tmp;
    }
}

希尔排序的运行时间依赖于增量序列的选择，证明起来非常复杂。希尔排序的平均情形分析，除最平凡的一些增量序列外，是一个长期未解决的问题。使用希尔增量时希尔排序的最坏情形运行时间为$O(N^2)$。使用Hibbard增量的希尔排序的最坏情形运行时间为$O(N^{3/2})$。

快速排序

快速排序应该是最常用的排序算法了，它的基本思想是：待排序数据中选择一个基准数（有的书上称为枢纽元（pivot）），将比它小的数放到它的左边，比它大的数放到它的右边，再递归处理两边的数据，直到排序结束。

选取枢纽元

选择合适的枢纽元直接影响排序的效率。

错误做法

一种通常的做法是选择第一个元素作为枢纽元。如果输入是随机的，那么这是可以接受的。但是如果输入是预排序或是反序的，那就可能导致所有的元素都被划入枢纽元的左边或右边，而且这在所有的递归中都会发生，这样排序的时间花费将是二次的。另一种想法是选取前两个互异的元素中的较大者作为枢纽元，不过这与只选取第一个元素作为枢纽元具有相同的害处。

安全做法

一种安全做法是随机选取枢纽元，一般来说这是安全的，除非随机数产生器有问题。然而，随机数的生成一般开销很大。

三数中值分割法

显然，枢纽元最好的选择是数组的中值，但是计算中值比较困难而且会影响排序的速度。中值的估算量可以通过随机选取三个元素并用它们的中值作为枢纽元，事实上，随机选取帮助不大，一般可以使用左端、右端和中心位置上的三个元素的中值作为枢纽元。

分割策略

分割的第一步是将枢纽元与最后的元素交换使得枢纽元离开要被分割的数据段。i从第一个元素开始向右移过所有小元素，j从倒数第二个元素开始向左移过所有大元素，然后将i、j互换，直到i、j交错。最后再将枢纽元与i交换。

一个重要的问题是如何处理等于枢纽元的元素，即i或j遇到一个等于枢纽元的元素时是否应该停止。

考虑数组中所有的元素都相等的情况。如果i和j都停止，那么过程中有很多次交换，最终建立了两个几乎相等的子数组，因此运行时间为O(N*logN)。

如果i和j都不停止，那么就应该防止i和j越过数组的端点。而且，最终枢纽元与i交换位置，此时i会在最左端或最右端，这样就会产生两个非常不均衡的子数组。那么运行时间将是O(N*N)。

因此，进行不必要的交换建立两个均衡的子数组要比蛮干冒险得到两个不均衡的子数组好。

小数组

对于很小的数组（N<=20），快速排序不如插入排序。

代码实例

private static void quickSort(AnyType[] a, int left, int right)
{
  if(left + CUTOFF <= right)
  {
    AnyType pivot = median3(a, left, right);
    
    int i = left, j = right - 1;
    for( ; ; )
    {
      while(a[++i].compareTo(pivot) < 0) {}
      while(a[--j].compareTo(pivot) > 0) {}
      if(i < j)
        swapReferences(a, i, j);
      else
        break;
    }
    
    swapReferences(a, i, right - 1);
    
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
  } else 
    insertionSort(a, left, right);
}

private static AnyType median3(AnyType[] a, int left, int right)
{
  int center = (left + right) / 2;
  if(a[center].compareTo(a[left]) < 0)
    swapReferences(a, left, center);
  if(a[right].compareTo(a[left]) < 0)
    swapReferences(a, left, right);
  if(a[right].compareTo(a[center]) < 0)
    swapReferences(a, center, right);
    
  swapReferences(a, center, right - 1);
  return a[right - 1];
}

上述方法执行三数中值分割法，先将三数进行了排序，然后将right-1位置上的数作为枢纽元。这个方法的额外好处就是，left和right位置上的数已经放在了正确的位置。

算法分析

快速排序时间花费的最坏情况是O(N^2)，最好情况是O(N*logN)，平均情况也是O(N*logN)。快速排序是不稳定的。

堆排序

使用堆排序，首先需要建立一个二叉堆。这时最小的元素就会在堆顶，每次执行deleteMin操作，最小的元素先离开堆，通过将这些元素依次记录到另一个数组中，得到N个元素的排序。

但是，这样的方法就使用了一个附加的数组。因此，存储需求增加一倍。为了回避这个问题，可以这么做：每次deleteMin之后，堆减小1。因此，位于堆中最后的单元可以用来存放刚刚删去的元素。使用这种策略时，最后该数组会保存一个倒序的排序，所以如果想进行典型的递增排序，一开始应建立最大堆。

在实现中，通过每次将堆中的最后元素与第一个元素交换，执行N-1次deleteMax操作，每次将堆的大小缩减1并进行下滤。

private static int leftChild(int i)
{
	return 2 * i + 1;
}

private static void percDown(AnyType[] a, int i, int n)
{
	int child;
	AnyType tmp;

	for (tmp = a[i]; leftChild(i) < n; i = child) {
		child = leftChild(i);
		if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0)
			child++;
		if (tmp.compareTo(a[child]) < 0)
			a[i] = a[child];
		else
			break;
	}
	a[i] = tmp;
}

public static void heapSort(AnyType[] a)
{
	for (int i = a.length / 2; i >= 0; i--) {	/* buildHeap */
		percDown(a, i, a.length);
	}
	for (int i = a.length - 1; i > 0; i--) {
		swapReferences(a, 0, i);				/* deleteMax */
		percDown(a, 0, i);
	}
}

建立二叉堆的时间花费为O(N)，然后执行N次deleteMax操作，每个deleteMax花费时间O(logN)，因此总的运行时间为O(NlogN)。堆排序是不稳定的。

归并排序

归并排序的基本操作是合并两个已排序的表。基本的合并算法是取两个输入数组A和B，一个输出数组C，以及3个计数器Actr、Bctr、Cctr，它们初始置于对应数组的开始端。A[Actr]和B[Bctr]中的较小者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完的时候，则将另一个表中的剩余部分拷贝到C中。

对merge例程的设计比较关键，如果对merge的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有logN个临时数组处在活动期（为什么呢。。merge本身并没有递归，似乎只有创建临时数组会浪费一些时间。。）。由于merge是mergeSort的最后一行，因此在任一时刻只需要一个临时数组在活动，而且这个临时数组可以在public型的mergeSort驱动程序中建立。

private static void merge(AnyType[] a, AnyType[] tmpArray, int leftPos, int rightPos, int rightEnd)
{
	int leftEnd = rightPos - 1;
	int tmpPos = leftPos;
	int numElements = rightEnd - leftPos + 1;

	while(leftPos <= leftEnd && rightPos <= rightEnd)
		if (a[leftPos].compareTo(a[rightPos]) <= 0)
			tmpArray[tmpPos++] = a[leftPos++];
		else
			tmpArray[tmpPos++] = a[rightPos++];

	while(leftPos <= leftEnd) // Copy rest of first half
		tmpArray[tmpPos++] = a[leftPos++];

	while(rightPos <= rightEnd) // Copy rest of the right half
		tmpArray[tmpPos++] = a[rightPos++];

	// Copy tmpArray back
	for (int i = 0; i < numElements; i++, rightEnd--) {
		a[rightEnd] = tmpArray[rightEnd];
	}
}

private static void mergeSort(AnyType[] a, AnyType[] tmpArray, int left, int right)
{
	if (left < right) {
		int center = (left + right) / 2;
		mergeSort(a, tmpArray, left, center);
		mergeSort(a, tmpArray, center + 1, right);
		merge(a, tmpArray, left, center + 1, right);
	}
}

public static void mergeSort(AnyType[] a)
{
	AnyType[] tmpArray = (AnyType[])new Comparable[a.length];
	mergeSort(a, tmpArray, 0, a.length - 1);
}

归并排序的运行时间是O(NlogN)，但是它有一些附加消耗，如拷贝临时数组等。归并排序是稳定的。

拓扑排序

拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从vi到vj的路径，那么排序中vj就出现在vi的后面。显然，如果图含有圈，那么拓扑排序是不可能的。此外，拓扑排序不必是唯一的；任何合理的排序都可以。

一个简单的拓扑排序算法是先找出任意一个没有入边的顶点。然后显示出该顶点，并将它及其边一起从图中删除。然后对图的其余部分应用同样的方法处理。

假设每个顶点的入度被存储且图被读入一个邻接表中，则简单的拓扑排序伪代码如下：

void topsort() throws CycleFoundException
{
	for (int counter = 0; counter < NUM_VERTICES; counter++) {
		Vertex v = findNewVertexOfIndegreeZero();
		if (v == null) {
			throw new CycleFoundException();
		}
		v.topNum = counter;
		for each Vertex w adjacent to v
			w.indegree--;
	}
}

因为findNewVertexOfIndegreeZero方法是对顶点数组的一个简单的顺序扫描，所以每次对它的调用都花费O(|V|^2)时间，因此该算法的运行时间为O(|V|^2)。

下面对该算法进行优化。可以通过将所有（未分配拓扑编号）的入度为0的顶点放在一个特殊的盒子中而消除全局扫描的无效劳动。此时findNewVertexOfIndegreeZero方法返回（并删除）的是该盒子中的任一顶点。当降低它的邻接顶点的入度时，检查每一个顶点并在入度降为0时把它放入盒子中。为实现这个盒子，可以使用一个栈或队列。拓扑排序就是顶点出队的顺序。

void topsort() throws CycleFoundException
{
	Queue<Vertex> q = new Queue<Vertex>();
	int counter = 0;

	for each Vertex v
		if (v.indegree == 0)
			q.enqueue(v);

	while(!q.isEmpty) {
		Vertex v = q.dequeue();
		v.topNum = ++counter;

		for each Vertex w adjacent to v
			if(--w.indegree == 0)
				q.enqueue(w);
	}

	if (counter != NUM_VERTICES) {
		throw new CycleFoundException();
	}
}

如果使用邻接表，那么执行这个算法所用的时间为O(|E|+|V|)。

计数排序

计数排序是一种非比较的排序算法，它与简化版的桶排序类似。同样，C[i]表示元素i出现的次数。但计数排序通常有额外的工作：

• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加，C[i] = C[i] + C[i-1]），C[i]就表示值不大于i的元素个数
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

public class CountingSort {
    public static void main(String[] argv) {
        int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
        Utils.print(A);
    }

    public static int[] countingSort(int[] A) {
        int[] B = new int[A.length];
        // 假设A中的数据a'有，0<=a' && a' < k并且k=100
        int k = 100;
        countingSort(A, B, k);
        return B;
    }

    private static void countingSort(int[] A, int[] B, int k) {
        int[] C = new int[k];
        // 计数
        for (int j = 0; j < A.length; j++) {
            int a = A[j];
            C[a] += 1;
        }
        Utils.print(C);
        // 求计数和
        for (int i = 1; i < k; i++) {
            C[i] = C[i] + C[i - 1];
        }
        Utils.print(C);
        // 整理
        for (int j = A.length - 1; j >= 0; j--) {
            int a = A[j];
            B[C[a] - 1] = a;
            C[a] -= 1;
        }
    }
}


//针对c数组的大小，优化过的计数排序
public class CountSort{
	public static void main(String []args){
		//排序的数组
		int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
		int b[] = countSort(a);
		for(int i : b){
			System.out.print(i + "  ");
		}
		System.out.println();
	}
	public static int[] countSort(int []a){
		int b[] = new int[a.length];
		int max = a[0], min = a[0];
		for(int i : a){
			if(i > max){
				max = i;
			}
			if(i < min){
				min = i;
			}
		}
		//这里k的大小是要排序的数组中，元素大小的极值差+1
		int k = max - min + 1;
		int c[] = new int[k];
		for(int i = 0; i < a.length; ++i){
			c[a[i]-min] += 1;//优化过的地方，减小了数组c的大小
		}
		for(int i = 1; i < c.length; ++i){
			c[i] = c[i] + c[i-1];
		}
		for(int i = a.length-1; i >= 0; --i){
			b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
		}
		return b;
	}
}

计数排序具有线性的时间复杂度。

基数排序

假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。

通常，基数排序要用到计数排序或者桶排序。下面排序正整数的实现中用到了计数排序：

void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n); //求数据的最大位数
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

基数排序的时间复杂度为O(k*n)，其中n为元素个数，k为元素的排序关键字个数。

参考

• 《数据结构与算法分析——Java语言描述》第2版
• 《啊哈！算法》
• 计数排序
• 基数排序
• 三种线性排序算法 计数排序、桶排序与基数排序