ericpuwang

排序

假设 $K_i=K_j (1 \leq i \leq n，1 \leq j \leq n，i \neq j)$ ，且在排序前的序列中 $R_i$ 领先于 $R_j$ (即i<j)。若在排序后的序列中 $R_i$ 仍领先于 $R_j$ ，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中 $R_j$ 领先于 $R_i$ ，则称所用的排序方法是不稳定的

#define MAXSIZE 20
typedef int KeyType
typedef struct {} InfoType
typedef struct {
    KeyType key;  // 关键字项
    InfoType otherinfo; // 其他数据项
}RedType;
typedef struct {
    RedType r[MAXSIZE+1]; // r[0]闲置或用做哨兵单元
    int length;  // 顺序表长度
}SqList; // 顺序表类型

插入排序

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止

直接插入排序

将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(1)$

void InsertSort(SqList *L)
{
    for (int i = 2; i <= L.length; i++)
    {
        if (L.r[i].key < L.r[i-1].key)
        {
            L.r[0] = L.r[i]; // 将待插入的记录暂存到监视哨中
            L.r[i] = L.r[i-1]; // r[i-1]后移
            // 从后向前寻找插入位置
            for (int 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]; // 将r[0]即r[i],插入到正确位置
        }
    }
}

折半插入排序

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(1)$

void BInsertSort(SqList *L)
{
    for (int i=2;i<=L.length;i++)
    {
        L.r[0] = L.r[i];
        int low=1; high=i-1;
        // 折半查找
        while (low <= high)
        {
            int m = (low + high) / 2;
            if (L.r[0].key < L.r[m].key)
            {
                high = m -1;
            } else {
                low = m + 1;
            }
        }
        // 记录后移
        for (int j=i-1;j>=high+1;j--)
        {
            L.r[j+1] = L.r[j];
        }
        L.r[high+1] = L.r[0];
    }
}

希尔排序（缩小增量排序）

• 时间复杂度: 当增量序列为 $dt[k]=2^{t−k+1}−1$ 时，希尔排序的时间复杂度为 $O(n^{3/2})$ ，其中t为排序趟数, $1 \leq k \leq t \leq \lfloor log_2{(n+1)} \rfloor$ 。还有人在大量的实验基础上推出：当n在某个特定范围内，希尔排序所需的比较和移动次数约为 $n^{1.3}$ ，当n→∞时，可减少到 $n(log_2n)^2$ 。
• 空间复杂度: $O(1)$

void ShellInsert(SqList *L, int dk)
{
    for (int i=dk+1; i <=L.length; i++)
    {
        // 将L.r[i]插入有序增量列表
        if (L.r[i].key < L.r[i-dk].key)
        {
            int j=0;
            L.r[0] = L.r[i];
            for (j=i-dk; j>0&&L.r[0].key<L.r[j].key; j-=dk)
            {
                L.r[j+dk] = L.r[j];
            }
            L.r[j+dk] = L.r[0];
        }
    }
}

void ShellSort(SqList *L, int dt[], int t)
{
    // 按增量序列dt[0..t-1]对顺序表L作t趟希尔排序
    for (int k=0; k<t; k++)
    {
        ShellInsert(L, dt[k]);
    }
}

交换排序

冒泡排序

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(1)$

void BubbleSort(SqList *L)
{
    int m = L.length-1;
    // 用于标记某一趟排序是否发生交换
    int flag = 1;
    while (m>0&&flag==1)
    {
        flag = 0;
        for (int j=1; j<=m; j++)
        {
            if (L.r[j].key > L.r[j+1].key)
            {
                flag = 1;
                RedType t = L.r[j];
                L.r[j] = L.r[j+1];
                L.r[j+1] = t;
            }
            m--;
        }
    }
}

快速排序

快速排序是由冒泡排序改进而得到的。在冒泡排序过程中，只有相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序，如果通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度

• 时间复杂度 $O(nlog_2n)$
• 空间复杂度 $O(log_2n) \to O(n)$

int Partition(SqList *L, int low, int high)
{
    // 对子表[low...high]排序
    L.r[0] = L.r[low];
    KeyType 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[high].key <= pivotkey) ++low;
        L.r[high] = L.r[low];
    }
    L.r[low] = L.r[0];
    return low;
}

void QSort(SqList *L, int low, ing high)
{
    if (low < high)
    {
        KeyType pivotkey = Partition(L, low, high);
        Qsort(L, low, pivotkey-1);
        Qsort(L, pivotkey, high);
    }
}

void QuickSort(SqList *L)
{
    QSort(L, 1, L.length);
}

选择排序

每一趟从待排序的记录中选择关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止

简单选择排序

• 时间复杂度 $O(n^2)$
• 空间复杂度 $O(1)$

void SelectSort(SqList *L)
{
    for (int i=1; i<L.length; i++)
    {
        int k = i;
        for(int j=i+1; j<=L.length; j++)
        {
            if (L.r[j].key < L.r[k].key) k = j;
        }
        if (k != i)
        {
            int t = L.r[i];
            L.r[i] = L.r[k];
            L.r[k] = L.r[t];
        }
    }
}

堆排序

// 假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆
void HeapAdjust(SqList *L, int s, int m)
{
    RedType rc = L.r[s];
    // 沿key较大的孩子节点向下筛选
    for (int j=2*s; j<=m; j++)
    {
        if (j<m&&L.r[j].key < L.r[j+1].key) ++j;
        if (rc.key >= L.r[j].key) break;
        L.r[s] = L.r[j];
        s = j;
    }
    L.r[s] = rc;
}

void CreateHeap(SqList *L)
{
    int n = L.length;
    for (int i=n/2; i>0; i--)
    {
        HeadAdjust(L, i, n);
    }
}

void HeapSort(SqList *L)
{
    CreateHeap(L);
    // 将堆顶记录与未经排序子序列L.r[1..i]中的最后一个记录互换
    for (int i=L.length; i>1; i--)
    {
        RedType x = L.r[1];
        L.r[1] = L.r[i];
        L.r[i] = x;
    }
    HeapAdjust(L, 1, i-1);
}