第九章排序

直接插入排序

结构体定义

#define MAXSIZE 20;
typedef int KeyType;

typedef struct {
    KeyInfo key;
    InfoType otherinfo;
}RedType;

typedef struct {
    RedType r[MAXSIZE + 1];
    int lenght;
}SqList;

一趟直接插入排序的过程为:
1．在R[1…i-1]中查找R[i]的插入位置,
R[1..j].keyR[i].key< R[j+1..i-1].key;
2．将R[j+1…i-1]中的所有记录均后移一个位置;
3．将R[i]插入到R[j+1]的位置上.

直接插入排序的算法实现

Status InsertSort(SqList &L){
    for(i = 2; i < L.length; i++){
        if(L.r[i].key < L.r[i - 1].key){
            L.r[0] = L.r[i];
            for(j = i - 2; L.r[0].key < L.r[j].key; j--){
                L.r[j + 1] = L.r[j];
            }
            L.r[j + 1] = L.r[0];
        }
    }
}

当待排记录的数量n很小时, 直接插入排序是一种很好的排序方法, 但是当n很大时, 则不宜采用此排序方法.

希尔排序

冒泡排序

快速排序

堆排序

堆排序是一种不稳定的排序方法, 适用于记录个数n较大的情况.

归并排序

对比

排序算法比较

:::tip
直接插入排序、冒泡排序, 归并排序是稳定的排序方法.
:::

:::danger
简单选择排序、快速排序、堆排序和希尔排序是不稳定的排序方法.
:::

从平均时间性能而言, 快速排序最佳.其所需时间最省.但快速排序, 最快情况下的时间性能不如堆排序和归并排序.
借助于比较进行的排序算法, 在最坏情况下能达到的最好的时间复杂度为O(nlogn).

第九章 排序