排序

本文主要介绍排序的几种实现，简单计算一下复杂度。

1. 冒泡排序

---

  void BubbleSort(ElementType A[],int N)
  {
      int P,flag;
      for(P = N-1;P>=0;p--)
      {
        flag = 0;/*建立一个检查标志：在某次排序提前完成后终止循环*/
        for(int i=0;i < p;i++)/*一趟冒泡*/
        {
            if(A[i]>A[i+1])
            {
                  swap(A[i],A[i+1]);
                  flag = 1;
              }
          }
          if (flag = 0) break;
      }
  }/*冒泡排序*/

2. 插入排序

---

由N-1趟排序组成
C语言代码实现：

void(InsertionSort)(ElementType A[],int N)
{
  int j,P;
  ElementType tmp;
  for(P=1;P<N;P++)
{
    tmp = A[P];/*摸下一张牌*/
    for(j = P; j>0&&A[j-1]>tmp; j--)
        A[j] = A[j-1];/*移出空位*/
    A[j] = tmp;/*新牌落位*/
 }
}/*插入排序例程*/

插入排序为O（N^2）
N个互异数的数组的平均逆序数是N（N-1）/4。

3. 希尔排序-缩小增量排序

---

思想：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
直接插入排序和希尔排序的比较：

1. 直接插入排序是稳定的；而希尔排序是不稳定的。
2. 直接插入排序更适合于原始记录基本有序的集合。
3. 希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
4. 在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
5. 直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。

希尔排序.png

C语言代码实现：

void Shellsort(ElementType A[],int N)
{
int i,j,Increment;
ElementType tmp;
for (Increment = N/2; Increment>0; Increment/=2)
for ( i = Increment; i < N; i++)
{
  tmp = A[i];
  for ( j = i; j >= Increment; j-=Increment)
       if(tmp<A[j - Increment)
      A[j] = A[j- Increment];
    else
      break;
  A[j] = tmp;
  }
}/*使用希尔增量的希尔排序例程*/

Java代码实现：

package notes.javase.algorithm.sort;
public class ShellSort {
public void shellSort(int[] list) {
    int gap = list.length / 2;
 while (1 <= gap) {
        // 把距离为 gap 的元素编为一个组，扫描所有组
        for (int i = gap; i < list.length; i++) {
            int j = 0;
            int temp = list[i];
            // 对距离为 gap 的元素组进行排序
            for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
        System.out.format("gap = %d:\t", gap);
        printAll(list);
        gap = gap / 2; // 减小增量
    }
}
// 打印完整序列
public void printAll(int[] list) {
    for (int value : list) {
        System.out.print(value + "\t");
    }
    System.out.println();
}
public static void main(String[] args) {
    int[] array = {
            9, 1, 2, 5, 7, 4, 8, 6, 3, 5
    };
    // 调用希尔排序方法
    ShellSort shell = new ShellSort();
    System.out.print("排序前:\t\t");
    shell.printAll(array);
    shell.shellSort(array);
    System.out.print("排序后:\t\t");
    shell.printAll(array);
 }
}

4. 堆排序

---

基本方法：建立N个元素的二叉堆，花费时间O(N)，然后执行N次DeletedMin操作花费时间O(log⁡N)，所以总的运行时间为O(N log⁡N)
缺点：DeleteMin操作中使用了一个数组用来存储离开堆得元素，所以存储需求增加一倍。
C语言代码实现：
#define LeftChild(i)(2*(i)+1)
void
PercDown(ElementType A[],int i,int N)
{
int Child;
ElementType tmp;
for(tmp = A[i];LeftChild(i)<N;i = Child)
{
Child = LeftChild(i);
if(Child!=N-1&&A[Child + 1]>A[Child])
Child++;
if(tmp<A[Child])
A[i] = A[Child];
else
break;
}
A[i] = tmp;
}
void Heapsort(ElementType A[],int N)
{
int i;
for(i = N/2;i>=0;i--)
PercDown(A,i,N);
for(i = N-1;i >0;i--)
{
Swap(&A[0],&A[i]);
PercDown(A,0,i);
}
}

Sorting_heapsort_anim.gif

5. 归并排序

---

归并排序以O（NlogN）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。是递归算法的一个很好的实例。分治是递归非常有力的用法。

void MSort(ElementType A[],ElementType TmpArray[],int Left,int Right)
{
int Center;
if(Left<Right)
  {
        Center = (Left + Right)/2;
        MSort(A,TmpArray,Left,Center);
        MSort(A,TmpArray,Center+1,Right);
        Merge(A,TmpArray,Left,Center+1,Right);
  }
}

void Mergesort(ElementType A[],int N)
{
      ElementType *TmpArray;
      TmpArray = malloc(N*sizeof(ElementType));
      if(TmpArray != NULL)
     {
      MSort(A,TmpArray,0,N-1);
      free(TmpArray);
     }
     else
    FatalError("No space for tmp array!");
}/*归并排序例程*/

Merge_sort_animation2.gif
问题：因为合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加工作，其结果严重放慢了排序的速度。所以很难用于主存排序。

6. 快速排序

---

快速排序是在实践中最快的已知排序算法，它的平均运行时间为O（NlogN）。该算法非常快的原因是非常精炼和高度优化的内部循环。最坏情况的性能为O（N^2），但稍加努力就可以避免。
三数中值分割法：消除了预排序输入的坏情况，并且减少了快速排序大约5%的运行时间。
对于很小的数组（N<=20）不递归地使用快速排序，而代之以诸如插入排序这种对小数组有效的排序算法。
算法步骤：

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

  void Quicksort(ElementType A[],int N)
{
    Qsort(A,0,N-1);
}

ElementType Median3(ElementType A[],int Left,int Right)
{
    int Center = (Left + Right)/2;
    if(A[Left]>A[Center])
        Swap(&A[Left],&A[Center]);
    if(A[Left]>A[Right])
        Swap(&A[Left],&A[Right]);
    if(A[Center]>A[Right])
        Swap(&A[Center],&A[Right]);
    Swap(&A[Center],&A[Right-1]);
    return A[Right-1];
}/*实现三数中值分割方法的程序*/


#define Cutoff(3)
void Qsort(ElementType A[],int Left,int Right)
{
    int i,j;
    ElementType Pivot;
    if(Left+Cutoff <=Right)
    {
        Pivot = Median3(A,Left,Right);
        i = Left;j = Right-1;
        for( : : )
        {
            while(A[++j]<Pivot){}
            while(A[--j]>Pivot){}
            if(i<j)
                Swap(&A[i],&A[j]);
            else
                break;
        }
        Swap(&A[i],&A[Right-1]);
        Qsort(A,Left,i-1);
        Qsort(A,i+1,Right);
    }
    else
        InsertionSort(A+Left,Right - Left + 1)；
  }/*快速排序的主例程序*/

Sorting_quicksort_anim.gif

参考：

1. 程序员必须知道的10大基础实用算法及其讲解

2. 排序四 希尔排序