各类排序算法总结

三.交换类排序[接上]

2.快速排序

快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序.

如果每次划分对一个元素定位后,该元素的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况!

【算法如下】

//伪码表示
//一趟快速排序算法：
int Partition1 (Elem R[], int low, int high)
{
    pivotkey = R[low].key; // 用子表的第一个记录作枢轴记录
    while (low<high)   // 从表的两端交替地向中间扫描
    {
        while (low<high && R[high].key>=pivotkey)
        {
            --high;
        }
        R[low]←→R[high]; // 将比枢轴记录小的记录交换到低端

        while (low<high && R[low].key<=pivotkey)
        {
            ++low;
        }
        R[low]←→R[high]; // 将比枢轴记录大的记录交换到高端
    }

    return low; // 返回枢轴所在位置
}

容易看出，调整过程中的枢轴位置并不重要，因此，为了减少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记录应在的位置之后(此时low=high),再将枢轴记录到位。

将上述“一次划分”的算法改写如下：

int Partition2 (Elem R[], int low, int high)
{
    R[0] = R[low]; // 用子表的第一个记录作枢轴记录
    pivotkey = R[low].key; // 枢轴记录关键字

    while (low < high)   // 从表的两端交替地向中间扫描
    {
        while (low<high && R[high].key>=pivotkey)
        {
            --high;
        }
        R[low] = R[high]; // 将比枢轴记录小的记录移到低端

        while (low<high && R[low].key<=pivotkey)
        {
            ++low;
        }
        R[high] = R[low]; // 将比枢轴记录大的记录移到高端
    }
    R[low] = R[0]; // 枢轴记录到位

    return low; // 返回枢轴位置
}

//递归形式的快速排序算法：
void QSort (Elem R[], int low, int high)
{
    // 对记录序列R[low..high]进行快速排序
    if (low < high-1)   // 长度大于1
    {
        pivotloc = Partition(L, low, high); // 将L.r[low..high]一分为二
        QSort(L, low, pivotloc-1); // 对低子表递归排序，pivotloc 是枢轴位置
        QSort(L, pivotloc+1, high); // 对高子表递归排序
    }
}

void QuickSort(Elem R[], int n)   // 对记录序列进行快速排序
{
    QSort(R, 1, n);
}

【性能分析】

(1)空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。

(2)时间效率：在n 个记录的待排序列中，一次划分需要约 n 次关键码比较，时效为O(n)，若设T(n)为对 n 个记录的待排序列进行快速排序所需时间。理想情况下：每次划分，正好将分成两个等长的子序列，则

   T(n)≤cn+2T(n/2)							c 是一个常数
≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)
≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)
······
≤cnlog2n+nT(1)=O(nlog2n)

可以证明,QuickSort的平均计算也是O(nlog2n).

最坏情况下：即每次划分，只得到一个子序列，时效为O(n^2)。

快速排序是通常被认为在同数量级O(nlog2n)的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。

(3)快速排序是一个不稳定的排序方法.

(4) 最惨情况:空间复杂度->O(n),时间复杂度->O(n^2)

平均情况:空间复杂度->O(log2n),时间复杂度->O(nlog2n)

(5)快速排序比较适用于输入规模n较大的情况.

四.选择类排序

1.选择排序

简单选择排序是最简单的一种选择类的排序方法。假设排序过程中，待排记录序列的状态为：

并且有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i 趟简单选择排序是，从无序序列R[i..n]的n-i+1 记录中选出关键字最小的记录加入有序序列。

操作方法：第一趟，从n 个记录中找出关键码最小的记录与第1 个记录交换；第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第2 个记录交换；如此，第i趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第 i 个记录交换，直到整个序列按关键码有序。

【算法如下】

//C++代码
int selectMinIndex(int *A,int index,int length)
{
    int min = index;
    for (int i = index+1; i != length; ++i)
    {
        if (A[i] < A[min])
        {
            min = i;
        }
    }

    return min;
}

void selectSort(int *A,int length)
{
    for (int i = 0; i != length; ++i)
    {
        int k = selectMinIndex(A,i,length);

        if (k != i)
        {
            int temp = A[i];
            A[i] = A[k];
            A[k] = temp;
        }
    }
}

【性能分析】

(1)空间效率：仅用了一个辅助单元，空间复杂度为O(1)。

(2)时间效率：简单选择排序的最好和平均时间复杂度均为O(n^2)。

(3)稳定性：不同教材对简单选择排序的稳定性有争议，一般认为，若是从前往后比较来选择第i 小的记录则该算法是稳定的，若是从后往前比较来选择第i 小的记录则该算法是不稳定的。

2.堆排序

堆排序的特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果.

堆的定义: 堆是满足下列性质的数列{r1, r2, …，rn}：

若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。

由此，若上述数列是堆，则r1 必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。

堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：设有 n 个元素，将其按关键码排序。首先将这 n 个元素按关键码建成堆，将堆顶元素输出，得到n 个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1 个元素建成堆，输出堆顶元素，得到n 个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

（1）如何将n 个元素的序列按关键码建成堆。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。n 个结点的完全二叉树，则最后一个结点是第 n/2 个结点的孩子。对第 n/2 个结点为根的子树筛选，使该子树成为堆，之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

（2）输出堆顶元素后，怎样调整剩余n-1 个元素，使其按关键码成为一个新堆。

调整方法：设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶，堆被破坏，其原因仅是根结点不满足堆的性质。将根结点与左、右孩子中较小(或小大)的进行交换。若与左子女交换，则左子树堆被破坏，且仅左子树的根结点不满足堆的性质；若与右子女交换，则右子树堆被破坏，且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。称这个自根结点到叶子结点的调整过程为筛选。

【算法如下】

堆排序的算法如下所示：

void heapSort ( Elem R[], int n )   // 对记录序列R[1..n]进行堆排序。
{
    for ( i=n/2; i>0; --i )         // 把R[1..n]建成大顶堆
        HeapAdjust ( R, i, n );

    for ( i=n; i>1; --i )
    {
        R[1]←→R[i];
        //将堆顶记录和当前未经排序子序列,R[1..i]中最后一个记录相互交换
        HeapAdjust(R, 1, i-1);      // 将R[1..i-1] 重新调整为大顶堆
    }
}?

其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。

void HeapAdjust (Elem R[], int s, int m)
{
    /* 已知R[s..m]中记录的关键字除R[s].key 之外均满足堆的定义，本函数调整R[s] 的关
    键字，使R[s..m]成为一个大顶堆（对其中记录的关键字而言）*/
    rc = R[s];
    for ( j=2*s; j<=m; j*=2 )   // 沿key 较大的孩子结点向下筛选
    {
        if ( j<m && R[j].key<R[j+1].key )
            ++j; // j 为key 较大的记录的下标

        if ( rc.key >= R[j].key )
            break; // rc 应插入在位置s 上

        R[s] = R[j];
        s = j;
    }

    R[s] = rc; // 插入
}

【性能分析】

（1）空间效率：仅用了一个辅助单元，空间复杂度为O(1)。

（2）时间效率：

①对深度为k 的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);

②对n 个关键字，建成深度为h(=?log2n?+1)的堆，所需进行的关键字比较的次数至多为4n;

③调整“堆顶”n-1 次，总共进行的关键字比较的次数不超过

2(?log2(n-1)?+ ?log2(n-2)?+ …+log22)<2n(?log2n?)

因此，堆排序的平均和最坏时间复杂度均为O(nlogn)。

(3)堆排序是一个不稳定的排序方法。

2.二路归并排序:

【算法思想】

归并排序的基本思想是：将两个或两个以上的有序子序列“归并”为一个有序序列。

在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列，

空间复杂度为O(n),稳定,时间复杂度O(nlog2n)

【算法如下】

//伪代码,不一定能够运行
void Merge(Elem SR[], Elem TR[], int i, int m, int n)
{
// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]
    for (j=m+1, k=i; i<=m && j<=n; ++k)   // 将SR 中记录由小到大地并入TR
    {
        if (SR[i].key<=SR[j].key)
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }

    if (i<=m)
        TR[k..n] = SR[i..m]; // 将剩余的SR[i..m]复制到TR
    if (j<=n)
        TR[k..n] = SR[j..n]; // 将剩余的SR[j..n]复制到TR
}

归并排序的算法可以有两种形式：递归的和递推的，它是由两种不同的程序设计思想得出的。

在此，只讨论递归形式的算法，这是一种自顶向下的分析方法：如果记录无序序列R[s..t]的两部分R[s..?(s+t)/2?]和R[?(s+t)/2+1..t?]分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。

void Msort ( Elem SR[], Elem TR1[], int s, int t )
{
    if (s==t)
        TR1[s] = SR[s];
    else
    {
        m = (s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]

        Msort (SR, TR2, s, m);
        // 递归地将SR[s..m]归并为有序的TR2[s..m]
        Msort (SR, TR2, m+1, t);
        //递归地SR[m+1..t]归并为有序的TR2[m+1..t]
        Merge (TR2, TR1, s, m, t);
        // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
    }
}

void MergeSort (Elem R[])   // 对记录序列R[1..n]作2-路归并排序。
{
    MSort(R, R, 1, n);
}

【性能分析】

(1)空间效率：需要一个与表等长的辅助元素数组空间，所以空间复杂度为O(n)。

(2)时间效率：对n 个元素的表，将这n 个元素看作叶结点，若将两两归并生成的子表看作它们的父结点，则归并过程对应由叶向根生成一棵二叉树的过程。所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n 次，故时间复杂度为O(nlog2n)。

(3)稳定性：归并排序是一个稳定的排序方法。