数据结构与算法-数组排序算法

0. 交换两个变量中的值(辅助函数)

最简单的，利用一个临时变量：

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

还有其他办法么？答案是使用异或(XOR或^)。但是为什么呢？

假设a为二进制数01，b为二进制数10，a^b的结果为11并将其存储在变量c中。

11^01=10
11^10=01
// 转换成我们的变量
c^a = b;
c^b = a;

我们发现，将两数异或的结果与其中一数再进行异或，可以得到另一个数。

原理：两数异或的结果保存了两个数上每一个二进制位不同或相同的信息。如果相应的二进制位不同，就标志为1，如果相同，则标志为0。

a和c进行异或，相当于把c中和a相同的部分抵消掉，就可以得到b。

b和c进行异或，相当于把b中和a相同的部分抵消掉，就可以得到a。

void swap(int *a, int *b)
{
    int c = *a ^ *b;
    *a = c ^ *a;
    *b = c ^ *b;
}

但代码上看着还是需要一个临时变量？

简单分析一下，就可以发现，c中信息丰富，可以说保存了a和b的信息，我们可以把a变成c，信息是没有损失的。

void swap(int *a, int *b)
{
    *a = *a ^ *b; // 相当于c，保存了a和b的信息
    *b = *a ^ *b; // 相当于c^b，可以得到a
    *a = *a ^ *b; // 虽然看着是a^b，但现在a=c，b=a，实际是c^a，可以得到b
}

当然，如果你很骚(想装逼)，也可以写得更简洁：

void swap(int *a, int *b)
{
    *a^=*b^=*a^=*b;
}

1. 冒泡排序

核心思想：

• 把最后的位置留给最大元素。下次循环的时候就可以少遍历一个数。

• 通过不断交换，把较大的数往后挪。

过程：

1. 从头开始遍历，结束遍历的时候，末尾的就是最大的元素。
2. 下一个最大元素只需要从n-1个数字中确定，再从n-2个数字中确定，...，最后到0。
3. 当前元素 > 后一个元素，则交换两个元素位置，最大元素就后移了。
   • 也就是说，每次遍历较大的数字一定会逐渐后移。但遇到更大的数时，更大的数开始后移，所以最后一定是最大的数放在最后。

void BubbleSort(int *arr, int n)
{
    for (int i = n - 1; i > 0; i--) // 预留位置索引
        for (int j = 0; j < i; j++) // 当前元素和后一个元素比较，预留索引的比较通过j+1实现
            if (arr[j] > arr[j+1]) // 当前元素 > 后一个元素，则交换两个元素位置，最大元素就后移了。
                swap(&arr[j], &arr[j+1]);
}

2. 选择排序

核心思想：

• 把最前面的位置留给最小元素。下次循环的时候就可以少遍历一个数。

• 找到目标索引，最后进行交换。

过程：

1. 从当前位置开始到最后一个元素，找到最小的元素索引。
2. 找到最小元素的索引，如果和当前位置不一样，就交换两个元素。

void SelectionSort(int *arr, int n)
{
    int i, j, idx;
    for (i = 0; i < n - 1; i++) { // 预留位置索引
        // 1.从当前位置开始到最后一个元素，找到最小的元素索引
        idx = i;
        for (j = i + 1; j < n; j++) // 当前位置不用比较，从下一个位置开始
            if (arr[j] < arr[idx])
                idx = j;
        // 2.找到最小元素的索引，如果和当前位置不一样，就交换两个元素
        if (idx != i)
            swap(&arr[i], &arr[idx]);
    }
}

2.1 比较冒泡和选择排序

都是预留一个位置给目标元素，但是又有些不同。

• 冒泡排序会不断交换元素。

• 选择排序只会在最后判断是否需要交换。

当然预留位置是最前还是最后都可以实现对应的算法。

比如冒泡算法，如果预留的位置是最前也可以做，但可能就不叫冒泡算法了。

冒泡算法：水中底部压力大，气泡较小，随着气泡上升，压力变小，气泡变大。

void BubbleSort2(int *arr, int n)
{
    for (int i = 0; i < n - 1; i++) // 预留位置索引
        for (int j = n - 1; j > i; j--) // 当前元素和前一个元素比较，结束位置为预留位置的后一个位置
            if (arr[j] < arr[j-1]) // 当前元素 < 前一个元素，则交换两个元素位置，最小元素就前移了。
                swap(&arr[j], &arr[j-1]);
}

同样，选择排序也可以预留最后的位置。

void SelectionSort2(int *arr, int n)
{
    int i, j, idx;
    for (i = n - 1; i > 0; i--) { // 预留位置索引
        // 1.从最后一个元素开始向前查找，找到最大的元素索引
        idx = i;
        for (j = i - 1; j >= 0; j--) // 当前位置不用比较，从前一个位置开始
            if (arr[j] > arr[idx])
                idx = j;
        // 2.找到最大元素的索引，如果和当前位置不一样，就交换两个元素
        if (idx != i)
            swap(&arr[i], &arr[idx]);
    }
}

3. 插入排序

类似于链表的头插法，我们把数组分为已排序部分和未排序部分。

你可以想象你正在摸扑克牌，你现在手中有一张拍，然后继续摸牌，摸牌的同时对你手中的牌进行排序(插入到合适的位置)。

• 第一张牌，索引0不需要排序。
• 继续摸牌，找到合适的位置i，将i后的牌后移。(给这张牌滕出位置)
• 插入摸到的这张牌。

void InsertionSort(int *arr, int n)
{
    int i, j, tmp;
    for (i = 1; i < n; i++) { // 第一张牌，索引0不需要排序，直接跳过从1开始
        tmp = arr[i]; // 摸到的下一张牌，即未排序部分的开头
        for (j = i; j >= 1 && arr[j-1] > tmp; j--) // 从后往前遍历，将更大的牌后移(前面的是排序过的，是从小到大排列的)
            arr[j] = arr[j-1];
        arr[j] = tmp; // 循环将比摸到的牌更大的牌后移了，结束的位置就是插入牌的位置
    }
}

4. 希尔排序

其实就是分治法升级版的插入排序，又称为缩小增量排序。我们不断减半增量，直到增量为1时，退化为普通插入排序。

插入排序过程中：

• 如果新摸到的是较大的牌，不需要滕位置，或者只需要滕很少的位置，就行了。
• 如果新摸到的是较小的牌，每次要滕位置的时候，只能一个位置一个位置地挪，是非常低效的。

希尔排序通过增量进行了分组(分治)，比较的是arr[j-increment]和arr[j]，跨度是increment，如果摸到的是较小的牌，只需要移动1次，而插入排序需要移动increment次。

• 也就是说希尔排序的优势是，能让较小的牌更容易来到数组的前面部分，节约了移动次数。

void ShellSort(int *arr, int n)
{
    int i, j, tmp, increment;
    for (increment = n/2; increment > 0; increment /= 2) { // 增量变化
        for (i = increment; i < n; i++) { // 增量是increment，不同增量分组时，第一张摸到的牌
            tmp = arr[i]; // 摸到的下一张牌，即未排序部分的开头
            for (j = i; j >= increment && arr[j - increment] > tmp; j -= increment) // 从后往前遍历，将更大的牌后移(前面的是排序过的，是从小到大排列的)
                arr[j] = arr[j - increment]; 
            arr[j] = tmp; // 循环将比摸到的牌更大的牌后移了，结束的位置就是插入牌的位置
        }
    }
}

当increment等于1的时候就和插入排序一模一样了。

需要注意的是：

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

5. 堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为，它也是不稳定排序。

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

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

或者

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

如下图：

大顶堆、小顶堆

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

数组表示

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆： arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆： arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的基本思想是：

1. 用待排序序列构造一个大顶堆。
2. 将其与末尾元素进行交换，此时末尾就为最大值。
3. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
4. 如此反复执行，便能得到一个有序序列了。

我们可以发现其实堆排序还是一种选择排序，用一句话概括思想：

利用堆结构特性，不断选出最大值，放到最后。

// 左儿子索引
#define LeftChild(i) (2 * (i) + 1)

/// 为目标节点找到合适的位置
/// @param arr 数组
/// @param i 当前要调整的节点索引
/// @param n 节点总数
void FormatHeap(int *arr, int i, int n) {
    int child, tmp;
    tmp = arr[i]; // 目标节点
    for (; LeftChild(i) < n; i = child) { // 从当前节点开始，不断遍历子节点
        child = LeftChild(i); // 获取左儿子
        // 左儿子如果是n-1就没有右儿子了，右儿子如果比左儿子大，就选右儿子
        if (child != n-1 && arr[child + 1] > arr[child])
            child++;
        // 如果子节点比目标节点大，则子节点上移覆盖父节点，滕出位置给目标节点，否则结束排序
        if (tmp < arr[child])
            arr[i] = arr[child];
        else
            break;
    }
    arr[i] = tmp; // 当前节点填入目标节点
}

void HeapSort(int *arr, int n) {
    int i;
    // 通过可能有值的父节点n/2-1开始，倒序遍历所有子节点
    // 也就是说，先排好下层节点，再排上层节点，所以FormatHeap的内遍历深度只会向下1层
    for (i = n/2 - 1; i >= 0; i--)
        FormatHeap(arr, i, n);
    // 构建好大顶堆后开始排序
    for (i = n-1; i > 0; i--) { // 预留位置索引(最后)
        swap(&arr[0], &arr[i]); // 将堆顶的最大元素，和预留位置元素交换
        // 现在只有栈顶的元素没有被放到合适的位置，所以是0
        // 预留位置已经填入了合适的值，所以总的个数现在是预留位置索引
        FormatHeap(arr, 0, i);
    }
}

6. 归并排序

归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略。

将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起。

归并排序

进行合并时，我们需要一个额外的数组来进行辅助排序，再回填回原数组。

6.1 递归写法

/// 治，缝合，把结果存入b数组
/// @param a 数组a
/// @param b 数组b
/// @param lb 左边开始的索引
/// @param center 中间的索引
/// @param rEnd 结束的索引
void Merge(int *a, int *b, int lb, int center, int rEnd)
{
    int i, rb, count;
    i = lb; // 遍历开始
    rb = center + 1; // 右边开始的索引
    count = rEnd - lb + 1; // 缝合需要缝合的总数
    while (lb <= center && rb <= rEnd) // 把两个部分按大小存入临时数组b
        if (a[lb] < a[rb])
            b[i++] = a[lb++];
        else
            b[i++] = a[rb++];
    while (lb <= center) // 如果左半部分还有剩，则全部接到数组b后面
        b[i++] = a[lb++];
    while (rb <= rEnd) // 如果右半部分还有剩，则全部接到数组b后面
        b[i++] = a[rb++];
    for (int i = 0; i < count; i++, rEnd--) // 将b中的结果，回填到数组a中
        a[rEnd] = b[rEnd];
}

/// 分治
/// @param a 数组a
/// @param b 数组b
/// @param l 开始索引
/// @param r 结束索引
void RecursionMergeSort(int *a, int *b, int l, int r)
{
    if (l < r) { // 递归结束条件，结束时每个元素都变成单个的了
        int center = (l + r) >> 1 // 找到中心位置
        RecursionMergeSort(a, b, l, center); // 分成左半部分
        RecursionMergeSort(a, b, center + 1, r); // 分成右半部分
        Merge(a, b, l, center + 1, r); // 合并
    }
}

void MergeSort(int *arr, int n)
{
    int *b = malloc(n * sizeof(int)); // 临时数组，用于存放缝合结果
    if (b) {
        RecursionMergeSort(arr, b, 0, n-1);// 分治
        free(b);
    }
    else
        FatalError("No space for temp array!")
}

6.2 循环写法

/// 治，缝合，把结果存入b数组
/// @param a 数组a
/// @param b 数组b
/// @param lb 左边开始的索引
/// @param center 中间的索引
/// @param rEnd 结束的索引
void Merge(int *a, int *b, int lb, int center, int rEnd)
{
    int i, rb, count;
    i = lb; // 遍历开始
    rb = center + 1; // 右边开始的索引
    count = rEnd - lb + 1; // 缝合需要缝合的总数
    while (lb <= center && rb <= rEnd) // 把两个部分按大小存入临时数组b
        if (a[lb] < a[rb])
            b[i++] = a[lb++];
        else
            b[i++] = a[rb++];
    while (lb <= center) // 如果左半部分还有剩，则全部接到数组b后面
        b[i++] = a[lb++];
    while (rb <= rEnd) // 如果右半部分还有剩，则全部接到数组b后面
        b[i++] = a[rb++];
    for (int i = 0; i < count; i++, rEnd--) // 将b中的结果，回填到数组a中
        a[rEnd] = b[rEnd];
}

void LoopMergeSort(int *a, int *b, int n)
{
    int i, l, center, r, size;
    size = 1; // 每组里面的元素数量
    while (size < n) {
        for (i = 0; i < n;) {
            l = i; // 左边开始索引
            center = l + size - 1; // 中点索引
            r = center + size; // 右边结束索引
            r = r < n - 1 ? r : n - 1; // 右边部分可能没有那么多
            Merge(a, b, l, center, r); // 合并两个部分
            i = r + 1; //下一组的开始索引
        }
        size *= 2; // 合并的总大小翻倍
    }
}

void MergeSort(int *arr, int n)
{
    int *b = malloc(n * sizeof(int)); // 临时数组，用于存放缝合结果
    if (b) {
        LoopMergeSort(arr, b, n);
        free(b);
    }
    else
        FatalError("No space for temp array!")
}

7. 快速排序

快速排序是对冒泡排序的一种改进。

基本思想：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序过程：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分。
2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
   • 此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
3. 左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

7.1 递归写法

int QuickSortKeyIndex(int *arr, int left, int right)
{
    int i = left; // 开始的索引
    int j = right; // 结束的索引
    int key = arr[left]; // 分界值
    while (i < j) { // 把比分界值大的放右边，比分界值小的放左边
        while (i < j && key <= arr[j]) //从右往左，跳过比分界值大的部分
            j--;
        arr[i] = arr[j]; // 把比分界值小的值放到i对应的索引
        while (i < j && key >= arr[i]) //从左往右，跳过比分界值小的部分
            i++;
        arr[j] = arr[i]; // 把比分界值大的值放到j对应的索引
    }
    arr[i] = key; // 在组内找完一遍以后就把分界值key回归
    return i;
}

void RecursionQuickSort(int *arr, int left, int right)
{
    if (left < right) { // 递归结束条件
        int i = QuickSortKeyIndex(arr, left, right); // 确定分界值的位置，然后分界值不再参与排序
        RecursionQuickSort(arr, left, i - 1); // 分为左半部分再来一遍
        RecursionQuickSort(arr, i + 1, right); // 分为右半部分再来一遍
    }
}

void QuickSort(int *arr, int n) {
        RecursionQuickSort(arr, 0, n-1);
}

7.2 循环写法

利用栈结构辅助，将栈帧记录的数据，存入自己的栈结构。

int QuickSortKeyIndex(int *arr, int left, int right)
{
    int i = left; // 开始的索引
    int j = right; // 结束的索引
    int key = arr[left]; // 分界值
    while (i < j) { // 把比分界值大的放右边，比分界值小的放左边
        while (i < j && key <= arr[j]) //从右往左，跳过比分界值大的部分
            j--;
        arr[i] = arr[j]; // 把比分界值小的值放到i对应的索引
        while (i < j && key >= arr[i]) //从左往右，跳过比分界值小的部分
            i++;
        arr[j] = arr[i]; // 把比分界值大的值放到j对应的索引
    }
    arr[i] = key; // 在组内找完一遍以后就把分界值key回归
    return i;
}

void LoopQuickSort(int *arr, int n)
{
    int top = -1;
    int *stack = (int *)malloc(sizeof(int) * (n + 4));
    stack[++top] = 0;
    stack[++top] = n - 1;
    int left, i, right;
    while (top > -1) {
        right = stack[top--];
        left = stack[top--];
        i = QuickSortKeyIndex(arr, left, right);
        if (left < i-1){
            stack[++top] = 0;
            stack[++top] = i-1;
        }
        if (i+1 < right) {
            stack[++top] = i+1;
            stack[++top] = right;
        }
    }
}

void QuickSort(int *arr, int n) {
    LoopQuickSort(arr, n);
}