08_排序

基本概念与分类

假设含有n个记录的序列为 ${r_1,r_2,...,r_n\}$ ，其相应的关键字分别为 ${k_1,k_2,...,k_n\}$ ，需确定1，2，…，n的一种排列 $p_1,p_2,...,p_n$ ，使其相应的关键字满足 $k_{p1}\leq k_{p2}\leq ... \leq k_{pn}$ （非递减或递增）关系，即使得序列成为一个按关键字有序的序列 ${r_{p1},r_{p2},...,r_{pn}\}$ ，这样的操作称为排序。

排序的稳定性

假设 $r_i=r_j(1 \leq i \leq n,i \leq j \leq n,i \neq j)$ ，且在排序前的序列中 $r_i$ 领先与 $r_j$ 。如果排序后 $r_i$ 仍然领先与 $r_j$ ，则称所用的排序方法是稳定的；反之则是不稳定的。

内排序与外排序

内排序是在排序整个过程中，待排序的所有记录全部被就置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。

排序用到的结构与函数

#define MAXSIZE 10    /* 用于要排序数组个数最大值，可以根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1]; /* 存储要排序的数组，r[0]用作哨兵或临时变量 */
    int length;       /* 用于记录顺表的长度 */
}SqList;

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList * L,int i,int j) 
{
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

冒泡排序

冒泡排序（Bubble Sort）一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

/* 对顺序表L作交换排序（冒泡排序初级版） */
void BubbleSort0(SqList *L)
{
    int i,j;
    for(i=1;i<L->length;i++)
    {
        for(j=i+1;j<L->length;j++)
        {
            if(L->r[i]>L->r[j])
            {
                swap(L,i,j);
            }
        }
    }
}

/* 对顺序表L作交换排序（冒泡排序改进版） */
void BubbleSort(SqList *L)
{
    int i,j;
    for(i=1;i<L->length;i++)
    {
        for(j=L->length-1;j>=i;j--) /* 注意j是从后向前循环 */
        {
            if(L->r[j]>L->r[j+1])   /* 若前者大于后者（注意这里与上一算法的差异） */
            {
                swap(L,j,j+1);
            }
        }
    }
}

/* 对顺序表L作交换排序（冒泡排序优化版） */
void BubbleSort2(SqList *L)
{
    int i,j;
    bool flag = true;				/* flag用来作为标记 */
    for(i=1;i<L->length && flag ;i++) /* flag为false，则退出循环 */
    {
        flag = false;				/* 初始化false */
        for(j=L->length-1;j>=i;j--) 
        {
            if(L->r[j]>L->r[j+1])   
            {
                swap(L,j,j+1);
                flag = true; /* 如果有数据交换，则flag为true */
            }
        }
    }
}

冒泡排序算法的时间复杂度： $KaTeX parse error: Expected group after '_' at position 5: \sum_̲\limits{i=2}^{n…$ ，总的时间复杂度为 $O(n^2)$

简单选择排序

简单选择排序法（Simple Selection Sort）就是通过 $n - i$ 次关键字间的比较，从 $n - i + 1$ 记录中选出关键字最小的记录，并和第 $i(1\leq i \leq n)$ 个记录交换。

/* 对顺序表L作简单选择排序 */
void SelectSort(SqList * L) {
    int i,j,min;
    for(i=1;i<L->length;i++){
    	min = i;     				   /* 将当前下标定义为最小值下标 */
        for(j = i+1;j<=L->length;j++){ /* 循环之后的数据 */
            if(L->r[min]>L->r[j])      /* 如果有小于当前最小值的关键字 */
                min = j;   			   /* 将此关键字的下标赋值给min */
        }
        if(i != min)				   /* 若min不等于i，说明找到最小值，交换 */
            swap(L,i,min)			   /* 交换L->r[i]与L->r[min]的值 */
    }
}

简单选择排序算法的时间复杂度： $KaTeX parse error: Expected group after '_' at position 5: \sum_̲\limits{i=1}^{n…$ ，总的时间复杂度为 $O(n^2)$ 。

尽管与冒泡排序同为 $O(n^2)$ ，但简单选择排序的性能上还是略优于冒泡排序。

直接插入排序

直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

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

最好情况（有序表本身有序）下的算法复杂度： $n-1(\sum_{i=2}^n1)$ ，时间复杂度为O(n)

最坏情况（有序表是逆序）下的算法复杂度：比较 $KaTeX parse error: Expected group after '_' at position 5: \sum_̲\limits{(i=2)}^…$ 次，记录移动 $KaTeX parse error: Expected group after '_' at position 5: \sum_̲\limits{i=2}^{n…$ 次

如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为 $\frac{n^2}4$ 。直接插入排序法的时间复杂度为 $O(n^2)$ ，直接插入排序法比冒炮和简单选择排序的性能要好一些。

希尔排序算法

将原本有大量记录数的记录进行分组，分割成若干个子序列。
在这些子序列内进行插入排序，当整个序列基本有序时，再对全体记录进行一次直接插入排序

所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。

/* 对顺序表L作希尔排序 */
void ShellSort(SqList * L)
{
    int i,j;
    int increment = L->length;
    do
    {
        increment = increment/3 +1;  /*增量序列*/
        for(i = increment +1;i<=L->length;i++)
        {
            if(L->r[i] < L->r[i-increment])
            {
                /* 需将L->r[i] 插入有序增量子表 */
                L->r[0] = L->r[i]; /* 暂存在L->r[0] */
                for(j=i-increment;j>0 && L->r[0]< L->r[j];j-=increment)
                    L->r[j+increment] = L->r[j]; /* 记录后移，查找插入位置 */
                L->r[j+increment] = L->r[0]; /* 插入 */
            }
        }        
    }
    while(increment > 1);
}