一、定义

排序：假设含有n个记录的序列为(r1,r2,.....,rn)， 其相应的关键字分别为{k1,k2,......,kn}，需确定 1,2,......,n 的一种排序p1,p2,......pn，使其相应的关键字满⾜kp1 <= kp2 <= ...... <= kpn ⾮递减(或 非递增)关系. 即使得到序列成为一个按关键字有序的序列(rp1,rp2,...,rpn).这样得出操作称为排序。

• 内排序:是在排序整个过程中,待排序的所有记录全部被放置在内存中;
• 外排序:由于排序的记录个数太多,不能同时放置在内存,整个排序过程需要在内外存之间多次交换数据才能进⾏。
  假设ki=kj(1<=i<=n, 1<=j<=n, i != j)，且在排序前有序列中ri领先于rj(即i<j)。如果排序后ri仍领先rj，则称所用的方法是稳定的。反之，若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。

二、冒泡排序

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

代码实现

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

//5.冒泡排序-对顺序表L作冒泡排序(正宗冒泡排序算法)
void BubbleSort(SqList *L){
    for(int i = 1; i<L->length; i++){
        for(int j = L->length-1; j>= i; j--){
            if(L->r[j]>L->r[j+1]){
                //利用了之前比较的结果
                swap(L, j, j+1);
            }
        }
    }
}

//6.冒泡排序-对顺序表L冒泡排序进行优化
void BubbleSort2(SqList *L){
    Status flag = TRUE;
    //定义一个标志，当flag为false的时候，表示已经是有序的
    //已经出现过一次j从L->Length-1 到 i的过程,都没有交换的状态
    //当序列为{2,1,3,4,5,6,7,8,9}时，只需要经过两次排序就完成了整个排序过程
    for(int i = 1;i<L->length && flag; i++){
        flag = FALSE;
        for(int j = L->length-1; j>=i; j--){
            if(L->r[j]>L->r[j+1]){
                swap(L, j, j+1);
                flag = TRUE;
            }
        }
    }
}

算法复杂度

当最好的情况，也就是说排序表本身就是有序的时候，我们比较的次数，根据最后优化的代码，可以推断出是n-1次比较，没有数据交换，复杂度为O(n)。
当最坏的情况，即排序表是逆序的时候，一共比较了n*(n-1)/2次。因此，总的复杂度为O(n²)。

三、选择排序

选择排序的基本思想：每一躺在n-i+1(i=1,2,..,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录。

代码实现

//7.选择排序--对顺序表L进行简单选择排序
void SelectSort(SqList *L){
    int min;
    for(int i = 1; i<L->length; i++){
        min = i;
        for(int j = i+1; j<=L->length; j++){
            if(L->r[min]>L->r[j]){
                min = j;
            }
        }
        if(min != i){
            swap(L, i, min);
        }
    }
}

算法复杂度

从简单选择排序的过程看，它最大的特点是交换移动数据的次数相当少，这样也就节约了相应的时间，分析它的复杂度发现，无论最好最差的情况，其比较的次数一样多，需要比较n*(n-1)/2次，因此，总的算法复杂度为O(n)。

四、直接插入排序

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

代码实现

//8.直接插入排序算法--对顺序表L进行直接插入排序
void InsertSort(SqList *L){
    int i,j;
    for(i = 2;i<=L->length; i++){
        if(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];
        }
        print(*L);
        printf("\n");
    }
}

算法复杂度

从空间上看，它只需要一个记录的辅助空间，因此关键看它的时间复杂度。
当最好的情况，也就是排序表本身就是有序的，因为有序，所以不需要移动记录，因此时间复杂度为O(n)。
当最坏的情况，即待排序表为逆序的时候，需要比较(n+2)(n-1)/2次，而移动记录的次数也高达(n+4)(n-1)/2次。
因此我们得出，直接插入排序的算法复杂度为O(n²)。

五、希尔排序

希尔排序思想：希尔排序是把记录按下标的一定增量分组，对每组使用插入排序算法排序，随着增量逐渐减少，每组包含的关键字越来越多，当增量减少至1时，整个序列恰被分成一组，算法便终止。

代码实现

//9.希尔排序-对顺序表L希尔排序
void shellSort(SqList *L){
    int i,j;
    //定义一个增量，可根据这个增量将序列分成n段
    int increment = L->length;
    //0,9,1,5,8,3,7,4,6,2
    while(increment > 1){
        increment = increment/3+1;
        //i的待插入序列数据 [increment+1 , length]
        for(i = increment+1; i<=L->length; i++){
            //如果r[i] 小于它的序列组元素则进行插入排序,例如3和9.3比9小,所以需要将3与9的位置交换
            if(L->r[i]<L->r[i-increment]){
                L->r[0] = L->r[i];
                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];
            }
        }
    }
}

算法复杂度

通过代码分析，希尔排序的关键并不是随便分组后各自排序，而是相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序序列提高。其时间复杂度为O(n^3/2)，比直接排序O(n²)要好。
需要注意的是：增量序列的最后一个增量值必须等于1才行。

六、堆排序

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

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

如果按照层序遍历的方式给结点从1开始编号，则结点之间的关系满足如果关系：

image.png

左图为大顶堆，右图为小顶堆
堆排序的基本思想：将待排序的序列构成一个大顶堆，此时整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组末尾的元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复，就能得到一个有序的序列。

代码实现

//大顶堆调整函数;
/*
 条件: 在L.r[s...m] 记录中除了下标s对应的关键字L.r[s]不符合大顶堆定义,其他均满足;
 结果: 调整L.r[s]的关键字,使得L->r[s...m]这个范围内符合大顶堆定义.
 */
void HeapAjust(SqList *L,int s,int m){
    int temp = L->r[s];
    int j;
    
    //s为非叶子结点，s结点的左孩子为2s，s结点的右孩子为2s+1
    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;
    }
    L->r[s] = temp;
    print(*L);
}

//10.堆排序--对顺序表进行堆排序
void HeapSort(SqList *L){
    //完全二叉树的性质，非叶子结点的个数为L->length/2
    //大顶堆只需要父结点的值大于子结点的值，子结点之间没有大小之分，所以在进行大顶堆的构造时，只需要调整非叶子结点
    for(int i = L->length/2; i>0; i--){
        HeapAjust(L, i, L->length);
    }
    
    for(int i = L->length; i>1; i--){
        //此时，堆顶元素为最大值，交换堆顶元素和末尾元素
        swap(L, 1, i);
        print(*L);
        //由于交换了元素，因为当前堆又不是大顶堆，需要重新进行大顶堆调整
        HeapAjust(L, 1, i-1);
    }
}

算法复杂度

从代码中可以看出，它的运行时间主要是消耗在初始构建堆和重建堆的反复筛选上。
在构建堆的过程中，因为我们是完全二叉树从最下层最右边的非终端结点开始构建，将它与其孩子进行比较和若有必要的互换，对于每个非终端结点来说，其实最多只需要两次比较和互换。因此整个构建的算法复杂度为O(n)。
在正式排序的时候，第i次取堆顶记录重建堆需要用O(logi)的时间，因此重建堆的算法复杂度为O(logn)。
所以总的算法复杂度为O(nlogn)。