数据结构中排序的进阶篇章（其二）

数据结构中排序的进阶篇章（其二）

接续前文展开排序相关内容

目录

一. 交换排序

基本思想：

所谓交换操作，乃是依据序列中两个记录键值的对比结果，对这两个记录在序列里的位置进行对换。交换排序的特点体现为：将键值较大的记录朝着序列的尾部移动，把键值较小的记录往序列的前部挪动。

1.1 冒泡排序

1.1.1 代码实现

void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

void BubbleSort(int* a, int n)
{
    for (int j = 0; j < n; j++)
    {
        bool hasExchanged = false;
        for (int i = 1; i < n - j; i++)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                hasExchanged = true;
            }
        }

        if (!hasExchanged)
        {
            break;
        }
    }
}

1.3 冒泡排序的特性总结：

1. 冒泡排序是一种极易理解的排序方式
2. 时间复杂度：O(N²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

2.1 快速排序

2.1.1 基本思想

快速排序是由Hoare在1962年提出的一种基于二叉树结构的交换排序方法。其基本思路是：从待排序的元素序列中任意选取一个元素作为基准值，按照该排序码将待排序集合划分成两个子序列，使得左子序列中的所有元素都小于基准值，右子序列中的所有元素都大于基准值，之后对左右子序列重复这一过程，直至所有元素都排列到相应的位置上。

将区间依据基准值划分为左右两部分的常见方式有：

2.2.2 代码实现

将区间依据基准值划分为左右两部分的常见方式如下：

1. hoare版本

// 三数取中函数
int GetMidNumi(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else // a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] < a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

// hoare版本快速排序
void QuickSort(int* a, int left, int right)
{
    // 三数取中操作
    int midi = GetMidNumi(a, left, right);
    if (midi != left)
        swap(&a[midi], &a[left]);

    int key = left;
    while (left < right)
    {
        while (a[right] >= a[key])
            right--;

        while (left < right && a[left] <= a[key])
            left++;

        swap(&a[right], &a[left]);
    }
    swap(&a[key], &a[left]);

}

2. 挖坑法

// 挖坑法实现快速排序
void PartSort2(int* a, int left, int right)
{
    // 三数取中
    int midi = GetMidNumi(a, left, right);
    if (midi != left)
        swap(&a[midi], &a[left]);

    if (left >= right)
        return;
    int key = a[left];
    int hole = left;
    while (left < right)
    {
        while (a[right] >= a[key])
            right--;

        a[hole] = a[right];
        hole = right;

        while (left < right && a[left] <= a[key])
            left++;

        a[right] = a[left];
        hole = left;

    }
    a[left] = key;
    hole = left;

    PartSort2(a, 0, hole - 1);
    PartSort2(a, hole + 1, right);

}

3. 前后指针版本

// 前后指针法实现快速排序
void PartSort3(int* a, int left, int right)
{
    // 三数取中
    int midi = GetMidNumi(a, left, right);
    if (midi != left)
        swap(&a[midi], &a[left]);

    if (left >= right)
        return;
    int key = left;
    int prev = left;
    int cur = left + 1;
    while(cur <= right)
    {
        if (a[cur] < a[key])
        {
            prev++;
            swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    swap(&a[prev], &a[key]);

    PartSort3(a, 0, prev - 1);
    PartSort3(a, prev + 1, right);
}

2.2.3 快速排序的优化（三数取中）

三数取中的基本思路是：在待排序的数组（或子数组）中，选取第一个元素、最后一个元素以及中间位置的元素，然后对这三个元素的值进行比较，取它们的中间值作为基准值（pivot）。这么做的目的是尽可能选择一个处于数据中间位置的元素作为基准，从而减少数据分区的不均衡性。

实现步骤

1. 确定元素位置：首先，找出数组（或子数组）的第一个元素、最后一个元素以及中间位置的元素。
2. 比较元素值：接着，对这三个元素的值进行比较。
3. 选取中间值：依据比较结果，将这三个元素按从小到大的顺序进行排列（必要时可交换它们的位置），然后把中间的元素选为基准值（pivot）。
4. 进行分区操作：以这个基准值为依据，对数组进行分区，也就是让小于基准值的元素位于基准值的左边，大于基准值的元素处在基准值的右边。

// 三数取中函数
int GetMidNumi(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else // a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] < a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
}

3.1 快速排序非递归

3.1.1 代码实现

非递归实现借助栈的压栈和出栈来开展排序

#include <stdio.h>
#include "Stack.h"

// 快速排序非递归实现
void QuickSortNonR(int* a, int left, int right)
{
    Stack st;
    StackInit(&st);

    int end = right;
    int begin = left;

    StackPush(&st, end);
    StackPush(&st, begin);

    while (!StackEmpty(&st))
    {
        begin = StackTop(&st);
        StackPop(&st);
        end = StackTop(&st);
        StackPop(&st);
        int keyi = PartSort1(a, begin, end);
        //[begin , keyi - 1] [keyi] [keyi + 1 , end]
        if (end > keyi + 1)
        {
            StackPush(&st, end);
            StackPush(&st, keyi + 1);
        }
        if (keyi - 1 > begin)
        {
            StackPush(&st, keyi - 1);
            StackPush(&st, begin);
        }
    }
}

快速排序的特性总结：

1. 快速排序整体的综合性能以及适用场景都较为不错，所以才被称作快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

二. 归并排序

基本思想：

归并排序（MERGE-SORT）是建立在归并操作之上的一种高效排序算法，该算法是采用分治法（Divide andConquer）的一个非常典型的应用。它的做法是将已有序的子序列进行合并，从而得到完全有序的序列；也就是先让每个子序列达到有序状态，再让子序列段之间实现有序。要是把两个有序表合并成一个有序表，就称为二路归并。归并排序的核心步骤如下：

代码实现

void _Catego(int* a, int begin, int end, int* copy)
{
    if (begin >= end)
        return;

        int i = begin;
        int mid = (begin + end) / 2;
        _Catego(a, begin, mid, copy);
        _Catego(a, mid+1, end, copy);

        int begin1 = begin; int end1 = mid;
        int begin2 = mid+1;  int end2 = end;
        while (begin2 <= end2 && begin1 <= end1)
        {
            if (a[begin1] > a[begin2])
            {
                copy[i++] = a[begin2++];
            }
            else
            {
                copy[i++] = a[begin1++];
            }
        }

        while (begin2 <= end2)
        {
            copy[i++] = a[begin2++];
        }

        while (begin1 <= end1)
        {
            copy[i++] = a[begin1++];
        }
    memcpy(a + begin, copy + begin, sizeof(int) * (end - begin + 1));
}


void CategoSort(int* a, int n)
{
    int* copy = (int*)malloc(sizeof(int) * n);
    if (copy == NULL)
    {
        perror("malloc");
        return;
    }

    _Catego(a, 0, n-1, copy);
    free(copy);
}

非比较排序 （非递归）

非递归实现时需留意越界问题：要对end1、begin2、end2分别进行边界处理

void CatagoSort(int *a,int n)
{
    int* copy = (int*)malloc(sizeof(int) * n);
    if (copy == NULL)
    {
        perror("malloc");
        return;
    }


    int gap = 1;

    while (gap < n)
    {
        int j = 0;
        int i = 0;
        for (int i = 0; i < n; i += 2*gap)
        {
            int begin1 = i; int end1 = i + gap -1;
            int begin2 = i + gap; int end2 = i + 2 * gap -1;

            // 间距为gap的多组数据，归并完以后，一把拷贝(梭哈)

            if (end1 >= n)
            {
                end1 = n - 1;
                begin2 = n;
                end2 = n-1;
            }
            else if (begin2 >= n)
            {
                begin2 = n;
                end2 = n - 1;
            }
            else if (end2 >= n)
            {
                end2 = n - 1;
            }

            printf("[%d] [%d] [%d] [%d]", begin1, end1, begin2, end2);
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] > a[begin2])
                {
                    copy[j++] = a[begin2++];
                }
                else
                {
                    copy[j++] = a[begin1++];
                }
            }
            while (begin1 <= end1)
            {
                copy[j++] = a[begin1++];
            }
            while (begin2 <= end2)
            {
                copy[j++] = a[begin2++];
            }
        }
        printf("\n");
        memcpy(a, copy, sizeof(int) * n);
        gap *= 2;
    }
    memcpy(a, copy, sizeof(int) * n);
    free(copy);
}

void MergeSortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail\n");
        return;
    }

    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            // [begin1,end1][begin2, end2]
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            //printf("[%d,%d][%d,%d] ", begin1, end1,begin2,end2);

            if (end1 >= n || begin2 >= n)
            {
                break;
            }

            if (end2 >= n)
            {
                end2 = n - 1;
            }

            printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);

            int j = i;
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[j++] = a[begin1++];
                }
                else
                {
                    tmp[j++] = a[begin2++];
                }
            }

            while (begin1 <= end1)
            {
                tmp[j++] = a[begin1++];
            }

            while (begin2 <= end2)
            {
                tmp[j++] = a[begin2++];
            }

            // 归并一部门拷贝一部分
            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
        }

        printf("\n");

        gap *= 2;
    }

    free(tmp);
}

归并排序的特性总结：

1. 归并排序的不足之处在于需要O(N)的空间复杂度，归并排序的思路更多地是用于解决磁盘