@qiezhian 2014-11-15T08:40:34.000000Z 字数 10299 阅读 1434

排序算法总结

算法
本文总结最常用的几个排序算法，包括插入、冒泡、shell排序、归并排序、快速排序、堆排序等，并分析其空间和时间复杂度。剩余几种排序算法，如堆排序、基数排序、桶排序等会在下次文章更新中补充。本文给出C++代码并封装为类CSort。本文总结大部分取自《数据结构与算法分析》[1]一书。
本文描述算法都将接收一个含有元素的数组和一个包含元素个数的整数。本文给出的代码假设函数调用者给的参数是合法的。

排序算法总结

冒泡排序

原理：冒泡排序算法的运作如下[2]：（从后往前）
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
分析：冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。冒泡排序最好的时间复杂度为 $\Theta (N)$ 。若初始文件是反序的，需要进行N-1趟排序，每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置，此种情况下时间界为 $\Theta (N^2)$ 。平均情况下时间界也为 $\Theta (N^2)$ 。下面给出的代码是将小的元素往前调。

template<typename T>
void CSort<T>::BubbleSort( T A[], const int N)
{
    int i, j;
    for( i=0; i<N; i++)
        for( j=N-1; j>=i; j--)
            if( A[j-1] > A[j] )
                Swap( &A[j-1], &A[j] );
}

选择排序

原理[3] ：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。
分析：平均时间复杂度 $\Theta (N^2)$ 。选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。比较次数 $\Theta (N^2)$ ,比较次数与关键字的初始状态无关，总的比较次数

N = (n - 1) + (n - 2) + . . . + 1 = n * (n - 1) / 2

$N=(n-1)+(n-2)+...+1=n*(n-1)/2$ 交换次数

Θ(N) $\Theta (N)$ ,最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

template<typename T>
void CSort<T>::SelectSort( T A[], const int N)
{
    int min, index;
    int i, j;
    for( i=0; i<N-1; i++)
    {
        min = A[i];
        index = i;
        for( j=i; j<N; j++)
            if( A[j]<min )
            {
                min = A[j];
                index = j;
            }
        if( index!=i )
            Swap( &A[i], &A[index] );
    }
}

插入排序

原理：插入排序 (insertion sort) 是一种基于比较的排序算法。假设元素个数为N,那么插入排序由N-1趟排序完成。对于第P(0<p<N)趟排序，插入排序保证位置0到位置P-1的元素是排过序的。所以经过N-1趟排序之后，整个序列都能保证是有序的。
分析：插入排序最坏情况的时间复杂度为 $\Theta (N^2)$ 。最好的情况为初始序列已排序，复杂度为 $\Theta (N)$ ，如果输入几乎被排序，则插入排序运行较快。平均情况下，时间复杂度为 $\Theta (N^2)$ 。
N个互异数的数组的平均逆序数为 $N(N-1)/4$ ，通过交换相邻元素进行排序只能减少一个逆序，所以通过交换相邻元素进行排序的任何算法平均需要 $\Theta (N^2)$ 时间。这个时间下界说明，为使一个排序算法以亚二次时间运行，需要对相距较远的元素进行交换，使得每一次交换减少不止一个逆序。

template<typename T>
void CSort<T>::InsertSort(T A[], const int N)
{
    if( A==NULL || N<=0 )
        return;
    int i, j;
    //start from index 1
    for( i=1; i<N; i++)
        for( j=i; j>0 && ( A[j]<A[j-1] ); j--)
            Swap( &A[j], &A[j-1]);
}

Shell排序

原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。从下面的代码也可以看出，Shell排序与插入排序的关系。当Increment=1时，Shell排序就是插入排序。
交换元素A[i]和A[i+k]，它们最初是无序的，则减掉的逆序数最少为1个最多为2k-1个。Shell排序就是根据这个事实，在Icrement较大的时候，通过交换一次较远元素可以减少多个逆序。当Increment=1时，序列几乎已经被排好序，所以速度较快。
分析：增量序列的选取对算法性能有很大的影响。常用的增量序列为N/2,N/4 ... 1。Shell排序的时间界分析比较复杂，在使用上述增量序列时，最坏时间界为 $\Theta (N^2)$ 。

template<typename T>
void CSort<T>::ShellSort( T A[], const int N)
{
    int Increment;
    int i, j;
    for( Increment=N/2; Increment>0; Increment/=2)
        for( i=Increment; i<N; i++)
            for( j=i; j>=Increment && A[j]<A[j-Increment]; j-=Increment)
                Swap( &A[j], &A[j-Increment]);
}

归并排序

原理：归并排序的基本操作是合并两个已排好序的表。对表A进行排序可分解为三步：
1.将表A分解成表B和表C，B和C不相交
2.B、C分别排序
3.合并B、C得到排序后表A
从上述过程可以看出，归并排序是个典型的分治算法，它将问题分解成一些小问题并递归求解，而治的阶段将分的阶段得到的结果补到一起。下面给出的代码从中间位置对表进行分割。
分析：归并排序需要额外的 $\Theta (N)$ 空间用来合并子表B和C，最后再将此合并表数据Copy回表A。归并排序以 $\Theta (N \log{N})$ 的最坏时间界运行，所使用的比较次数几乎是最优的。但是它很难用于主存排序，主要问题在于合并两个排序子表需要线性附加内存，还要花费线性数据拷贝时间，严重拖慢了排序速度。

//非递归实现
template<typename T>
void CSort<T>::MergeSortNonR( T A[], const int N)
{
    int Increment=1;
    if( N<=Increment )
        return;
    T* Tmp;
    Tmp = (T*) malloc( N*sizeof(T) );
    if( Tmp==NULL )
        return;
    int i,j;
    for( ; Increment<N; Increment*=2 )
        for( i=0; i+Increment<N; i+=2*Increment)
            Merge( A, Tmp, i, i+Increment, ( N-1>i+2*Increment-1 ? (i+2*Increment-1):(N-1) ) );
}
//递归实现
template<typename T>
void CSort<T>::MergeSort( T A[], const int N)
{
    if( A==NULL || N<=0 )
        return;
    T *Tmp;
    Tmp = (T*)malloc( N*sizeof(T));
    if(Tmp)
    {
        MSort( A, Tmp, 0, N-1);
        free( Tmp );
    }
    else
        return;
}
template<typename T>
void CSort<T>:: MSort( T A[], T Tmp[], int Left, int Right)
{
    if( Left<Right)
    {
        int center =(Left + Right)/2;
        MSort( A, Tmp, Left,center);
        MSort( A, Tmp, center+1,Right);
        Merge( A, Tmp, Left, center+1, Right);
    }
}
template<typename T>
void CSort<T>::Merge( T A[], T Tmp[], int LPos, int RPos, int RightEnd)
{
    int i, j;
    int TmpPos, LeftPos, LeftEnd, RightPos;
    int NumElements;
    NumElements = RightEnd - LPos +1;
    TmpPos = LPos;
    LeftPos = LPos;
    LeftEnd = RPos-1;
    RightPos = RPos;
    while( LeftPos<=LeftEnd && RightPos<=RightEnd)
    {
        if( A[LeftPos]<A[RightPos] )
            Tmp[TmpPos++] = A[LeftPos++];
        else
            Tmp[TmpPos++] = A[RightPos++];
    }
    while( LeftPos<=LeftEnd )
        Tmp[TmpPos++] = A[LeftPos++];
    while( RightPos<=RightEnd )
        Tmp[TmpPos++] = A[RightPos++];
    //copy Tmp[] data back to A[]
    for( i=LPos; i<=RightEnd; i++)
        A[i] = Tmp[i];
}

快速排序

原理：将数组 $S$ 排序的基本算法由四步组成：
1.如果 $S$ 中元素个数为0或1,则返回
2.取 $S$ 中任意元素 $v$ ，称之为枢纽元
3.将 $S$ 中其他元素分成两个不相交集合 $S_{1}$ 和 $S_{2}$ ， $S_{1}$ 中元素均小于v， $S_{2}$ 中元素均大于 $v$
4.返回排序后 $S$ : ${quicksort(S_{1}),v,quicksort(S_{2})}$
分析：快速排序是在实践中最快的已知排序算法，它的平均运行时间界 $\Theta (N \log{N})$ ，它的最坏情形时间界为 $\Theta (N^2)$ 。一个影响因素是第2步中枢纽元的选取，它影响到第3步分割，继而影响排序性能。一半常用的策略取中间位置元素，或者在首位、中间位、最后位中选择三者的中值作为枢纽元。下面代码给出的是取中间位置元素作为枢纽元。

template<typename T>
void CSort<T>::QuickSort(T A[],const int N)
{
    QSort( A, 0, N-1);
}
template<typename T>
void CSort<T>::QSort( T A[], int Left, int Right)
{
    if( A==NULL || Left>=Right )
        return;
    int index;
    int i, j;
    index = ( Left+Right )/2;
    Swap( &A[index],&A[Right] );//swap the pivot value to the last position of A[]
    for( i=Left-1, j=Right;;)
    {
        while( A[++i]<A[Right] );
        while( A[--j]>A[Right] );
        if( i<j )
            Swap( &A[i], &A[j] );
        else
            break;
    }
    Swap( &A[i], &A[Right] );//swap back 
    QSort( A, Left, i-1);
    QSort( A, i+1, Right);
}

堆排序

堆排序首先花费 $\Theta(N)$ 时间建立二叉堆，然后执行N次DeleteMin操作，按照操作顺序，最小的元素先例开该堆，最后得到已排序序列。堆排序关键在于理解二叉堆的构造，会在下篇文章中介绍。这里先给出代码。

template<typename T>
void CSort<T>::PercDown( T A[], int i, int N)
{
    int nChild;
    T Tmp;
    for( Tmp=A[i]; (2*i+1)<N; i=nChild)
    {
        nChild = ( 2*i+1 );
        if( ( nChild!=N-1 ) && ( A[nChild+1]>A[nChild] ) )
            nChild++;
        if( A[nChild] > Tmp )
            A[i] = A[nChild];
        else
            break;
    }
    A[i] = Tmp;
}
template<typename T>
void CSort<T>::BuildHeap(T A[], const int N)
{
    int i;
    for( i=N/2; i>=0; i--)
        PercDown( A, i, N);
}
template<typename T>
void CSort<T>::HeapSort( T A[], const int N)
{
    int i;
    BuildHeap( A, N);
    for( i=N-1; i>=0; i--)
    {
        Swap( &A[0], &A[i] );
        PercDown( A, 0, i);
    }
}

性能分析

算法	插入排序	冒泡排序	选择排序	Shell排序	堆排序	快速排序
已排序	$O(N)$
全逆序	$O(N^2)$
平均情况	$O(N^2)$

实现

最后给出本文完整代码，包括sort.hpp文件与sort.cpp文件。

/********************************************************************************
FileName:   sort.h
Version:    14.6.11
Author:     Qie Zhian
Data:       2014-6-11
Comment:
*********************************************************************************/
#ifndef _SORT_H_
#define _SORT_H_
#include "stdlib.h"
#include "stdio.h"
template<typename T>
class CSort
{
private:
    void Swap( T *a, T *b);
    // for HeapSort() function
    void BuildHeap( T A[], const int N);
    void PercDown( T A[], int i, int N);
    //for MergeSort() function
    void MSort( T A[], T Tmp[], int Left, int Right);
    void Merge( T A[], T Tmp[], int LPos, int RPos, int RightEnd);
    //for QuickSort() function
    void QSort( T A[], int Left, int Right);
public:
    void InsertSort(T A[], const int N);
    void BucketSort( T A[], const int N); 
    void ShellSort( T A[], const int N);
    void MergeSort( T A[], const int N);
    void MergeSortNonR( T A[], const int N);
    void QuickSort( T A[], const int N);
    void BubbleSort( T A[], const int N);
    void SelectSort( T A[], const int N);
    void HeapSort( T A[], const int N);
};
template<typename T>
void CSort<T>::Swap( T *a, T *b)
{
    T Tmp;
    Tmp = *a;
    *a = *b;
    *b = Tmp;
}   
template<typename T>
void CSort<T>::PercDown( T A[], int i, int N)
{
    int nChild;
    T Tmp;
    for( Tmp=A[i]; (2*i+1)<N; i=nChild)
    {
        nChild = ( 2*i+1 );
        if( ( nChild!=N-1 ) && ( A[nChild+1]>A[nChild] ) )
            nChild++;
        if( A[nChild] > Tmp )
            A[i] = A[nChild];
        else
            break;
    }
    A[i] = Tmp;
}
template<typename T>
void CSort<T>::BuildHeap(T A[], const int N)
{
    int i;
    for( i=N/2; i>=0; i--)
        PercDown( A, i, N);
}
template<typename T>
void CSort<T>::HeapSort( T A[], const int N)
{
    int i;
    BuildHeap( A, N);
    for( i=N-1; i>=0; i--)
    {
        Swap( &A[0], &A[i] );
        PercDown( A, 0, i);
    }
}
template<typename T>
void CSort<T>::InsertSort(T A[], const int N)
{
    if( A==NULL || N<=0 )
        return;
    int i, j;
    //start from index 1
    for( i=1; i<N; i++)
        for( j=i; j>0 && ( A[j]<A[j-1] ); j--)
            Swap( &A[j], &A[j-1]);
}
template<typename T>
void CSort<T>::MergeSortNonR( T A[], const int N)
{
    int Increment=1;
    if( N<=Increment )
        return;
    T* Tmp;
    Tmp = (T*) malloc( N*sizeof(T) );
    if( Tmp==NULL )
        return;
    int i,j;
    for( ; Increment<N; Increment*=2 )
        for( i=0; i+Increment<N; i+=2*Increment)
            Merge( A, Tmp, i, i+Increment, ( N-1>i+2*Increment-1 ? (i+2*Increment-1):(N-1) ) );
}
template<typename T>
void CSort<T>::MergeSort( T A[], const int N)
{
    if( A==NULL || N<=0 )
        return;
    T *Tmp;
    Tmp = (T*)malloc( N*sizeof(T));
    if(Tmp)
    {
        MSort( A, Tmp, 0, N-1);
        free( Tmp );
    }
    else
        return;
}
template<typename T>
void CSort<T>:: MSort( T A[], T Tmp[], int Left, int Right)
{
    if( Left<Right)
    {
        int center =(Left + Right)/2;
        MSort( A, Tmp, Left,center);
        MSort( A, Tmp, center+1,Right);
        Merge( A, Tmp, Left, center+1, Right);
    }
}
template<typename T>
void CSort<T>::Merge( T A[], T Tmp[], int LPos, int RPos, int RightEnd)
{
    int i, j;
    int TmpPos, LeftPos, LeftEnd, RightPos;
    int NumElements;
    NumElements = RightEnd - LPos +1;
    TmpPos = LPos;
    LeftPos = LPos;
    LeftEnd = RPos-1;
    RightPos = RPos;
    while( LeftPos<=LeftEnd && RightPos<=RightEnd)
    {
        if( A[LeftPos]<A[RightPos] )
            Tmp[TmpPos++] = A[LeftPos++];
        else
            Tmp[TmpPos++] = A[RightPos++];
    }
    while( LeftPos<=LeftEnd )
        Tmp[TmpPos++] = A[LeftPos++];
    while( RightPos<=RightEnd )
        Tmp[TmpPos++] = A[RightPos++];
    //copy Tmp[] data back to A[]
    for( i=LPos; i<=RightEnd; i++)
        A[i] = Tmp[i];
}
template<typename T>
void CSort<T>::ShellSort( T A[], const int N)
{
    int Increment;
    int i, j;
    for( Increment=N/2; Increment>0; Increment/=2)
        for( i=Increment; i<N; i++)
            for( j=i; j>=Increment && A[j]<A[j-Increment]; j-=Increment)
                Swap( &A[j], &A[j-Increment]);
}
template<typename T>
void CSort<T>::QuickSort(T A[],const int N)
{
    QSort( A, 0, N-1);
}
template<typename T>
void CSort<T>::QSort( T A[], int Left, int Right)
{
    if( A==NULL || Left>=Right )
        return;
    int index;
    int i, j;
    index = ( Left+Right )/2;
    Swap( &A[index],&A[Right] );//swap the pivot value to the last position of A[]
    for( i=Left-1, j=Right;;)
    {
        while( A[++i]<A[Right] );
        while( A[--j]>A[Right] );
        if( i<j )
            Swap( &A[i], &A[j] );
        else
            break;
    }
    Swap( &A[i], &A[Right] );
    QSort( A, Left, i-1);
    QSort( A, i+1, Right);
}
template<typename T>
void CSort<T>::BubbleSort( T A[], const int N)
{
    int i, j;
    for( i=0; i<N; i++)
        for( j=N-1; j>=i; j--)
            if( A[j-1] > A[j] )
                Swap( &A[j-1], &A[j] );
}
template<typename T>
void CSort<T>::SelectSort( T A[], const int N)
{
    int min, index;
    int i, j;
    for( i=0; i<N-1; i++)
    {
        min = A[i];
        index = i;
        for( j=i; j<N; j++)
            if( A[j]<min )
            {
                min = A[j];
                index = j;
            }
        if( index!=i )
            Swap( &A[i], &A[index] );
    }
}
#endif
#endif

/*****************************************************************************
FileName:   sort.cpp
Version:    14.6.11
Author:     Qie 
Data:       2014-6-11
Comment:
******************************************************************************/
#include <iostream>
#include "sort.hpp"
using namespace std;
int main()
{
    int A[]={9,8,7,6,5,4,3,2,1,2,5,6};
    int N=sizeof(A)/sizeof(int);
    CSort<int> sort_int;
//  sort_int.InsertSort(A,N);
//  sort_int.MergeSort(A,N);
//  sort_int.ShellSort(A,N);
//  sort_int.QuickSort(A,N);
//  sort_int.BubbleSort(A,N);
//  sort_int.SelectSort(A,N);
//  sort_int.HeapSort(A,N);
    sort_int.MergeSortNonR(A,N);
    int i;
    for(i=0;i<N;i++)
        cout<< A[i]<<endl;
}

[1] Mark Allen Weiss ,数据结构与算法分析--C语言描述，第二版，机械工业出版社 ↩
[2] http://baike.baidu.com/view/254413.htm?fr=aladdin ↩
[3] http://blog.csdn.net/cjf_iceking/article/details/7914554 ↩