排序算法2

简单排序算法

公用部分

#define MAXSIZE 10
typedef struct {
    int r[MAXSIZE+1];//r[0]用作哨兵或临时变量
    int length;
}SqList;

void swap(SqList *L,int i,int j)
{
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

堆排序

堆是具有下列性质的完全二叉树：

  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
  • 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将他移走，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列。

void HaepSort(SqList *L)
{
    int i;
    //构造大顶堆
    for(i=L->length/2;i>0;i--)/*序列从0到L->length/2，都是有孩子的结点*/
    {
        HeapAdjust(L,i,L->length);
    }
    //将堆顶元素和最后一个元素交换，得到有序序列
    for(i=L->length;i>1;i++)
    {
        swap(L,1,i);
        HeapAdjust(L,1,i-1);
    }
}

void HeapAdjust(SqList *L,int s,int m)
{
    int temp,j;
    temp = L->r[s];
    for(j=2*s;j<=m;j*=2)//找到左右子结点
    {
        if(j < m && L->r[j] < L->r[j+1])//找到相对较大的孩子结点
            ++j;
        if(temp >= L->r[j])
            break;
        //交换值
        L->r[s] = L->r[j];
        s = j;
        //若j*=2后小于等于m,则继续向下层执行
    }
    //交换值
    L->r[s] = temp;
}

归并排序

假设初始序列有含有n个记录，则可以看成是n个有序序列的子序列，每个子序列的长度为1，然后两辆归并，得到[n/2]个长度为2或1的有序子序列；再两两归并…..，如此重复，直到得到一个长度为n的有序序列。

void MergeSort(SqList *L)
{
    MSort(L->r,L->r,1,L->length);
}

void MSort(int SR[],int TR1[],int s,int t)
{
    int m;
    int TR2[MAXSIZE+1];
    if(s==t)
    {
        TR1[s] = SR[s];
    }
    else
    {
        m = (s + t)/2;//划分序列
        MSort(SR,TR2,s,m);//递归调用排序子序列
        MSort(SR,TR2,m+1,t);//递归调用排序子序列
        Merge(TR2,TR1,s,m,t);//合并子序列
    }
}

void Merge(int SR[],int TR[],int i,int m,int n)
{
    int j,k,l;
    //把较小的插入TR中
    for(j=m+1,k=i;i<=m && j<=n;k++)
    {
        if(SR[i] < SR[j])
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }
    //若还有剩余的，则连续插入后端即可
    if(i <= m)
    {
        for(l=0;l<=m-i;l++)
            TR[k+l] = SR[i+l];
    }
    if(j<=n)
    {
        for(l=0;l<=n-j;l++)
            TR[k+l] = SR[i+l];
    }
}

非递归实现

void MergeSort2(SqList *L)
{   
    //申请额外的空间
    int* TR = (int *)malloc(L->length * sizeof(int));

    int k = 1;
    while(k < L->length)
    {
        MergePass(L->r,TR,k,L->length);
        k = k * 2;//子序列长度加倍
        MergePass(TR,L->r,k,L->length);
        k = k * 2;
    }
}

void MergePass(int SR[],int TR[],int s,int n)
{
    int i = 1;
    int j;
    while(i <= n- 2*s +1)
    {
        Merge(SR,TR,i,i+s-1,i- 2*s +1);
        i = i + 2*s;
    }
    if(i < n-s+1)
        Merge(SR,TR,i,i+s-1,n);
    else
        for(j=i;j<=n;j++)
        TR[j] = SR[j];
}

快速排序

通过一趟排序将序列记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，最终得到有序序列。

void QuickSort(SqList *L)
{
    QSort(L,1,L->length);
}

void QSort(SqList *L,int low,int high)
{
    int pivot;
    if(low < high)
    {
        //得到中间枢轴值的下标，将序列一份为二
        pivot=Partition(L,low,high);
        //对子序列递归排序
        QSort(L,low,pivot-1);
        QSort(L,pivot+1,high);
    }
}

int Partition(SqList *L,int low,int high)
{
    int pivotkey;
    pivotkey = L->r[low];//选取枢轴
    while(low < high)//当两个下标相遇时，排序完成，退出
    {
        //将大于枢轴的过滤掉
        while(low<high && L->r[high] >= pivotkey)
            high--;
        //交换小的枢轴
        swap(L,low,high);
        //将小于枢轴的过滤掉
        while(low < high && L->r[low] <= pivotkey)
            low++;
         //交换大的枢轴
        swap(L,low,high);
    }
    return low;
}

优化

  • 优化选取枢轴：三数取中，九数取中
  • 优化不必要交换：将枢轴关键字备份，采用替换赋值，而不是交换的方式
  • 当子序列比较小时，切换到直接插入排序
  • 优化递归操作
12 Feb 2020