C/C++『排序算法』

---

前言：定义排序的结构和交换函数

在代码举例的过程中会用到顺序表结构，同时排序过程难免涉及数据交换，故此设计以下结构体和函数
顺序表结构如下所示：

// 定义排序的所用到的结构
#define MAXSIZE 10
typedef struct
{
    int r[MAXSIZE + 1]; //通常将r[0]作为哨兵或者临时变量
    int Length;	//顺序表长度
} SqList;

交换函数如下所示：

// 定义在排序中常常用到的交换数据的函数
void swap(SqList *L, int i, int j)
{
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

此外，为了使用统一的函数接口SqList，有些情况下的排序算法采取多层封装

---

1 冒泡排序

1.1 交换排序

// 1.冒泡排序初级版，仅对顺序表L作交换排序，输入参数为一个顺序表
void Bubble_Sort0(SqList *L)
{
    int i, j;
    for (i = 1; i < L->Length; i++)
    {
        for (j = 0; j < L->Length; j++)
        {
            if (L->r[i] > L->r[j])
            {
                swap(L, i, j); //交换L->r[i] 和 L->r[j] 的值
            }
        }
    }
}

1.2 冒泡排序

// 2.冒泡排序，输入参数为一个顺序表
void Bubble_Sort(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->r[j] 和 L->r[j+1] 的值
            }
        }
    }
}

1.3 冒泡排序优化

// 3.冒泡排序优化，输入参数为一个顺序表
// typedef bool Status;
// #define TRUE 1
// #define FALSE 0
void Bubble_Sort_Improve(SqList *L)
{
    int i, j;
    bool flag = true;                       // flag用来做标记
    for (i = 1; i < L->Length && flag; i++) //若flag为false则退出循环
    {
        flag = false;                        // flag初始化为false
        for (j = L->Length - 1; j >= i; j--) // j从后往前循环
        {
            if (L->r[j] > L->r[j + 1]) //若前者大于后者
            {
                swap(L, j, j + 1); //交换L->r[j] 和 L->r[j+1] 的值
                flag = true;       //如果有数据交换，则flag为true
            }
        }
    }
}

---

2 简单选择排序

//执行简单选择排序
void Select_Sort(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, j, j + 1); //交换L->r[j] 和 L->r[min] 的值
        }
    }
}

---

3 直接插入排序

//执行插入排序
void Insert_Sort(SqList *L)
{
    int i, j;
    for (i = 2; i < L->Length; i++)
    {
        if (L->r[i] < L->r[i - 1])
        {
            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] = L->r[0]; //插入到正确位置
        }
    }
}

---

4 希尔排序

//执行希尔排序
void Shell_Sort(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] 插入有序增量表w*/
                L->r[0] = L->r[i]; //暂存在L->r[0]
                for (j = i - increment; j > 0 && L->r[0] < L->r[j]; j++)
                {
                    L->r[j + increment] = L->r[j]; //记录后移，查找插入位置
                }
                L->r[j + increment] = L->r[0]; //插入
            }
        }
    } while (increment > 1);
}

---

5 堆排序

//首先本函数调整L->r[s]的关键字，使得L->r[s......m]成为一个大顶堆
void HeapAdjust(SqList *L, int s, int m)
{
    int temp;
    temp = L->r[s];
    for (int j = 2 * s; j <= m; j *= 2) //沿关键字较大的的孩子节点向下筛选
    {
        if (j < m && L->r[j] < L->r[j + 1])
        {
            ++j; // j为关键字中较大记录的下标
        }
        if (temp >= L->r[j])
        {
            break; // rc应当插入在位置s上
        }
        L->r[s] = L->r[j];
        s = j;
    }
    L->r[s] = temp; //插入
}
//然后执行堆排序
void Heap_Sort(SqList *L)
{
    int i;
    for (i = L->Length / 2; i > 0; i--)
    {
        HeapAdjust(L, i, L->Length); //将L中的r构建成一个大顶堆
    }
    for (i = L->Length; i > 1; i--)
    {
        swap(L, 1, i);           //将堆顶记录与当前未经排序的子序列的最后一个记录交换
        HeapAdjust(L, 1, i - 1); //将L->r[1.....i-1]重新调整为大顶堆
    }
}

---

6 归并排序

6.1 递归版归并排序

//首先归并两个序列
//将有序的两个序列SRC[i......m]和SRC[m+1......n]归并为有序的DES[i......n]
void Merge(int SRC[], int DES[], int i, int m, int n)
{
    int j, k, l;
    for (j = m + 1, k = i; j <= m && j <= n; k++) //将SRC中记录由小到大归并到DES中
    {
        if (SRC[i] < SRC[j])
        {
            DES[k] = SRC[i++];
        }
        else
        {
            DES[k] = SRC[j++];
        }
    }
    if (i <= m)
    {
        for (l = 0; l <= m - i; l++)
        {
            DES[k + 1] = SRC[i + 1]; //将剩余的SRC[i......m]复制到DES中
        }
    }
    if (j <= n)
    {
        for (l = 0; l <= n - j; l++)
        {
            DES[k + 1] = SRC[j + 1]; //将剩余的SRC[j......n]复制到DES中
        }
    }
}
//然后外封装一个函数，将SRC[s......t]归并排序为DES[s......t]
void MSort(int SRC[], int DES[], int s, int t)
{
    int m;
    int TEMP[MAXSIZE + 1];
    if (s == t)
    {
        DES[s] = SRC[s];
    }
    else
    {
        m = (s + t) / 2;            //将SRC[s......t]平分为两个序列SRC[s......m]和SRC[m+1......t]
        MSort(SRC, TEMP, s, m);     //递归将SRC[s......m]归并为有序的TEMP[s......m]
        MSort(SRC, TEMP, m + 1, t); //递归将SRC[m+1......t]归并为有序的TEMP[m+1......t]
        Merge(TEMP, DES, s, m, t);  //将TEMP[s......m]和TEMP[m+1......t]归并到DES[s......t]
    }
}
//最后递归归并排序
void Merge_Sort_Recursion(SqList *L)
{
    MSort(L->r, L->r, 1, L->Length);
}

6.2 迭代版归并排序

//首先
void MergePass(int SRC[], int DES[], int s, int n)
{
    int i = 1;
    int j;
    while (i <= n - 2 * s + 1)
    {
        Merge(SRC, DES, i, i + s - 1, i + 2 * s - 1); //两两归并
        i = i + 2 * s;
    }
    if (i < n - s + 1)
    {
        Merge(SRC, DES, i, i + s - 1, n); //归并最后两个序列
    }
    else
    {
        for (j = i; j <= n; j++) //若剩下最后单个序列
        {
            DES[j] = SRC[j];
        }
    }
}
//然后迭代归并排序
void Merge_Sort_Iterate(SqList *L)
{
    int *TR = (int *)malloc(L->Length * sizeof(int)); //申请额外空间
    int k = 1;
    while (k < L->Length)
    {
        MergePass(L->r, TR, k, L->Length);
        k = 2 * k; //子序列长度加倍
        MergePass(TR, L->r, k, L->Length);
        k = 2 * k; //子序列长度加倍
    }
}

---

7 快速排序

//首先，交换顺序表中的子表记录，并使枢轴记录到位，并返回相应位置
int Partition(SqList *L, int low, int high)
{
    int pivotkey;
    pivotkey = L->r[low]; //将表的第一个记录作枢轴记录
    while (low < high)    //从表的两边交替向中间扫描
    {
        while (low < high && L->r[high] >= pivotkey)
        {
            high--;
        }
        swap(L, low, high); //将比枢轴记录小的记录交换到低端
        while (low < high && L->r[low] <= pivotkey)
        {
            low++;
        }
        swap(L, low, high); //将比枢轴记录大的记录交换到高端
    }
    return low; //返回枢轴所在位置
}
//然后，递归排序
void QSort(SqList *L, int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = Partition(L, low, high); //将L->r[low ...... high]一分为二并算出枢轴值pivot
        QSort(L, low, pivot - 1);        //对低子表递归排序
        QSort(L, pivot + 1, high);       //对高子表递归排序
    }
}
//最后，执行快速排序
void Quick_Sort(SqList *L)
{
    QSort(L, 1, L->Length);
}

快速排序算法的优化：

1. 优化选取枢轴—-三数取中（始终保持左端较小）：在Partition函数第3行和第4行插入如下代码

int mid = low + (high - low)/2;
if (L->r[low]>L->r[high])
    swap(L,low,high);
if (L->r[mid]>L->r[high])
    swap(L,mid,high);
if (L->r[mid]>L->r[low])
    swap(L,low,mid);

2. 优化不必要交换—-在Partition函数中

   1. 首先，将枢轴关键字pivotkey备份到L->r[0];
   2. 其次，采用替换而不是交换的方式进行操作;
   3. 再者，将枢轴数值替换回L->r[low];

3. 优化小数组时的排序方案
   定义一个插入排序的最大数值【#define MAX_LENGTH_INSERT_SORT 7】
   在QSort函数中high-low的值 如果大于这个定义值就用快速排序，如果小于等于这个定义值就用插入排序

4. 优化递归操作

   将QSort函数的if语句改成while语句，并将第二个QSort改为low=pivot+1的尾递归