数据结构与算法-常见的排序算法

排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素的任一序列，重新排列成一个按关键字有序的序列。
由于待排序的记录数量不同，使得排序过程中设计的存储器不同，可将排序方法分为两大类：

• 内部排序，指的是待排序记录存放在计算机存储器中进行的排序过程；
• 外部排序，指的是待排序记录的数据量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

冒泡排序

冒泡排序(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; j > i; j--) {
            if (L->r[j - 1] > L->r[j]) {
                swap(L, j - 1, j);
            }
        }
    }
}

// 冒泡排序-对顺序表L冒泡排序进行优化
void BubbleSort2(SqList *L) {
    Status flag = TRUE;
    int i, j;
    for (i = 1; i <= L->length && flag; i++) {
        flag = FALSE;
        for (j = L->length; j > i; j--) {
            if (L->r[j - 1] > L->r[j]) {
                swap(L, j - 1, j);
                flag = TRUE;
            }
        }
    }
}

简单选择排序算法(Simple Selection Sort)

简单选择排序算法 就是通过n - i次关键词比较,从n - i + 1个记录中找出关键字最小的记录,并和第i(1 <= i <= 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;
            }
        }
        if (i != min) {
            swap(L, i, min);
        }
    }
}

直接插入排序

直接插入排序（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[0] = L->r[i];
            for (j = i - 1; L->r[0] < L->r[j]; j--) {
                L->r[j + 1] = L->r[j];
            }
            L->r[j + 1] = L->r[0];
        }
    }
}

希尔排序（Shell Sort）

希尔排序又称“最小增量排序”，它也是一种属插入排序类的方法，但在实际效率上较前述集中排序方法有较大的改进。
希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将像个某个“增量”的记录组成一个子序列。

// 希尔排序-对顺序表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[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];
            }
        }
        
    } while (increment > 1);
}

堆排序（Heap Sort）

堆排序 就是利用堆进行排序的算法。它的基本思想：

1. 将待排序的序列构成⼀个⼤顶堆，此时整个序列的最大值就堆顶的根结点，将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值);
2. 然后将剩余的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 j, temp;
    temp = L->r[s];
    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;
}


void HeapSort(SqList *L) {
    int i;
    for (i = L->length / 2; i > 0; i--) {
        HeapAjust(L, i, L->length);
    }
    for (i = L->length; i > 1; i--){
        swap(L, 1, i);
        HeapAjust(L, 1, i - 1);
    }
}