排序

排序

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

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

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

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

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

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

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

评价排序算法的标准：执行时间和所需的辅助空间，其次是算法的稳定性。时间是由比较和移动的次数之和确定的，两个记录的一次交换一般需要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);
}

总结：

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