• 八（7+1）大排序详解（学数据结构怎么能不学排序) ✈️

    学习数据结构怎么能不学排序呢，今天我们来用C语言实现一下八大排序🚀 ✈️ 🚁
    话不多说，开始上车
    在这里插入图片描述

    目录

    🚀前言

    排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
    分内部排序和外部排序，若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
    内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

    常见的排序算法：

    在这里插入图片描述

    各种常用排序算法的时间复杂度和空间复杂度：
    在这里插入图片描述

    🚀1. 直接插入排序

    基本思想：

    把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

    在我们的日常生活中，也有用到插入排序的时候，就例如打扑克：
    在这里插入图片描述

    动图演示：
    在这里插入图片描述

    实现思路：

    在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
     但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

    🚁代码展示：

    void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; ++i)//为防止x越界，需要使 i < n-1
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
        //代码执行到此位置有两种情况:
		//1.待插入元素找到应插入位置（break跳出循环到此）
		//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    直接插入排序特性：

    1. 元素集合越接近有序，直接插入排序算法的时间效率越高
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)
    4. 稳定性：稳定

    🚀2. 希尔排序

    基本思想：

    希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。即使序列相对有序。
    当到达=1时，所有记录在统一组内排好序。

    例如：
    在这里插入图片描述

    动图演示：

    在这里插入图片描述

    实现思路：

    希尔排序的目的是先让序列相对有序，然后再进行插入排序，先将序列分成距离相等的小组进行排序，让序列实现相对有序

    🚁代码展示：

    void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //gap > 1时候是预排序
		//gap最后一次等于1,是直接插入排序
        gap = gap / 3 + 1;
        //gap = gap / 2;

        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    希尔排序特性：

    1. 希尔排序是对直接插入排序的优化。
    2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样再进行直接插入排序可以提高效率，从而达到优化。
    3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。
    4. 稳定性：不稳定。

    🚀3. 选择排序

    基本思想：

    第一次从序列中选出最小（最大)的一个元素，存放在序列的起始(末尾)位置，然后遍历比较选出次小(次大)的一个元素，存放在下一个位置，重复这样的步骤直到全部待排序的数据元素排完 。

    动图演示：
    在这里插入图片描述

    实现思路：

    • 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素,将它与这组元素中的最后一个（第一个）元素交换
    • 在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
    • 我们可以在第一遍遍历中选出最大以及最小值,然后将最小值与起始位置交换，将最大值与末尾位置交换,从而提升效率。

    注意事项：

    当最大值刚好在第一个位置的情况：

    • 交换了最小值之后，最大值就被交换到了min的位置
    • 在每次交换了最小值之后应该判断一下最大值是否在起始位置，如果在需要将max赋值为min。
      在这里插入图片描述

    🚁代码展示：

    void SelectSort(int* a, int n)
{
    assert(a);
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] < a[mini])
                mini = i;

            if (a[i] > a[maxi])
                maxi = i;
        }
        Swap(&a[begin], &a[mini]);

        if (begin == maxi)
        {
            maxi = mini;
        }

        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    选择排序的特性：

    1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)
    4. 稳定性：不稳定

    🚀4. 堆排序

    基本思想：

    • 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
    • 需要掌握两种算法：1.向下调整算法 2.向上调整算法

    算法学习:

    • 向下调整算法 : 左右子树必须是一个堆,才能进行调整
      请添加图片描述
    • 向上调整算法:
      请添加图片描述

    动图演示：

    在这里插入图片描述

    实现思路：
    在这里插入图片描述

    🚁代码展示：

    //向上调整算法
void AdjustUp(HPDataType* a, size_t child)
{
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
        //if (a[child] > a[parent]) //大根堆
        if (a[child] < a[parent]) //小根堆
        {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
 
//向下调整算法
void AdjustDown(HPDataType* a, size_t size, size_t root)
{
    int parent = root;
    int child = 2 * parent + 1;
    while (child < size)
    {
        //1、确保child的下标对应的值最小，即取左右孩子较小那个
        if (child + 1 < size && a[child + 1] < a[child]) //得确保右孩子存在
        {
            child++; //此时右孩子小
        }
        //2、如果孩子小于父亲则交换，并继续往下调整
        if (a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

//堆排序
void HeapSort(int*a,int n)
{
 
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
 
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    堆排序的特性：

    堆排序使用堆来选数，效率就高了很多。
    2. 时间复杂度：O(N*logN)
    3. 空间复杂度：O(1)
    4. 稳定性：不稳定

    🚀5. 冒泡排序

    基本思想：

    冒泡排序是我们在C语言学习过程就要求掌握的排序方法，就是两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置，遍历n-1次就可以把序列排好。

    动图演示：

    在这里插入图片描述

    实现思路：

    两两相比选最大

    🚁代码实现

    void BubbleSort(int* a, int n)
{
    assert(a);

    for (int j = 0; j < n - 1; ++j)
    {
        int exchange = 0;
        for (int i = 1; i < n - j; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0)
        {
            break;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    冒泡排序的特性：

    1. 冒泡排序是一种非常容易理解的排序
    2. 时间复杂度：O(N^2)
    3. 空间复杂度：O(1)
    4. 稳定性：稳定

    🚀6. 快速排序（王者）

    基本思想：

    任取待排序元素序列中的某元素作为基准值(key)，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

    ✈️6.1 hoare

    实现思路：

    • 选定一个基准值key，一般选定最左边或者最右边（方便）。
    • 确定两个指针begin 和end 分别从开头和结尾向中间遍历数组。
    • 如果选最右边为key，那么begin指针先走，如果遇到大于key的数就停下来。
    • 然后end再走，遇到小于基准值的数就停下来。
    • 交换begin和end指针对应位置的值。
    • 重复以上步骤，直到left = right ，最后将key与left(right)位置的值交换。

    动图演示：

    在这里插入图片描述

    细节拆解：

    在这里插入图片描述

    🚁代码实现

    // [begin, end]
// 快速排序hoare版本
int PartSort1(int* a, int begin, int end)
{
    
    int key = end;//选定基准值
    while (begin < end)
    {
        //选右边为基准值，左指针先走
        while (begin < end && a[begin] <= a[key])
        {
            begin++;
        }
 
        //右指针再走
        while (begin < end && a[end] >= a[key])
        {
            end--;
        }
 
        Swap(&a[begin], &a[end]);
    }
    Swap(&a[begin], &a[key]);
    return begin;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    ✈️6.2 挖坑法

    和hoare差不多，可能相对好理解一点
    实现思路：

    • 选出key，在该数据位置形成一个坑。
    • 还是定义一个begin和一个end，begin从左向右走，end从右向左走。（若在最左边挖坑，则需要end先走；若在最右边挖坑，则需要begin先走）。
    • 在走的过程中，若R遇到小于key的数，则将该数抛入坑位，并在此处形成一个坑位，这时L再向后走，若遇到大于key的数，则将其抛入坑位，又形成一个坑位，如此循环下去，直到最终L和R相遇，这时将key抛入坑位即可。（选取最左边的作为坑位）

    动图演示：
    在这里插入图片描述

    🚁代码实现

    // 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];//取出基准值
    int hole = left;//保存坑的位置
    while (left < right)
    {
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;
 
        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    ✈️6.3 前后指针法

    这是一种全新的思路，和上面两种方法大不相同

    基本思路：

    • 选定基准值，定义prev和cur指针(cur = prev + 1)
    • cur先走，遇到小于key的数停下，然后将prev向后移动一个位置
    • 将prev对应值与cur对应值交换
    • 重复上面的步骤，直到cur走出数组范围
    • 最后将key与prev对应位置交换
    • 递归排序以key为界限的左右区间

    动图演示：
    在这里插入图片描述

    细节拆分：
    在这里插入图片描述
    在这里插入图片描述

    🚁代码演示

    // 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    //1.将基准值定在left
    int keyi = left;
    int prev = left;
    int cur =  left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
        
    }
    Swap(&a[prev], &a[keyi]);

    //2.将基准值定在right
    /*int keyi = right;
    int prev = left - 1;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    Swap(&a[keyi], &a[++prev]);*/
    return prev;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    ✈️6.4 快速排序优化

    上面的三种方法还有一些缺陷，会进行一些不必要的递归

    • 在key的选择上，如果选择的key为恰好为最小值，会进行不必要的递归。
    • 在排序大量有序数据或者接近有序数据时，效率会比较低，甚至可能会出现程序崩溃的情况。这是因为在排序有序数据时，快速排序的递归调用次数过多，会导致栈溢出的情况。

    优化方法：

    • 三数取中法选key
    • 递归到小的子区间时，可以考虑使用插入排序

    🚁代码实现

    //三数取中
 
int MidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	//防止mid越界
	//int mid = left+(right - left) / 2;
 
	if (a[left] < a[right])
	{
		if (a[mid] < a[left])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
	else
	{
		if (a[mid] > a[left])
		{
			return left;
		}
		else if (a[mid] < a[right])
		{
			return right;
		}
		else
		{
			return mid;
		}
	}
}

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    //1.将基准值定在left
    int keyi = left;
    int prev = left;
    int cur =  left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
        
    }
    Swap(&a[prev], &a[keyi]);

    //2.将基准值定在right
    /*int keyi = right;
    int prev = left - 1;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    Swap(&a[keyi], &a[++prev]);*/
    return prev;
}

void QuickSort(int* a, int begin, int end)
{
    assert(a);
    if (begin >= end)
    {
        return;
    }
 
    
    int keyi = PartSort1(a, begin, end);
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
    
 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    ✈️6.5 快速排序（非递归）

    快排（非递归）需要用到栈存放需要排序的左右区间，运用栈可以解决栈溢出的问题

    实现思路：

    • 将数组左右下标入栈，
    • 若栈不为空，两次取出栈顶元素，分别为闭区间的左右界限
    • 将区间中的元素按照快排的三种方法得到key
    • 再以key为界限，若key左右区间中有元素，则将区间入栈
    • 重复上述步骤直到栈为空

    🚁代码实现

    void QuickSortNonR(int* a, int left, int right)
{
    //创建栈
    struct Stack st;
    StackInit(&st);
 
    //原始数组区间入栈
    StackPush(&st, right);
    StackPush(&st, left);
 
    //将栈中区间排序
    while (!StackEmpty(&st))
    {
        //注意：如果right先入栈，栈顶为left
        left = StackTop(&st);
        StackPop(&st);
        right = StackTop(&st);
        StackPop(&st);
        
        //得到基准值
        int mid = PartSort3(a, left, right);
 
        // 以基准值为分割点，形成左右两部分
        if (right > mid+1)
        {
            StackPush(&st, right);
            StackPush(&st, mid + 1);
        }
        if (left < mid - 1)
        {
            StackPush(&st, mid - 1);
            StackPush(&st, left);
        }
    }
    StackDestory(&st);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    快速排序的特性：

    1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
    2. 时间复杂度：O(N*logN)
    3. 空间复杂度：O(logN)
    4. 稳定性：不稳定

    🚀7. 归并排序

    基本思想：

    归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

    核心步骤：
    在这里插入图片描述

    动图演示：
    在这里插入图片描述

    🚁代码实现

    void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
    if (left >= right)
    {
        return;
    }
 
    //划分数组，每次一分为二
    int mid = (left + right) / 2;
    _MergeSort(a, left, mid,tmp);//划分左区间
    _MergeSort(a, mid + 1, right,tmp);//划分右区间
 
    //合并有序序列
    int begin1 = left, end1 = mid;//有序序列1
    int begin2 = mid + 1, end2 = right;//有序序列2
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)//注意结束条件为一个序列为空时就停止
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
 
    //两序列不可能同时为空，将剩余元素合并
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
 
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
 
    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
    int j = 0;
    for (j = left; j <= right; j++)
    {
        a[j] = tmp[j];
    }
}
 
// 归并排序递归实现
void MergeSort(int* a, int n)
{
    assert(a);
    //因为需要将两个有序序列合并，需借助额外数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
 
    _MergeSort(a, 0, n - 1,tmp);
 
    free(tmp);
    tmp = NULL;
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
    assert(a);
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
 
    //初始化每组的元素个数为1
    int gap = 1;
    while (gap < n)//gap为n时就只有一个序列了，所以gap
    {
        //归并每两组归并一次
        int index = 0; //记录tmp数组中的元素下标
        for (int i = 0; i < n; i+=2*gap)//两组中的元素个数为2*gap
        {
            //控制两组边界
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            
            //当原数组中元素个数不是2^n时，最后两组组会出现元素不匹配的情况
            //情况1：end1>=n或begin2>=n,即最后两组中只有一组有元素，则不需归并
            if (end1 >= n || begin2 >= n)
            {
                break;
            }
            //情况2：end2>=n，即最后两组中，第二组元素个数小于第一组，则需要调整第二组边界
            if (end2 >= n)
            {
                end2 = n - 1;
            }
 
            //归并
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
 
            while (begin1 <= end1)
            {
                tmp[index++] = a[begin1++];
            }
 
            while (begin2 <= end2)
            {
                tmp[index++] = a[begin2++];
            }
 
            
        }
        //一趟排完后，将归并后的有序序列拷贝到原数组中
        for (int j = 0; j < index; j++)
        {
            a[j] = tmp[j];
        }
        //每次循环每组元素个数增大2倍
        gap *= 2;
    }
 
    free(tmp);
    tmp = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139

    归并排序的特性：

    1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
    2. 时间复杂度：O(N*logN)
    3. 空间复杂度：O(N)
    4. 稳定性：稳定

    🚀8. 基数排序（附）

    实现思想：

    计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。

    操作步骤：

    1. 统计相同元素出现次数
    2. 根据统计的结果将序列回收到原来的序列中
      在这里插入图片描述

    🚁代码实现

    // 计数排序
void CountSort(int* a, int n)
{
    assert(a);
    // 创建计数数组，数组大小为原数组中最大值-最小值+1
    int max = a[0], min = a[0];
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }
    }
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    // 初始化计数数组为0
    memset(count, 0, range * 4);
 
    // 统计次数
    for (i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
    // 根据次数，进行排序
    int j = 0;
    for (i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            a[j++] = i+min;
        }
    }
    free(count);
    count = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    计数排序的特性总结：

    1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
    2. 时间复杂度：O(MAX(N,范围))
    3. 空间复杂度：O(范围)
    4. 稳定性：稳定

    🚀9. 排序代码合集

    ✈️Sort.h

    #pragma once

#include 
#include 
#include 
#include 
#include 
#include 

void PrintArray(int* a, int n);
// 排序实现的接口
 
// 插入排序
void InsertSort(int* a, int n);
 
// 希尔排序
void ShellSort(int* a, int n);
 
// 选择排序
void SelectSort(int* a, int n);
 
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
 
// 冒泡排序
void BubbleSort(int* a, int n);
 
// 快速排序递归实现
 
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
 
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
 
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int begin, int end);
 
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
 
// 归并排序递归实现
void MergeSort(int* a, int n);
 
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);
 
// 计数排序
void CountSort(int* a, int n);


typedef int STDatatype;
typedef struct Stack
{
    STDatatype* a; //动态开辟的空间
    int top; //栈顶
    int capacicy; //容量
}ST;

void StackInit(ST* ps);//初始化
void StackPush(ST* ps, STDatatype x);//插入
bool StackEmpty(ST* ps);//判空
void StackPop(ST* ps);//删除
STDatatype StackTop(ST* ps);//栈顶
int StackSize(ST* ps);//长度
void StackDestory(ST* ps);//销毁

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    ✈️Sort.c

    #include "Sort.h"

void PrintArray(int* a, int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void InsertSort(int* a, int n)
{
    for (int i = 0; i < n - 1; ++i)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

//void ShellSort(int* a, int n)
//{
//    /*int gap = 3;*/
//
//    /*for (int j = 0; j < gap; ++j)
//    {
//        for (int i = j; i < n - gap; i += gap)
//        {
//            int end = i;
//            int tmp = a[end + gap];
//            while (end >= 0)
//            {
//                if (tmp < a[end])
//                {
//                    a[end + gap] = a[end];
//                    end -= gap;
//                }
//                else
//                {
//                    break;
//                }
//            }
//            a[end + gap] = tmp;
//        }
//    }*/
//
//
//    int gap = n;
//    while (gap > 1)
//    {
//        gap = gap / 3 + 1;
//        //gap = gap / 2;
//
//        for (int i = 0; i < n - gap; ++i)
//        {
//            int end = i;
//            int tmp = a[end + gap];
//            while (end >= 0)
//            {
//                if (tmp < a[end])
//                {
//                    a[end + gap] = a[end];
//                    end -= gap;
//                }
//                else
//                {
//                    break;
//                }
//            }
//            a[end + gap] = tmp;
//        }
//
//        //printf("gap:%d->", gap);
//        //PrintArray(a, n);
//    }
//}

void ShellSort(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        //gap = gap / 2;

        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}



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


void AdjustDwon(int* a, int size, int parent)
{
    int child = parent * 2 + 1;
    while (child < size)
    {
        
        if (child + 1 < size && a[child + 1] > a[child])
        {
            ++child;
        }

        if (a[child] > a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


void HeapSort(int* a, int n)
{
    for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    {
        AdjustDwon(a, n, i);
    }

    // O(N*logN)
    int end = n - 1;
    while (end > 0)
    {
        Swap(&a[0], &a[end]);
        AdjustDwon(a, end, 0);
        --end;
    }
}

void SelectSort(int* a, int n)
{
    assert(a);
    int begin = 0, end = n - 1;
    while (begin < end)
    {
        int mini = begin, maxi = begin;
        for (int i = begin + 1; i <= end; ++i)
        {
            if (a[i] < a[mini])
                mini = i;

            if (a[i] > a[maxi])
                maxi = i;
        }
        Swap(&a[begin], &a[mini]);

        if (begin == maxi)
        {
            maxi = mini;
        }

        Swap(&a[end], &a[maxi]);
        ++begin;
        --end;
    }
}


void BubbleSort(int* a, int n)
{
    assert(a);

    for (int j = 0; j < n - 1; ++j)
    {
        int exchange = 0;
        for (int i = 1; i < n - j; ++i)
        {
            if (a[i - 1] > a[i])
            {
                Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }

        if (exchange == 0)
        {
            break;
        }
    }
}

// [begin, end]
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{
    
    int key = right;//选定基准值
    while (left < right)
    {
        //选右边为基准值，左指针先走
        while (left < right && a[left] <= a[key])
        {
            left++;
        }
 
        //右指针再走
        while (left < right && a[right] >= a[key])
        {
            right--;
        }
 
        Swap(&a[left], &a[right]);
    }
    Swap(&a[left], &a[key]);
    return left;
}
 

// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{
    int key = a[left];//取出基准值
    int hole = left;//保存坑的位置
    while (left < right)
    {
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[hole] = a[right];
        hole = right;
 
        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}

// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{
    //1.将基准值定在left
    int keyi = left;
    int prev = left;
    int cur =  left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
        
    }
    Swap(&a[prev], &a[keyi]);

    //2.将基准值定在right
    /*int keyi = right;
    int prev = left - 1;
    int cur = prev + 1;
    while (cur <= right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        cur++;
    }
    Swap(&a[keyi], &a[++prev]);*/
    return prev;
}

void QuickSort(int* a, int begin, int end)
{
    assert(a);
    if (begin >= end)
    {
        return;
    }
 
    
    int keyi = PartSort1(a, begin, end);
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
    
 
}

//三数取中
 
int MidIndex(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    //防止mid越界
    //int mid = left+(right - left) / 2;
 
    if (a[left] < a[right])
    {
        if (a[mid] < a[left])
        {
            return left;
        }
        else if (a[mid] > a[right])
        {
            return right;
        }
        else
        {
            return mid;
        }
    }
    else
    {
        if (a[mid] > a[left])
        {
            return left;
        }
        else if (a[mid] < a[right])
        {
            return right;
        }
        else
        {
            return mid;
        }
    }
}



// 快速排序 非递归实现

void StackInit(ST* ps)
{
    assert(ps);
    //初始化
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}




void StackPush(ST* ps, STDatatype x)
{
    assert(ps);
    //检查空间，满了就增容
    if (ps->top == ps->capacicy)
    {
        //第一次开辟空间容量为4，其它次容量为当前容量*2
        int newcapacity = ps->capacicy == 0 ? 4 : ps->capacicy * 2;
        //第一次开辟空间，a指向空，realloc的效果同malloc
        STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);
        //检查realloc
            //realloc失败
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
            //realloc成功
        ps->a = tmp;
        ps->capacicy = newcapacity;
    }
    //插入数据
    ps->a[ps->top] = x;
    ps->top++;
}
bool StackEmpty(ST* ps)
{
    assert(ps);
    //等于0是真，否则为假
    return ps->top == 0;
}
void StackPop(ST* ps)
{
    assert(ps);
    //删除的话得保证指向的空间不为空
    assert(!StackEmpty(ps));
    //删除
    --ps->top;
}
int StackSize(ST* ps)
{
    assert(ps);
    //此时的top就是长度
    return ps->top;
}
STDatatype StackTop(ST* ps)
{
    assert(ps);
    //找栈顶的话得保证指向的空间不为空
    assert(!StackEmpty(ps));
    //此时的top-1就是栈顶数据
    return ps->a[ps->top - 1];
}
void StackDestory(ST* ps)
{
    assert(ps);
    //a为真代表它指向动态开辟的空间
    if (ps->a)
    {
        free(ps->a);
    }
    ps->a = NULL;
    ps->top = 0;
    ps->capacicy = 0;
}


void QuickSortNonR(int* a, int left, int right)
{
    //创建栈
    struct Stack st;
    StackInit(&st);
 
    //原始数组区间入栈
    StackPush(&st, right);
    StackPush(&st, left);
 
    //将栈中区间排序
    while (!StackEmpty(&st))
    {
        //注意：如果right先入栈，栈顶为left
        left = StackTop(&st);
        StackPop(&st);
        right = StackTop(&st);
        StackPop(&st);
        
        //得到基准值
        int mid = PartSort3(a, left, right);
 
        // 以基准值为分割点，形成左右两部分
        if (right > mid+1)
        {
            StackPush(&st, right);
            StackPush(&st, mid + 1);
        }
        if (left < mid - 1)
        {
            StackPush(&st, mid - 1);
            StackPush(&st, left);
        }
    }
    StackDestory(&st);
}

void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
    if (left >= right)
    {
        return;
    }
 
    //划分数组，每次一分为二
    int mid = (left + right) / 2;
    _MergeSort(a, left, mid,tmp);//划分左区间
    _MergeSort(a, mid + 1, right,tmp);//划分右区间
 
    //合并有序序列
    int begin1 = left, end1 = mid;//有序序列1
    int begin2 = mid + 1, end2 = right;//有序序列2
    int i = left;
    while (begin1 <= end1 && begin2 <= end2)//注意结束条件为一个序列为空时就停止
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
 
    //两序列不可能同时为空，将剩余元素合并
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
 
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
 
    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
    int j = 0;
    for (j = left; j <= right; j++)
    {
        a[j] = tmp[j];
    }
}
 
// 归并排序递归实现
void MergeSort(int* a, int n)
{
    assert(a);
    //因为需要将两个有序序列合并，需借助额外数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
 
    _MergeSort(a, 0, n - 1,tmp);
 
    free(tmp);
    tmp = NULL;
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
    assert(a);
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
 
    //初始化每组的元素个数为1
    int gap = 1;
    while (gap < n)//gap为n时就只有一个序列了，所以gap
    {
        //归并每两组归并一次
        int index = 0; //记录tmp数组中的元素下标
        for (int i = 0; i < n; i+=2*gap)//两组中的元素个数为2*gap
        {
            //控制两组边界
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;
            
            //当原数组中元素个数不是2^n时，最后两组组会出现元素不匹配的情况
            //情况1：end1>=n或begin2>=n,即最后两组中只有一组有元素，则不需归并
            if (end1 >= n || begin2 >= n)
            {
                break;
            }
            //情况2：end2>=n，即最后两组中，第二组元素个数小于第一组，则需要调整第二组边界
            if (end2 >= n)
            {
                end2 = n - 1;
            }
 
            //归并
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index++] = a[begin1++];
                }
                else
                {
                    tmp[index++] = a[begin2++];
                }
            }
 
            while (begin1 <= end1)
            {
                tmp[index++] = a[begin1++];
            }
 
            while (begin2 <= end2)
            {
                tmp[index++] = a[begin2++];
            }
 
            
        }
        //一趟排完后，将归并后的有序序列拷贝到原数组中
        for (int j = 0; j < index; j++)
        {
            a[j] = tmp[j];
        }
        //每次循环每组元素个数增大2倍
        gap *= 2;
    }
 
    free(tmp);
    tmp = NULL;
}

// 计数排序
void CountSort(int* a, int n)
{
    assert(a);
    // 创建计数数组，数组大小为原数组中最大值-最小值+1
    int max = a[0], min = a[0];
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (a[i] > max)
        {
            max = a[i];
        }
        if (a[i] < min)
        {
            min = a[i];
        }
    }
    int range = max - min + 1;
    int* count = (int*)malloc(sizeof(int) * range);
    // 初始化计数数组为0
    memset(count, 0, range * 4);
 
    // 统计次数
    for (i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }
    // 根据次数，进行排序
    int j = 0;
    for (i = 0; i < range; i++)
    {
        while (count[i]--)
        {
            a[j++] = i+min;
        }
    }
    free(count);
    count = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399
    • 400
    • 401
    • 402
    • 403
    • 404
    • 405
    • 406
    • 407
    • 408
    • 409
    • 410
    • 411
    • 412
    • 413
    • 414
    • 415
    • 416
    • 417
    • 418
    • 419
    • 420
    • 421
    • 422
    • 423
    • 424
    • 425
    • 426
    • 427
    • 428
    • 429
    • 430
    • 431
    • 432
    • 433
    • 434
    • 435
    • 436
    • 437
    • 438
    • 439
    • 440
    • 441
    • 442
    • 443
    • 444
    • 445
    • 446
    • 447
    • 448
    • 449
    • 450
    • 451
    • 452
    • 453
    • 454
    • 455
    • 456
    • 457
    • 458
    • 459
    • 460
    • 461
    • 462
    • 463
    • 464
    • 465
    • 466
    • 467
    • 468
    • 469
    • 470
    • 471
    • 472
    • 473
    • 474
    • 475
    • 476
    • 477
    • 478
    • 479
    • 480
    • 481
    • 482
    • 483
    • 484
    • 485
    • 486
    • 487
    • 488
    • 489
    • 490
    • 491
    • 492
    • 493
    • 494
    • 495
    • 496
    • 497
    • 498
    • 499
    • 500
    • 501
    • 502
    • 503
    • 504
    • 505
    • 506
    • 507
    • 508
    • 509
    • 510
    • 511
    • 512
    • 513
    • 514
    • 515
    • 516
    • 517
    • 518
    • 519
    • 520
    • 521
    • 522
    • 523
    • 524
    • 525
    • 526
    • 527
    • 528
    • 529
    • 530
    • 531
    • 532
    • 533
    • 534
    • 535
    • 536
    • 537
    • 538
    • 539
    • 540
    • 541
    • 542
    • 543
    • 544
    • 545
    • 546
    • 547
    • 548
    • 549
    • 550
    • 551
    • 552
    • 553
    • 554
    • 555
    • 556
    • 557
    • 558
    • 559
    • 560
    • 561
    • 562
    • 563
    • 564
    • 565
    • 566
    • 567
    • 568
    • 569
    • 570
    • 571
    • 572
    • 573
    • 574
    • 575
    • 576
    • 577
    • 578
    • 579
    • 580
    • 581
    • 582
    • 583
    • 584
    • 585
    • 586
    • 587
    • 588
    • 589
    • 590
    • 591
    • 592
    • 593
    • 594
    • 595
    • 596
    • 597
    • 598
    • 599
    • 600
    • 601
    • 602
    • 603
    • 604
    • 605
    • 606
    • 607
    • 608
    • 609
    • 610
    • 611
    • 612
    • 613
    • 614
    • 615
    • 616
    • 617
    • 618
    • 619
    • 620
    • 621
    • 622
    • 623
    • 624
    • 625
    • 626
    • 627
    • 628
    • 629
    • 630
    • 631
    • 632
    • 633
    • 634
    • 635
    • 636
    • 637
    • 638
    • 639
    • 640
    • 641
    • 642
    • 643
    • 644
    • 645
    • 646
    • 647
    • 648
    • 649
    • 650
    • 651
    • 652
    • 653
    • 654
    • 655
    • 656
    • 657
    • 658
    • 659
    • 660
    • 661
    • 662
    • 663
    • 664
    • 665

    ✈️main.c

    #include "Sort.h"

void TestInsertSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    InsertSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}

void TestShellSort()
{
    //int a[] = { 9, 1,9,3,8, 2, 5, 7, 4, 8, 6, 3, 5, 4,2,3,6,8,2,1,2,2};
    int a[] = { 9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5};
    ShellSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}

void TestSelectSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    SelectSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}

void TestBubbleSort()
{
    int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
    BubbleSort(a, sizeof(a) / sizeof(int));
    BubbleSort(a, sizeof(a) / sizeof(int));
    PrintArray(a, sizeof(a) / sizeof(int));
}

void TestQuickSort()
{
    int a[] = { 6,1,2,7,9,3,4,5,10,8 };
    QuickSort(a, 0, sizeof(a) / sizeof(int)-1);
    PrintArray(a, sizeof(a) / sizeof(int));
}

// ≤‚ ‘≈≈–Úµƒ–‘ƒ‹∂‘±»
void TestOP()
{
    srand(time(0));
    const int N = 1000000;
    int* a1 = (int*)malloc(sizeof(int)*N);
    int* a2 = (int*)malloc(sizeof(int)*N);
    int* a3 = (int*)malloc(sizeof(int)*N);
    int* a4 = (int*)malloc(sizeof(int)*N);
    int* a5 = (int*)malloc(sizeof(int)*N);
    int* a6 = (int*)malloc(sizeof(int)*N);
    int* a7 = (int*)malloc(sizeof(int)*N);


    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
        a7[i] = a1[i];
    }

    //ShellSort(a1, N);

    long int begin1 = clock();
    //InsertSort(a1, N);
    long int end1 = clock();

    long int begin2 = clock();
    ShellSort(a3, N);
    long int end2 = clock();

    long int begin3 = clock();
    //SelectSort(a3, N);
    long int end3 = clock();

    long int begin4 = clock();
    HeapSort(a4, N);
    long int end4 = clock();

    long int begin5 = clock();
    QuickSort(a5, 0, N - 1);
    long int end5 = clock();

    long int begin6 = clock();
    //MergeSort(a6, N);
    long int end6 = clock();

    long int begin7 = clock();
    //BubbleSort(a7, N);
    long int end7 = clock();

    printf("InsertSort:%ld\n", end1 - begin1);
    printf("ShellSort:%ld\n", end2 - begin2);
    printf("SelectSort:%ld\n", end3 - begin3);
    printf("HeapSort:%ld\n", end4 - begin4);
    printf("QuickSort:%ld\n", end5 - begin5);
    printf("MergeSort:%ld\n", end6 - begin6);
    printf("BubbleSort:%ld\n", end7 - begin7);


    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
}

int main()
{
    //TestInsertSort();
    //TestShellSort();
    //TestSelectSort();
    //TestBubbleSort();
    //TestQuickSort();

    TestOP();

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123

    🚀10. 相关题目训练

    去做题吧！

    题目描述：
    在这里插入图片描述

    //冒泡排序
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    if (numsSize <= 1) {
      return nums;
    }
    bool flag = true;
    for (int i = 0; i < numsSize; ++i) {
      flag = false;
      for (int j = 0; j < numsSize-i-1;++j) {
        if (nums[j] > nums[j+1]) {
          int temp = nums[j];
          nums[j] = nums[j+1];
          nums[j+1] = temp;
          flag = true;
        }
      }
      if (!flag) {
        break;
      }
    }
    return nums;
}
//插入排序
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    if (numsSize <= 1) {
      return;
    }
  
    //! 从第二个元素开始比较 插入
    for (int i = 1; i < numsSize; ++i) {
      //! 当前遍历 需要比较的数字 value
      int value = nums[i];
      int j = i - 1;
      //! 遍历value前面的数组，j不停变小
      for (; j >= 0; --j) {
        if (nums[j] > value) { //! 如果找到比value大的数字，数据向后移动，
          nums[j+1] = nums[j];
        } else { //! 没有找到比当前值小的，不需要移动
          break;
        }
      }
    
      //！ 最后定位到 value的位置
      nums[j+1] = value;
    
    }
    return nums;
}
//选择排序
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    if (numsSize == 1) {
      return;
    }
  
    //! 已排序区间角标
    int point = 0;
    //！ 定位最小值 角标
    int k = point;
  
 
    for (int i = 0; i < numsSize-1; ++i) {
      //！ 未排序最小值，默认取已排序的最后一个元素
      int temp = nums[point];
      int k = point;
      for (int j = point; j < numsSize; ++j) {
        if (temp > nums[j]) {
          temp = nums[j];
          k = j;
        }
      }

      //! 交换
      nums[k] = nums[point];
      nums[point] = temp;
      //! 区间+1
      ++point;
    
    }
    return nums;
}
//归并排序
//! 递归调用函数
void merge_sort_c (int* nums, int p, int r);
//! 合并函数
void merge_arr (int* nums, int p, int q, int r);

int* sortArray(int* nums, int numsSize, int* returnSize){
    merge_sort_c(nums,0,numsSize-1);
    *returnSize = numsSize;
    return nums;
}

void merge_sort_c (int* nums, int p, int r) {
    //! 递归终止条件
    if (p >= r) {
      return;
    }
  
    //! 取p到r之间的中间位置q
    int q;
    q = (p+r)/2;
  
    merge_sort_c(nums,p,q);
    merge_sort_c(nums, q+1, r);
    //! 合并
    merge_arr(nums,p,q,r);
}

void merge_arr (int* nums, int p, int q, int r) {
    int *temp;
    int i , j , k ;
  
    //! 创建一个连续的空间 作为临时数组
    temp = (int *)malloc((r-p+1) * sizeof(int));
  
    if (!temp) {
      abort();
    }
  
    for (i = p,j = q+1,k=0; i<=q && j<= r;) {
      if (nums[i] <= nums[j]) {
        temp[k++] = nums[i++];
      } else {
        temp[k++] = nums[j++];
      }
    
    }
  
    //!
    if (i == q+1) {
      for (; j <= r;) {
        temp[k++] = nums[j++];
      }
    
    } else {
      for (; i <= q; ) {
        temp[k++] = nums[i++];
      }
    }
  
    //! 拷贝回原来的数组
    memcpy(nums+p,temp,(r-p+1) * sizeof(int));
    free(temp);
}
//快速排序
//! 递归函数，
void quick_sort (int* nums,int p, int r);
// 分区函数
int partition (int* nums, int p, int r);
//！ 交换函数
void swap(int *nums, int i,int j);

int* sortArray(int* nums, int numsSize, int* returnSize){
  quick_sort(nums, 0, numsSize-1);
  *returnSize = numsSize;
  return nums;
}

void quick_sort (int* nums,int p, int r) {
  if (p >= r) {
    return;
  }
  int q;
  //!  
  q = partition(nums, p, r);
  quick_sort(nums, p,q-1);
  quick_sort(nums, q+1, r);
}

int partition (int* nums, int p, int r) {
  int i,j;
  i = j = p;

  //! 随机选择一个元素作为锚点，跟最后一个元素交换
  int q = rand() % (r - p + 1) + p;
  swap(nums,q,r);
 
  for (; j < r; j++) {
    if (nums[j] < nums[r]) {
      if (i != j) {
        swap(nums,i,j);
      }
      i++;
    }
  }
  swap(nums,i,r);
  return i;
}

//！ 交换函数
void swap(int *nums, int i,int j) {
  int tmp = nums[i];
  nums[i] = nums[j];
  nums[j] = tmp;
}
//希尔排序
int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int step = numsSize/2;
    while (step > 0) {
      //!
      for(int i = step;i<numsSize;++i) {
        int tmp = nums[i];
        int j =  i - step;
        while (j >= 0 && tmp < nums[j]) {
          nums[j+step] = nums[j];
          j -= step;
        }
        nums[j + step] = tmp;
      }
      step = step/2;
    }
    return nums;
}
//基数排序
int* sortArray(int* nums, int numsSize, int* returnSize) {
    int min = INT_MAX, max = INT_MIN;
    *returnSize = numsSize;
    for (int i = 0; i < numsSize; ++i) {
      min = fmin(min,nums[i]);
      max = fmax(max,nums[i]);
    }
    int n = (max-min+1);
    int *countArr = (int *)malloc(n*sizeof(int));
    memset(countArr,0,n*sizeof(int));
   
    for (int i = 0; i < numsSize; ++i) {
      countArr[nums[i]-min] += 1;
    }

    int *res = (int *)malloc(numsSize*sizeof(int));
    int index = 0;

    for (int i = 0; i < n; ++i) {
      if (countArr[i] == 0) {
        continue;
      }
      for(int j = 0; j < countArr[i]; ++j) {
        res[index] = i+min;
        index += 1;
      }
    }

    free(countArr);
    return res;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250

    博客很长，感谢大家的耐心观看🙏🙏🙏🙏🙏🙏

  • 相关阅读:
    Vuex 的用法
    【面试题】2022前端面试真题
    集合（容器）-List接口及实现类
    pytorch指定使用多个GPU
    不同框架实现LSTM代码及转Onnx方法
    ES mapping之keyword；term查询添加keyword查询；更改mapping keyword类型
    Facebook Developer 的 HashCode
    13 - 多线程之锁优化（中）：深入了解Lock同步锁的优化方法
    Dubbo简易搭建
    (matplotlib)如何让各个子图ax大小（宽度和高度）相等
  • 原文地址：https://blog.csdn.net/m0_60338933/article/details/126001430