排序(一)

初级排序算法

选择排序

思想：首先，找到数组中最小的那个元素。其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

【图例】

图中，x轴方向为数组的索引，y轴方向为待排序元素的值。

选择排序有两个很鲜明的特点：

运行时间和输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点。（无论数组的初始状态是什么，此算法效率都一样低效）

数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了N次交换——交换次数和数组的大小是线性关系。（我们将研究的其他任何算法都不具备这个特征）

【对于长度为N的数组，选择排序需要大约N²/2次比较和N次交换】

冒泡排序

思想：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。（较大的元素也会慢慢沉到底部。）

冒泡排序算法的运作如下：

1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤，除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

【图例】

图中，x轴方向为数组的索引，y轴方向为待排序元素的值。

由图中可看出，冒泡排序是从后到前，逐步有序的，最大的元素先沉到底部，接着是次大的……

void BubbleSort(Comparable[] a)
{
    //exchanged表示是否做过交换处理，一趟冒泡没有做过交换处理，即没有改变任何元素的位置，则停止冒泡。
    bool exchanged = false ; 

    int N = a.length ;
    
    //最多n-1趟冒泡排序(若发现某趟排序没有交换操作,则停止冒泡) 
    for (int i = 1; i < N && !exchanged; i++)
    {
        exchanged = false ;
        //从第0个到第N-1-i个 为一趟冒泡，选择出此趟中最大的值，沉到底部。
        for(j = 0; j < N-i; j++)
        {
            //若相邻的两关键字逆序 交换 
            if(a[j] > a[j+1])
            {
                exch(a[j], a[j+1]) ;    //交换a[j]、a[j+1]
                exchanged = true ;   //标记有元素交换位置 
            }
        }//for(j)
    }
}

特点：

冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n²)次交换，而插入排序只要最多O(n)交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行O(n²)，而插入排序在这个例子只需要O(n)个运算。

因此很多实现中避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序好的数列就无交换的需要。（例如上面代码）

插入排序

思想：将第i个元素与其左边的已经有序的元素一一比较，找到合适的位置，插入其中。为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。

具体算法描述如下：

1、从第一个元素开始，该元素可以认为已经被排序

2、取出下一个元素，在已经排序的元素序列中从后向前扫描

3、如果该元素（已排序）大于新元素，将该元素移到下一位置

4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

5、将新元素插入到该位置后

6、重复步骤2~5

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

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。对一个其中的元素已经有序(或接近有序)的数组进行排序，将会比对随机顺序的数组或是逆序数组进行排序要快得多。

【图例】

 使用插入排序为一列数字进行排序的过程。

从前到后逐步有序。

void sort(Comparable[] a)
{
    //将a[]按升序排列
    int N = a.length ;
    for (int i = 1; i < N; i++)
    {
        //将a[i]插入到a[i-1]、a[i-2]、a[i-3]……之中
        for (int j=i; j>=1 && less(a[j], a[j-1]); j--)
            exch(a, j, j-1) ;
    }
}

//在索引i由左向右变化的过程中，它左侧的元素总是有序的，所以当i到达数组的右端时排序就完成了。

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

【平均情况下插入排序需要~N²/4次比较以及~N²/4次交换。】

【当倒置(两元素颠倒)的数量很少时，插入排序很可能比其他任何排序算法都要快！】

【插入排序对于部分有序的数组十分高效，也很适合小规模数组。它也是高级排序算法的中间过程。】

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1、插入排序在对几乎已经排好序的数据操作时，效率高， 即可以达到线性排序的效率

2、对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。

希尔排序简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。（先将整个大数组基本有序，再对大数组来一次插入排序）

思想：使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。

我们只需要在插入排序的代码中将移动元素的距离改为h即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。

【图例】

void sort(Comparable[] a)
{
    //将a[]按升序排列
    int N = a.length ;
    int h = 1 ;
    
    //根据数组长度 选取适当的初始间隔h
    while (h < N/3)
        h = 3*h + 1 ;  //1,4,13,40,121,364,1093....
    
    //每次Shell排序的h逐渐减小
    while (h >= 1)
    {
        //将数组变为h有序
        for (int i = h; i < N; i++)
        {
            //将a[i]插入到a[i-h]、a[i-2*h]、a[i-3*h]……之中
            for (int j=i; j>=h && less(a[j], a[j-h]); j-=h)
                exch(a, j, j-h) ;
        }
        h = h/3 ;
    }
}

希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初，各个子数组都很短，排序之后子数组都是部分有序的，这两种情况都很适合插入排序。

希尔排序的算法性能不仅取决于h，还取决于h之间的数学性质。在实际应用中，使用3*h+1的递增序列基本就足够了。

【在最坏情况下希尔排序的比较次数和N^1.5成正比】

希尔排序的代码量很小，且不需要使用额外的内存空间。如果你需要解决一个排序问题而又没有系统排序函数可用（例如运行于嵌入式中的代码），可以先用希尔排序，然后再考虑是否值得将它替换为更加复杂的排序算法。

归并排序

思想：要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

【图例】

一个归并排序的例子:对一个随机点的链表进行排序。

void Sort(Comparable[] a)
{
    aux = new Comparable[a.length] ; //分配辅助空间
    sort(a, 0, a.length - 1) ;
}

void sort(Comparable[] a, int lo, int hi)
{
    //将数组a[lo....hi]排序
    if (hi <= lo) //只有一个元素，结束递归
        return ;
    
    int mid = lo + (hi - lo)/2 ;
    sort(a, lo, mid) ;      //将左半边排序
    sort(a, mid+1, hi) ;    //将右半边排序
    merge(a, lo, mid, hi) ; //归并结果
}
//原地归并
void merge(Comparable[] a, int lo, int mid, int hi)
{
    //将a[lo...mid]和a[mid+1...hi]归并
    int i = lo, j = mid+1;
    
    for (int k = lo; k <= hi; k++) //将a[lo..hi]复制到辅助数组aux[lo..hi]
        aux[k] = a[k] ;

    for (int k = lo; k <= hi; k++) //归并回到a[lo..hi]
        if (i > mid)
            a[k] = aux[j++] ;
        else if (j > hi)
            a[k] = aux[i++] ;
        else if (aux[j] < aux[i])
            a[k] = aux[j++] ;
        else
            a[k] = aux[i++] ;
}

改进：用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。（即增大递归的粒度，使递归在达到小范围时停止，而不是到一个元素时停止递归）

对排序来说，插入排序非常简单，因此很可能在小数组上比归并排序更快。使用插入排序处理小规模的子数组一般可以将归并排序的运行时间缩短10%~15%。

自底向上的归并排序

递归实现的归并排序是算法设计中分治思想的典型应用。我们可以把递归方式写成迭代的——先归并那些微型数组，然后再成对归并得到的子数组。

void sort(Comparable[] a)
{
    aux = new Comparable[a.length] ; //分配辅助空间
    int N = a.length ;
    
    for (int sz = 1; sz < N; sz = sz+sz)         //sz子数组大小
        for (int lo = 0; lo < N-sz; lo += sz+sz)  //一趟归并
            merge(a, lo, lo+sz-1, min(lo+sz+sz-1, N-1)) ;
}

自底向上的归并排序比较适合用链表组织的数据。这种方法只需要重新组织链表链接就能将链表原地排序（不需要创建任何新的链表结点）

【归并排序是一种渐进最优的基于比较排序的算法】

（即：归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~NlgN）

归并排序的缺点：它所需的额外空间和N成正比。

快速排序

思想：快速排序是一种分治的排序算法。它将一个数组分成两个子数组，将两部分独立地排序。

一般策略是先随意地取a[lo]作为切分元素，即那个将会被排定的元素，然后我们从数组的左端开始向右端扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素。

void  sort(Comparable[] a, int lo, int hi)
{
    if (hi <= lo)
        return ;
    int  j = partition(a, lo, hi) ; //切分
    sort(a, lo, j-1) ;          //将左半部分排序
    sort(a, j+1, hi) ;          //将右半部分排序
}
//快速排序的切分
int  partition(Comparable[] a, int lo, int hi)
{
    int  i = lo , j = hi + 1 ;  //左右扫描指针
    Comparable v = a[lo] ;  //切分元素
    
    while (true)
    {
        //扫描左右，检查扫描是否结束并交换元素
        while (less(a[++i], v))  if (i == hi) break ;
        while (less(v, a[--j]))  if (j == lo) break ;
        if (i >= j)
            break ;
        exch(a, i, j) ;
    }
    
    return j ;
}

快速排序的特点是原地排序（只需要一个很小的辅助栈），且将长度为N的数组排序所需的时间和NlgN成正比。

缺点：在切分不平衡时这个程序可能会极为低效。

改进：切换到插入排序

和大多数数组递归排序算法一样，改进快速排序性能的一个简单办法基于以下两点：

对于小数组，快速排序比插入排序慢。

因为递归，快速排序的sort()方法在小数组中也会调用自己。

因此，在排序小数组时应该切换到插入排序。

将 sort()中的语句 if (hi <= lo)  return ;

替换成:          if (hi <= lo + M)  { Insertion.sort(a, lo, hi);  return; }

●三向切分的快排

在实际应用中经常会出现含有大量重复元素的数组。

在有大量重复元素的情况下，快速排序的递归性会使元素全部重复的子数组经常出现，这就有很大的改进潜力，将当前实现的线性对数级的性能提高到线性级别。

一个简单的想法是将数组切分为三部分，分别对应小于、等于和大于切分元素的数组元素。

void sort(Comparable[] a, int lo. int hi)
{
    if (hi <= lo)
        return ;
    int lt = lo, i = lo+1, gt = hi ;
    Comparable v = a[lo] ;
    
    while (i <= gt)
    {
        if (a[i] < v)
            exch(a, lt++, i++) ; //a[i]比v小 把a[i]值放入[lo...lt-1]集合中
        else if (a[i] > v)
            exch(a, i, gt--) ;   //a[i]比v大 把a[i]值放入尾部
        else
            i++ ;
    }
    
    sort(a, lo, lt-1) ;
    sort(a, gt+1, hi) ;
}

这段排序代码的切分能够将和切分元素相等的元素归位，这样它们就不会被包含在递归调用处理的子数组之中。对于存在大量重复元素的数组，这种方法比标准的快速排序的效率高的多。

优先队列

许多应用程序都需要处理有序的元素，但不一定要求它们全部有序，或是不一定要一次将它们排序。很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素，如此这般。

在这种情况下，一个合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。

数据结构二叉堆能够很好地实现优先队列的基本操作。

当一颗二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。（大顶堆）

堆的算法

我们用长度为N+1的私有数组pq[]来表示一个大小为N的堆，我们不会使用pq[0]，堆元素放在pq[1]至pq[N]中。

在有序化的过程中我们会遇到两种情况：

当某个结点的优先级上升（或是在堆底加入一个新的元素）时，我们需要由下至上恢复堆的顺序。

当某个结点的优先级下降（例如，将根结点替换为一个较小的元素）时，我们需要由上至下恢复堆的顺序。

·由下至上的堆有序化（上浮）

如果堆的有序状态因为某个结点变得比它的父结点更大而被打破，那么我们就需要通过交换它和它的父结点来修复堆。

交换后，这个结点比它的两个子结点都大，但这个结点仍然可能比它现在的父结点更大。我们可以一遍遍地用同样的办法恢复秩序，将这个结点不断向上移动直到我们遇到了一个更大的父结点。（溯流而上）

void swim(int k)
{
    while (k > 1 && less(k/2, k))
    {
        exch(k/2, k) ;
        k = k/2 ;
    }
}

·由上至下的堆有序化（下沉）

如果堆得有序状态因为某个结点变得比它的某子结点更小而被打破了，那么我们可以通过将它和它的两个子结点中的较大者交换来恢复堆。

交换可能会在子结点处继续打破堆的有序状态，因此我们需要不断地用相同的方式将其修复，将结点向下移动直到它的子结点都比它更小或是到达了堆的底部。（顺流而下）

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 ;
        exch(k, j) ;
        k = j ;
    }
}

堆排序

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将它们按顺序删去。

1.堆的构造：

由N个给定的元素构造一个堆，从右至左用sink()下沉函数构造子堆。开始时我们只需要扫描数组中的一半元素，因为我们可以跳过大小为1的子堆，由此向前对每个结点sink()，直到我们在位置1上调用sink()方法，扫描结束。

（用下沉操作由N个元素构造堆只需要少于2N次比较以及少于N次交换）

（如果我们从左至右用swim()上浮操作遍历数组，则需要用NlogN成正比的时间完成）

for (int k = N/2; k>= 1; k--)

    sink(a, k, N) ;

2.下沉排序：

堆排序的主要工作都是在第二阶段完成的。这里我们将堆中的最大元素删除，然后放入堆缩小后数组中空出的位置。

这个过程和选择排序有些类似（一步一步选出最值），但所需的比较要少的多，因为堆提供了一种从未排序部分找到最大元素的有效方法。

while (N > 1)

{

    exch(a, 1, N--) ; //把堆尾结点与堆顶最大元素交换

    sink(a, 1, N) ;   //对改变后的堆顶结点下沉操作

}

void sort(Comparable[] a)
{
    int n = a.length ;
    
    for (int k = N/2; k >= 1; k--)
        sink(a, k, N) ;

    while (N > 1)
    {
        exch(a, 1, N--) ; //把堆尾结点与堆顶最大元素交换
        sink(a, 1, N) ;  //对改变后的堆顶结点下沉操作
    }
}

特点：堆排序是我们所知的唯一能够同时最优地利用空间和时间的方法——在最坏的情况下它也能保证使用~2NlgN次比较和恒定的额外空间。

当空间十分紧张的时候（例如在嵌入式系统）它很流行，因为它只用几行就能实现较好的性能。但现代系统的许多应用很少使用它，因为它无法利用缓存。其数组元素很少和相邻的其他元素进行比较，因此其缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快速排序、归并排序，甚至是希尔排序。

应用：

TopM问题：

在某些数据处理的例子里，总数据量太大，无法排序（甚至无法全部装进内存）。如果你需要从10亿个元素中选出最大的十个，你真的想把一个10亿规模的数组排序吗？但有了优先队列，你就只用一个能存储十个元素的队列即可。

【例】

100w个数中找出最大的100个数。

答：

先把这100W个数分别放在100个文件中（每个文件存放1W个数）。

再用优先队列：在每个文件中求出TOP100，可以采用包含100个元素的堆完成（TOP100小，用最大堆，TOP100大，用最小堆，比如求TOP100大，我们首先取前100个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP100大）。

求出每个文件中的TOP100后，然后把这100个文件的TOP100组合起来，共1W个数据，再利用上面类似的方法求出TOP100就可以了。