排序

排序

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

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

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

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

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

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

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

评价排序算法的标准：执行时间和所需的辅助空间，其次是算法的稳定性。时间是由比较和移动的次数之和确定的，两个记录的一次交换一般需要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. 不稳定的排序方法：快速排序、堆排序、希尔排序（时间性能较好）。