内容纲要

排序

排序:是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程。关键字可以是记录的主关键字,也可以是次关键字或若干数据项的组合。

内部排序:在排序过程中,若整个数据表都是存放在内存中处理,排序时不涉及数据的内、外存交换。

外排序:排序过程中要进行数据的内、外存交换。

内部排序的分类:是否基于关键字的比较,分为基于比较的排序算法和不基于比较的排序。(插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法。基数排序是不基于比较的排序算法。)

算法的稳定性:如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,称这种排序方法是稳定的;反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。

正序:待排序记录的关键字顺序正好和要排序顺序相同。

反序:若待排序记录的关键字顺序正好和要排序顺序相反。

评价排序算法的标准:执行时间和所需的辅助空间,其次是算法的稳定性。时间是由比较和移动的次数之和确定的,两个记录的一次交换一般需要3次移动。

插入排序

插入排序:每一趟将一个待排序的记录,按其关键字值的大小插入到已经排序的部分文件中适当位置上,直到全部插入完成。

直接插入排序

直接插入排序:依次将每个记录插入到一个有序的序列中去。初始时,有序区只有一个元素R[0],i=1~n-1,共经过n-1趟排序。

代码实现:

// ------ 待排记录的数据类型--------
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
typedef struct { // 记录类型
    KeyType key; // 关键字项
    InfoType otherinfo; // 其它数据项,具体类型在主程中定义
} RedType;
typedef struct { // 顺序表类型
    RedType r[MAXSIZE + 1]; // r[0]闲置或用作哨兵单元
    int length; // 顺序表长度
} SqList;

void InsertSort(RedType R[], int n)
{
    int i, j;
    RedType tmp;
    for (i=1;i<n;i++){ //从第二个元素即R[1]开始的
        if (R[i-1].key>R[i].key){
            tmp=R[i]; //取出无序区的第一个元素R[i]
            j=i-1; //在R[0..i-1]中找R[i]的插入位置
            do{
                R[j+1]=R[j]; //将关键字大于tmp.key的元素后移
                j--; //继续向前比较
            } while (j>=0 && R[j].key>tmp.key);
            R[j+1]=tmp; //在j+1处插入R[i]
        }
    }
}

//设置哨兵
void InsertSort(SqList &L)
{
    // 对顺序表L作直接插入排序。算法10.1
    int i, j;
    for(i = 2; i <= L.length; ++i)
        // <,需将L.r[i]插入有序子表
        if (LT(L.r[i].key, L.r[i - 1].key)) {
            L.r[0] = L.r[i]; // 复制为哨兵
            for(j = i - 1; LT(L.r[0].key, L.r[j].key); --j)
                L.r[j + 1] = L.r[j]; // 记录后移
            L.r[j + 1] = L.r[0]; // 插入到正确位置
        }
}

折半插入排序

折半插入排序:有序区的有序性。可以采用折半查找方法先在R[0..i-1]中找到插入位置,再通过移动记录进行插入。这样的插入排序称为折半插入排序或二分插入排序。折半插入排序的元素移动次数与直接插入排序相同,不同的仅是变逐个移动为集中移动。

代码实现:

void binSort(RedType a[],int n)//按递增序进行二分法插入排序
{
    int i,j,left,mid,right;
    for (i=1;i<n;i++){
        left=0;right=i-1; 循环寻找位置
        while (left<=right){
            mid=(left+right)/2;
            if (a[i].key<a[mid].key)
                right=mid-1;
            else
                left=mid+1;
        }
        for(j=i-1;j>=left;j--)
            a[j+1]=a[j];//将排序大于ki 的记录后移插入
        if(left!=i)
            a[left]=a[i];
    }
}

希尔排序

希尔排序:(缩小增量排序)先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序。然后取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

代码实现:

//取d1= n/2,di+1=⌊di/2⌋时
void ShellSort(RedType R[],int n)
{
    int i,j,d;
    RedType tmp;
    d=n/2; //增量置初值
    while (d>0){
        for (i=d;i<n;i++){
            tmp=R[i]; //对所有相隔d位置的记录组采用直接插入排序
            j=i-d;
            while (j>=0 && tmp.key<R[j].key){
                R[j+d]=R[j];
                j=j-d;
            }
            R[j+d]=tmp;
        }
        d=d/2; //减小增量
    }
}
void ShellInsert(SqList &L, int dk)
{
    // 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比,
    // 作了以下修改:
    // 1.前后记录位置的增量是dk,而不是1;
    // 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
    int i, j;
    for(i = dk + 1; i <= L.length; ++i)
        if (LT(L.r[i].key, L.r[i - dk].key) ) {
            // 需将L.r[i]插入有序增量子表
            L.r[0] = L.r[i]; // 暂存在L.r[0]
            for(j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
                L.r[j + dk] = L.r[j]; // 记录后移,查找插入位置
            L.r[j + dk] = L.r[0]; // 插入
        }
}

交换排序

交换排序:交换排序是一类基于“交换”的排序,系统地交换反序的记录的偶对,直到不再有这样的偶对为止。交换排序的基本思路:两两比较待排序记录的关键字,并交换不满足次序要求的那些偶对,直到全部满足为止。

冒泡排序

冒泡排序:设待排序记录序列中的记录个数为n。最多作n-1 趟冒泡,i = 1, 2, 。。, n-1。在第i 趟中从后向前,j = n-1, n-2, 。。, i,顺次两两比较r[j-1].key和r[j].key。如果发生逆序,即r[j-1].key>r[j].key ,则交换r[j-1].key和r[j].key。

代码实现:

void BubbleSort(RedType R[],int n)
{
    int i,j,exchange;
    RedType tmp;
    for(i=0;i<n-1;i++){
        exchange=0; //本趟排序前置exchange为0
        for (j=n-1;j>i;j--) //比较,找出最小关键字的记录
            if(R[j].key<R[j-1].key){
                tmp=R[j]; //R[j]与R[j-1]进行交换,
                R[j]=R[j-1]; //将最小关键字记录前移
                R[j-1]=tmp;
                exchange=1; //本趟排序发生交换置exchange为1
            }
        if (exchange==0) //本趟未发生交换时结束算法
            return;
    }
}

快速排序

快速排序:找一个记录(例如取第一个记录) ,以它的关键字作为“枢轴”(基准);凡其关键字小于枢轴的记录均移动至该记录之前;凡其关键字大于枢轴的记录均移动至该记录之后。即对无序的记录序列进行“一次划分”,之后分别对分割所得两个子序列“递归”进行快速排序。

代码实现:

int Partition(SqList &L, int low, int high)
{
    // 交换顺序表L中子表r[low..high]的记录,枢轴记录到位,并返回其
    // 所在位置,此时在它之前(后)的记录均不大(小)于它。算法10.6(b)
    KeyType pivotkey;
    L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
    pivotkey = L.r[low].key; // 枢轴记录关键字
    while(low < high) {
        // 从表的两端交替地向中间扫描
        while(low < high && L.r[high].key >= pivotkey)
            --high;
        L.r[low] = L.r[high]; // 将比枢轴记录小的记录移到低端
        while(low < high && L.r[low].key <= pivotkey)
            ++low;
        L.r[high] = L.r[low]; // 将比枢轴记录大的记录移到高端
    }
    L.r[low] = L.r[0]; // 枢轴记录到位
    return low; // 返回枢轴位置
}
void QSort(SqList &L, int low, int high)
{
    // 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7
    int pivotloc;
    if(low < high) { // 长度大于1
        // 将L.r[low..high]一分为二
        pivotloc = Partition(L, low, high);
        // 对低子表递归排序,pivotloc是枢轴位置
        QSort(L, low, pivotloc - 1);
        QSort(L, pivotloc + 1, high); // 对高子表递归排序
    }
}
void QuickSort(SqList &L)
{
    // 对顺序表L作快速排序。算法10.8
    QSort(L, 1, L.length);
}

选择排序

选择排序:每一趟(例如第i 趟, i = 1, …, n-1) 在后面n-i+1 个待排序记录序列中选出关键字值最小的记录,作为有序记录序列的第i 个记录。待到第n-1 趟作完,待排序记录只剩下1 个, 就不用再选了。选择排序的每一趟可把有序区扩大,直到n-1趟后即可把有序区扩大到整个待排序序列。

简单选择排序

简单选择排序:在一组记录r[i]~r[n] 中选择具有最小关键字的记录;若它不是这组记录中的第一个记录,则将它与这组记录中的第一个记录对调;在这组记录中剔除这个具有最小关键字值的记录。在剩下的记录r[i+1]~r[n] 中重复执行前两步,直到剩余记录只有一个为止。

代码实现:

int SelectMinKey(SqList L, int i)
{
    // 返回在L.r[i..L.length]中key最小的记录的序号
    KeyType min;
    int j, k;
    k = i; // 设第i个为最小
    min = L.r[i].key;
    for(j = i + 1; j <= L.length; j++)
        if(L.r[j].key < min) { // 找到更小的
            k = j;
            min = L.r[j].key;
        }
    return k;
}
void SelectSort(SqList &L)
{
    // 对顺序表L作简单选择排序。算法10.9
    int i, j;
    RedType t;
    for(i = 1; i < L.length; ++i) { //选择第i小的记录,并交换到位
        // 在L.r[i..L.length]中选择key最小的记录
        j = SelectMinKey(L, i);
        if(i != j) { //与第i个记录交换
            t = L.r[i];
            L.r[i] = L.r[j];
            L.r[j] = t;
        }
    }
}

树型排序

树型排序:又称锦标赛排序。对n 个记录的关键字进行两两比较,然后再[n/2]个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可用一棵有n 个叶子结点的完全二叉树表示。

堆排序

堆:若将该记录序列视作完全二叉树,则:r2i 是ri 的左孩子;r2i+1 是ri 的右孩子。

堆

堆排序:对树型排序的进一步改进。是利用堆的特性对记录序列进行排序。堆排序采用堆结构选择最大(最小)元素。如果每个结点的关键字均大于等于其所有孩子结点的关键字,称为大根堆。如果每个结点的关键字均小于等于其所有孩子结点的关键字,称为小根堆。

  • 从最后一个分支结点(编号为n/2)开始到根结点(编号为1)通过多次调用筛选算法建立初始堆。
  • 将R[1](无序区中最大记录)与无序区最后一个记录交换,归位无序区最后一个记录,无序区减少一个记录。
  • 再筛选,重复进行,直到无序区只有一个记录。

代码实现:

typedef SqList HeapType; // 堆采用顺序表存储表示
//调整堆
void HeapAdjust(HeapType &H, int s, int m)
{ 
    // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义,本函数
    // RedType rc;调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)。算法10.10
    int j;
    rc = H.r[s];
    for(j = 2 * s; j <= m; j *= 2) {
        // 沿key较大的孩子结点向下筛选
        if(j < m && LT(H.r[j].key, H.r[j + 1].key))
            ++j; // j为key较大的记录的下标
        if(!LT(rc.key, H.r[j].key))
            break; // rc应插入在位置s上
        H.r[s] = H.r[j];
        s = j;
    }
    H.r[s] = rc; // 插入
}

void HeapSort(HeapType &H)
{
    // 对顺序表H进行堆排序。算法10.11
    RedType t;
    int i;
    // 把H.r[1..H.length]建成大顶堆
    for(i = H.length / 2; i > 0; --i)
        HeapAdjust(H, i, H.length);
        // 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
    for(i = H.length; i > 1; --i) {
        t = H.r[1];
        H.r[1] = H.r[i];
        H.r[i] = t;
        HeapAdjust(H, 1, i - 1); // 将H.r[1..i-1]重新调整为大顶堆
    }
}

归并排序

归并排序:通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度。多次将两个或两个以上的有序表合并成一个新的有序表。通常采用的是2-路归并排序。即:将两个位置相邻的记录有序子序列归并为一个记录的有序序列。

代码实现:

void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{
    // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12
    int j, k, l;
    // 将SR中记录由小到大地并入TR
    for(j = m + 1, k = i; i <= m && j <= n; ++k)
        if LQ(SR[i].key, SR[j].key)
            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]; // 将剩余的SR[i..m]复制到TR
    if(j <= n)
        for(l = 0; l <= n - j; l++)
            TR[k + l] = SR[j + l]; // 将剩余的SR[j..n]复制到TR
}
void MSort(RedType SR[], RedType TR1[], int s, int t)
{
    // 将SR[s..t]归并排序为TR1[s..t]。算法10.13
    int m;
    RedType TR2[MAX_SIZE + 1];
    if(s == t)
        TR1[s] = SR[s];
    else {
        m = (s + t) / 2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
    // 递归地将SR[s..m]归并为有序的TR2[s..m]
    MSort(SR, TR2, s, m);
    // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
    MSort(SR, TR2, m + 1, t);
    // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
    Merge(TR2, TR1, s, m, t);
    }
}
void MergeSort(SqList &L)
{
    // 对顺序表L作归并排序。算法10.14
    MSort(L.r, L.r, 1, L.length);
}

基数排序

基数排序:采用“分配”与“收集”的办法,用对多关键字进行排序的思想实现对单关键字进行排序的方法。

两种常用方法:最高位优先MSD (Most Significant Digit first )、最低位优先LSD (Least Significant Digit first)

最高位优先法:

  • 先根据最高位关键字K1排序, 得到若干元素组,元素组中各元素都有相同关键字K1。
  • 再分别对每组中元素根据关键字K2 进行排序,按K2 值的不同, 再分成若干个更小的子组, 每个子组中的元素具有相同的K1和K2值。
  • 依此重复, 直到对关键字Kd完成排序为止。
  • 最后, 把所有子组中的元素依次连接起来,就得到一个有序的元素序列。

最低位优先法

  • 首先依据最低位关键字Kd对所有元素进行一趟排序;再依据次低位关键字Kd-1对上一趟排序的结果再排序,依次重复,直到依据关键字K1最后一趟排序完成,就可以得到一个有序的序列。
  • 这种排序方法对每个关键字进行排序时,不需要再分组,而是整个元素组都参加排序。

链式基数排序:是典型的LSD排序方法, 利用“分配”和“收集”对单关键字进行排序。在这种方法中,把单关键字Ki 看成是一个d 元组。其中的每一个分量也可看成是一个关键字。分量有radix 种取值, 称radix 为基数。基数排序以静态链表作为它们的存储结构。

代码实现:

typedef struct node{
    int key;
    anytype data;
    int *next;
}List_Node;

List_Node *radixsort( List_Node *h,int d,int r)
{
    n=10; m=1;
    for(i=1; i<=d;i++){ //共“分配”、“收集”d 次
        for(j=0;j<=9;j++){ //初始化队列
            f[j]=NULL;t[j]=NULL;
        }
        p=h;
        while(p) {
            k=p->key%n/m // “分离”
            if(f[k]==NULL) f[k]=p; //入队
            else t[k]->next=p;
            t[k]=p;
            p=p->next; //从单链表中获取下一个结点
        }
        m=m*10; n=n*10;
        h=NULL; p=NULL; //“收集”
        for(j=0;j<r;j++)
            if (f[j]) {
                if (!h) { 
                    h=f[j];
                    p =t[j]; 
                }else {
                    p->next=f[j];p=t[j];
                }
            }
        }
    return(h);
}
时间复杂度
最好情况最坏情况平均情况空间复杂度稳定性
直接插入排序O(n)O(n2)O(n2)O(1)稳定
折半插入排序O(n)O(n2)O(n2)O(1)稳定
希尔排序O(n2/3)O(1)不稳定
冒泡排序O(n)O(n2)O(n2)O(1)稳定
快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定
简单选择排序O(n2)O(n2)O(n2)O(1)不稳定
堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定
基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定

总结

  1. 就平均时间性能而言,快速排序最佳。但在最坏情况下不如堆排序和归并排序。(归并排序对n较大时适用)
  2. 当序列中的记录“基本有序”或n 值较小时,直接插入排序是最佳的方法,因此常将它与其他排序方法结合使用,如快速排序、归并排序等。
  3. 基数排序的时间复杂度也可写成O(d*n),因此它最适用于n 值很大而关键字较小的序列。
  4. 稳定的排序方法:基数排序、简单排序。
  5. 不稳定的排序方法:快速排序、堆排序、希尔排序(时间性能较好)。
最后修改日期:2020年7月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。