手撕各种排序

> 作者简介：დ旧言~，目前大一，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：掌握每种排序的方法，理解每种排序利弊和复杂度。

> 毒鸡汤：船停在码头是最安全的，但那不是造船的目的；人呆在家里是最舒服的，但那不是人生的意义。最美好的生活方式，莫过于和一群志同道合的人奔跑在理想的路上！
> 望小伙伴们点赞👍收藏✨加关注哟💕💕 

🌟前言 

        谈起排序这个事情，大家都是耳熟能详的事了，从我们认识的斗地主，每一复牌都是按照从小到大的顺序排序的，如图：

       排序的目的是为了让我们很好的管理，使无序的事情变成有序，当然排序的方法有很多，如由大到小，由大到小.....。而面对大量数据就需要排序。在数据结构中我们发明了多种排序，如我们最早认识的冒泡排序，本篇博客让大家对多种排序有一个很好的认知，闲话少谈。

⭐主体  

咱们就掌握八种就行啦

🌙冒泡排序

这里博主在C语言刷题训练专栏中讲到过冒泡排序，咱们再回顾回顾

这里我们以接口的形式写代码，那咱们上代码咯

//冒泡排序测试
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int exchange = 0;for (int j = 1; j < n - i; j++){if (a[i - 1] > a[i]){//这里是一个交换函数Swap(&a[i - 1], &a[i]);exchange = 1;}}//这里进行一趟有序时，直接跳出循环if (exchange == 0){break;}}
}

注意事项：
💦1.我们知道当给的数据有序时，就不再需要进行循环了，直接跳出循环（exchange作用）。
💦2. 第二个循环中  j < n - i  不能搞错。

时间复杂度：O(N²)

空间复杂度：O(1)

稳定性：稳定

复杂性：简单

🌙直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 ，就好像我们斗地主拿牌插入相似。

咱们看看一个动态的插入动作。

 这里我们以接口的形式写代码，那咱们上代码咯

//插入排序
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];}else{break;}--end;}//最后把插入的元素赋值回去a[end + 1] = tmp;}
}

注意事项：
💦1.我们先进行第end个元素移动，再进行n个元素进行移动。
💦2. 最后需要a[end + 1] = tmp赋值

时间复杂度：O(N²)

空间复杂度：O(1)

稳定性：稳定

复杂性：简单

🌙希尔排序

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

在看看一个动态的图解：

  这里我们以接口的形式写代码，那咱们上代码咯

//希尔排序测试
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//间隔gap的元素进行排序gap = gap / 3 + 1;//本质上是插入排序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 = end - gap;}else{break;}}//最后把插入的元素赋值回去a[end + gap] = tmp;}}
}

注意事项：
💦1.首先先嵌套一个插入排序，再把分组的元素进行交换。
💦2. gap = gap / 3 + 1这个不要忘记。

时间复杂度：O(N¹·²³)

空间复杂度：O(1)

稳定性：不稳定

复杂性：复杂

🌙选择排序

       基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。咱们看看图解：

 

这里我们看一个动态的图解：

 

上代码：

//选择排序测试
void SelectSort(int* a, int n)
{//初始化第一个元素 和 最后一个元素int begin = 0;int end = n - 1;while (begin < end){//选出最大值和最小值int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}//最小值和最初的元素交换Swap(&a[begin], &a[mini]);//如果max被换走就需要重新赋值if (maxi == begin){maxi = mini;}//最大值和最末的元素交换Swap(&a[end], &a[maxi]);++begin;--end;}
}

注意事项：
💦1.这里先找到最小值和最大值，然后交换到最前面和最后面，一次进行。
💦2. 如果最大值被交换后，需要从新赋值。

时间复杂度：O(N²)

空间复杂度：O(1)

稳定性：不稳定

复杂性：简单

🌙堆排序

       堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。咱们看看图解：

再看看动态的图解：

上代码：

//堆排序测试
//实现向下调整建大堆
void AdjustDown(int* a, int n, int parent)
{//孩子和父亲的关系 int child = parent * 2 + 1;while (child < n){//找出小的那个孩子if (child + 1 < n && 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--){//实现向下调整建大堆AdjustDown(a, n, i);}int end = n - 1;while (end > 0){//元素交换Swap(&a[0], &a[end]);//实现向下调整建大堆AdjustDown(a, end, 0);--end;}
}

注意事项：
💦1.首先我们需要建大堆（以在二叉树讲解咯），交换，再建大堆
💦2. 每交换一个元素都需要再建一次大堆。

时间复杂度：O(NlogN)

空间复杂度：O(1)

稳定性：不稳定

复杂性：复杂

🌙快排

        在快排这个板块中我将讲述四个方法，希小伙伴都能掌握。

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

💫Hoare方法

       在动态图中，key称为基准值，默认把基准值定义在数组的首元素上，其次为了加快遍历的速度，需要用到两个变量分别去对应数组的首尾部分，L处在数列的首部，它需要从左往右寻找比Keyi位置的值大的，遇到后就停下来，没遇到就一直走；R处在数列的尾部，它需要从右往左去寻找比keyi位置的值小的，也是遇到后就停下来，没遇到就一直走。

        当L与R都遇到停下来后开始互换位置，然后继续遍历，直到L==R时，双方都不会再走了，因为它们走到了同一个位置，这个位置被称为它俩的相遇点，之后便需要将keyi位置的值与相遇点的值互换位置，这样keyi位置的值就放到了中间，成为了数组的中心——基准值，它意味着将数组分为两个子序列，左序列全是小于Keyi的值，右序列全是大于Keyi的值，这样便可以利用递归，一层一层再对左右两个子序列进行相同的步骤——将一个大的无序序列转化为多个小的序列，从而进行排序，最终排列为完全有序的序列。
 

上代码：

//三数取中 （找出中间值）
int GetMidi(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{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 右边找小，左边找大，交换，把左边的值跟a[keyi]交换
int PartSort1(int* a, int left, int right)
{//找中间值（相对）int midi = GetMidi(a, left, right);//把最左边（相对）跟中间值（相对）换Swap(&a[left], &a[midi]);//定位最左边（相对）int keyi = left;while (left < right){//找小while (left < right && a[right] >= a[keyi]){--right;}//找大while (left < right && a[left] <= a[keyi]){++left;}//左右交换Swap(&a[left], &a[right]);}//此时左边走到中间了，开始交换Swap(&a[keyi], &a[left]);//返回return left;
};

注意事项：
💦1.首先先找到中间值。
💦2.再和最左边元素互换

💦3.左边找比（中间值）大的数，右边找（中间值）小的数，然后左右值交换。

💦4.此时左边走到中间了，开始交换

💦5.上述进行循环，知道排序完成

💫挖坑法

大家就看一下下面图解：

//三数取中 （找出中间值）
int GetMidi(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{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//挖坑法
int PartSort2(int* a, int left, int right)
{//找中间值（相对）int midi = GetMidi(a, left, right);//把最左边（相对）跟中间值（相对）换Swap(&a[left], &a[midi]);//定位最左边（相对）int key = a[left];//保存key值以后，左边形成第一个坑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;
}

💫前后指针

       通过创建两个指针，prev指针指向数组序列首元素位置，cur指向prev的下一个位置，cur通过遍历去寻找比key基准值小的，若找到了，还得看prev的下一个位置是否为cur所处的位置，若prev的下一个位置确实为cur所处位置，则将cur指向的值与prev指向的值进行互换，若prev的下一个位置不是cur所处位置，则cur继续往后遍历，直到cur遍历结束，最后要将key基准值与prev指向的值进行互换，最终确认基准值处于数组序列的中间位置。


//三数取中 （找出中间值）
int GetMidi(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{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}//前后指针
int PartSort3(int* a, int left, int right)
{//找中间值（相对）int midi = GetMidi(a, left, right);//把最左边（相对）跟中间值（相对）换Swap(&a[left], &a[midi]);//定义指针开头int prev = left;//定义指针开头后一个int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}//交换Swap(&a[prev], &a[keyi]);return prev;
}

💫快排非递归

1.初始化我们的栈。

2.入栈把我们的开始的left==0  right==n-1；

3.进入我们的循环体循环体进入的条件是判断栈中是否还有数值如果有数值的化什么其中的数值对应的范围还是没有序的就需要出栈（这个时候就需要进行出栈（注意栈的数值的左右范围的对应））进行我们的挖坑排序（对于挖坑我们应该把key返回出来通过key的数值进行我们再一次的入栈操作同时我们的范围）。

3.1[left   key-1] 和[key+1   right]   这样的范围满足条件才能继续push  之后pop进行我们的排序；

4如果说我们的循环体结束了的话我们的数组就一定有序！

前面已经讲述了栈，这里就不再实现栈了

//快排非递归（采用栈的形式）（先进后出）
void QuickSortNonR(int* a, int begin, int end)
{//定义ST st;//初始化STInit(&st);//添加元素STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){//剥离元素  让left取先入但是后出的元素（区间的左边）int left = STTop(&st);STPop(&st);//让right取栈顶元素（是我们后入的区间的右边）int right = STTop(&st);STPop(&st);// 右边找小，左边找大，交换，把左边的值跟a[keyi]交换int keyi = PartSort1(a, left, right);//分割成段 // [lefy,keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){//添加元素STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1){//添加元素STPush(&st, keyi - 1);STPush(&st, left);}}//销毁STDestroy(&st);
}

🌙归并排序

这里讲述两种方法，一种是递归型另一种则是非递归

💫归并排序递归型

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

void _MergeSort(int* a, int* tmp, int begin, int end)
{//尾小于头时if (end <= begin)return;//开始分割int mid = (end + begin) / 2;// [begin, mid][mid+1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//归并到tmp数据组，再拷贝回去//a->[begin, mid][mid+1, end]->tmpint begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;//开始拷贝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++];}//拷贝回原数组memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//归并排序（分路并归）
void MergeSort(int* a, int n)
{//开辟空间int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//调用_MergeSort(a, tmp, 0, n - 1);//释放内存free(tmp);
}

💫归并排序非递归型

       第一次当 gap 为 1 的时候，我们将距离为 1 的两个数组（其实就是两个元素为 1 的数）进行归并，得到了拥有两个元素的一个有序数组，然后通过循环将后面的元素全部用同样的方式归并。然后就得到了如上图所示蓝色表示的元素排布。同时我们在将这一步骤之后的数组拷贝回到原数组。在进行接下来的操作（这里的意思和上递归的是一样的）。接着每次将 gap 的值增加 2 倍，直到 gap 的值不小于 n 结束归并。这个过程我们将其称为小区间优化。

//归并排序（非递归）
void MergeSortNonR(int* a, int n)
{//开辟空间int* tmp = (int*)malloc(sizeof(int) * n);//判断if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// [begin1,end1] [begin2,end2] 归并// 如果第二组不存在，这一组不用归并了if (begin2 >= n){break;}// 如果第二组的右边界越界，修正一下if (end2 >= n){end2 = n - 1;}//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int index = i;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++];}// 拷贝回原数组memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}printf("\n");gap *= 2;}free(tmp);
}

🌙计数排序

计数排序的朴素方法步骤：

        1、从无序数组中取出最大值max，新建一个长度为max+1的数组。

        2、遍历无序数组，取其中元素作为新建数组的索引，存在一个则新数组该索引所在的值自增。

        3、遍历新数组，当存在不为0的元素，取该元素的索引放入最终数组，并且该元素自减，直到为0，返回最终数组。
 

上代码：

//计数排序测试
void CountSort(int* a, int n)
{//找最大值和最小值int min = a[0], max = a[0];for (size_t i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//找出区间int range = max - min + 1;//开辟（区间）int* count = (int*)malloc(sizeof(int) * range);printf("range:%d\n", range);//判断if (count == NULL){perror("malloc fail");return;}//计入数字的个数memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

 ⭐总结

咱看看每种排序的复杂度和稳定性。

 🌠Sort.h代码


#include<stdio.h>//打印数据
void PrintArray(int* a, int n);//冒泡排序测试
void BubbleSort(int* a, int n);
//插入排序测试
void InsertSort(int* a, int n);
//希尔排序测试
void ShellSort(int* a, int n);
//选择排序测试
void SelectSort(int* a, int n);
//堆排序测试
void HeapSort(int* a, int n);//快排测试
void QuickSort1(int* a, int begin, int end);
void QuickSort2(int* a, int begin, int end);
//快排非递归测试
void QuickSortNonR(int* a, int begin, int end);//归并排序测试
void MergeSort(int* a, int n);
//归并排序（非递归）测试
void MergeSortNonR(int* a, int n);
//计数排序测试
void CountSort(int* a, int n);

🌠Test.c代码

#define _CRT_SECURE_NO_WARNINGS 1#include<time.h>
#include<stdlib.h>
#include"Sort.h"
#include"Stack.h"//希尔排序测试
void TestShellSort()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };ShellSort(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,1,2,3,5,1,8,3 };BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//堆排序测试
void TestHeapSort()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };HeapSort(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,1,2,3,5,1,8,3 };SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//测试代码
void TestOP()
{srand(time(0));const int N = 100000;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 = N - 1; i >= 0; --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];}int begin1 = clock();//插入排序InsertSort(a1, N);int end1 = clock();int begin2 = clock();//希尔排序测试ShellSort(a2, N);int end2 = clock();int begin7 = clock();//冒泡排序测试BubbleSort(a7, N);int end7 = clock();int begin3 = clock();//选择排序测试SelectSort(a3, N);int end3 = clock();int begin4 = clock();//堆排序测试HeapSort(a4, N);int end4 = clock();int begin5 = clock();//快排测试//QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();//MergeSort(a6, N);//计数排序测试//CountSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("BubbleSort:%d\n", end7 - begin7);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("CountSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{TestOP();//TestBubbleSort();//TestHeapSort();//TestSelectSort();//TestQuickSort();//TestMergeSort();//TestCountSort();//printf("%d\n", Func(100000));return 0;
}

 🌠Sort.c代码

#define _CRT_SECURE_NO_WARNINGS 1#include"Sort.h"
#include"Stack.h"//交换函数
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//打印数据
void PrintArray(int* a, int n)
{//循环for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}//冒泡排序测试
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int exchange = 0;for (int j = 1; j < n - i; j++){if (a[i - 1] > a[i]){//这里是一个交换函数Swap(&a[i - 1], &a[i]);exchange = 1;}}//这里进行一趟有序时，直接跳出循环if (exchange == 0){break;}}
}//插入排序
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];}else{break;}--end;}//最后把插入的元素赋值回去a[end + 1] = tmp;}
}//希尔排序测试
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//间隔gap的元素进行排序gap = gap / 3 + 1;//本质上是插入排序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 = end - gap;}else{break;}}//最后把插入的元素赋值回去a[end + gap] = 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;}}	*///选择排序测试
void SelectSort(int* a, int n)
{//初始化第一个元素 和 最后一个元素int begin = 0;int end = n - 1;while (begin < end){//选出最大值和最小值int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}//最小值和最初的元素交换Swap(&a[begin], &a[mini]);//如果max被换走就需要重新赋值if (maxi == begin){maxi = mini;}//最大值和最末的元素交换Swap(&a[end], &a[maxi]);++begin;--end;}
}//堆排序测试
//实现向下调整建大堆
void AdjustDown(int* a, int n, int parent)
{//孩子和父亲的关系 int child = parent * 2 + 1;while (child < n){//找出小的那个孩子if (child + 1 < n && 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--){//实现向下调整建大堆AdjustDown(a, n, i);}int end = n - 1;while (end > 0){//元素交换Swap(&a[0], &a[end]);//实现向下调整建大堆AdjustDown(a, end, 0);--end;}
}//三数取中 （找出中间值）
int GetMidi(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{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}// 右边找小，左边找大，交换，把左边的值跟a[keyi]交换
int PartSort1(int* a, int left, int right)
{//找中间值（相对）int midi = GetMidi(a, left, right);//把最左边（相对）跟中间值（相对）换Swap(&a[left], &a[midi]);//定位最左边（相对）int keyi = left;while (left < right){//找小while (left < right && a[right] >= a[keyi]){--right;}//找大while (left < right && a[left] <= a[keyi]){++left;}//左右交换Swap(&a[left], &a[right]);}//此时左边走到中间了，开始交换Swap(&a[keyi], &a[left]);//返回return left;
};//挖坑法
int PartSort2(int* a, int left, int right)
{//找中间值（相对）int midi = GetMidi(a, left, right);//把最左边（相对）跟中间值（相对）换Swap(&a[left], &a[midi]);//定位最左边（相对）int key = a[left];//保存key值以后，左边形成第一个坑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)
{//找中间值（相对）int midi = GetMidi(a, left, right);//把最左边（相对）跟中间值（相对）换Swap(&a[left], &a[midi]);//定义指针开头int prev = left;//定义指针开头后一个int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}//交换Swap(&a[prev], &a[keyi]);return prev;
}//快排测试一
void QuickSort1(int* a, int begin, int end)
{if (begin >= end)return;//小区间优化，小区间不再递归分割排序，降低递归次数//当元素小于10时，采用插入排序if ((end - begin + 1) > 10){//找值int keyi = PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{//插入排序InsertSort(a + begin, end - begin + 1);}
}//快排测试二
void QuickSort2(int* a, int begin, int end)
{if (begin >= end)return;//调用int keyi = PartSort3(a, begin, end);//[begin, keyi-1] keyi [keyi+1, end]QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);
}//快排非递归（采用栈的形式）（先进后出）
void QuickSortNonR(int* a, int begin, int end)
{//定义ST st;//初始化STInit(&st);//添加元素STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){//剥离元素  让left取先入但是后出的元素（区间的左边）int left = STTop(&st);STPop(&st);//让right取栈顶元素（是我们后入的区间的右边）int right = STTop(&st);STPop(&st);// 右边找小，左边找大，交换，把左边的值跟a[keyi]交换int keyi = PartSort1(a, left, right);//分割成段 // [lefy,keyi-1] keyi [keyi+1, right]if (keyi + 1 < right){//添加元素STPush(&st, right);STPush(&st, keyi + 1);}if (left < keyi - 1){//添加元素STPush(&st, keyi - 1);STPush(&st, left);}}//销毁STDestroy(&st);
}void _MergeSort(int* a, int* tmp, int begin, int end)
{//尾小于头时if (end <= begin)return;//开始分割int mid = (end + begin) / 2;// [begin, mid][mid+1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);//归并到tmp数据组，再拷贝回去//a->[begin, mid][mid+1, end]->tmpint begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int index = begin;//开始拷贝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++];}//拷贝回原数组memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}//归并排序（分路并归）
void MergeSort(int* a, int n)
{//开辟空间int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//调用_MergeSort(a, tmp, 0, n - 1);//释放内存free(tmp);
}//归并排序（非递归）
void MergeSortNonR(int* a, int n)
{//开辟空间int* tmp = (int*)malloc(sizeof(int) * n);//判断if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// [begin1,end1] [begin2,end2] 归并// 如果第二组不存在，这一组不用归并了if (begin2 >= n){break;}// 如果第二组的右边界越界，修正一下if (end2 >= n){end2 = n - 1;}//printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int index = i;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++];}// 拷贝回原数组memcpy(a + i, tmp + i, (end2 - i + 1) * sizeof(int));}printf("\n");gap *= 2;}free(tmp);
}//计数排序测试
void CountSort(int* a, int n)
{//找最大值和最小值int min = a[0], max = a[0];for (size_t i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}//找出区间int range = max - min + 1;//开辟（区间）int* count = (int*)malloc(sizeof(int) * range);printf("range:%d\n", range);//判断if (count == NULL){perror("malloc fail");return;}//计入数字的个数memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

🌟结束语

       今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小说手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/153569.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Tomcat隔离web原理和热加载热部署

Tomcat隔离web原理和热加载热部署

Tomcat 如何打破双亲委派机制 Tomcat 的自定义类加载器 WebAppClassLoader 打破了双亲委派机制&#xff0c;它首先自己尝试去加载某个类&#xff0c;如果找不到再代理给父类加载器&#xff0c;其目的是优先加载 Web 应用自己定义的类。具体实现就是重写 ClassLoader 的两个方法…
阅读更多...
bootstrapjs开发环境搭建

bootstrapjs开发环境搭建

Bootstrapjs是一个web前端页面应用开发框架&#xff0c;其提供功能丰富的JavaScript工具集以及用户界面元素或组件的样式集&#xff0c;本文主要描述bootstrapjs的开发环境搭建。 如上所示&#xff0c;使用nodejs运行时环境、使用npm包管理工具、使用npm初始化一个项目工程test…
阅读更多...
红队专题-Cobalt strike4.5二次开发

红队专题-Cobalt strike4.5二次开发

红队专题 招募六边形战士队员IDEA 自动换行原版CS反编译破解jar包反编译拔掉暗桩初始环境效果 stageless beacon http通信协议 过程分析上线&心跳get请求teamserver 处理请求 参考链接 招募六边形战士队员 一起学习 代码审计、安全开发、web攻防、逆向等。。。 私信联系 …
阅读更多...
MES系统安灯管理：实时可视化生产线状态

MES系统安灯管理：实时可视化生产线状态

一、MES系统安灯管理的意义&#xff1a; 安灯管理是指通过使用不同颜色的灯光信号来表示生产线的状态&#xff0c;以便生产人员能够直观地了解生产线的运行情况。MES系统安灯管理的意义在于提供一个实时可视化的工具&#xff0c;使制造企业能够及时发现生产线异常和潜在问题&a…
阅读更多...
UE5中实现沿样条线创建网格体2-SplineMesh版本

UE5中实现沿样条线创建网格体2-SplineMesh版本

我在之前的一篇文章中写过沿样条线创建网格体的方法&#xff1a; https://blog.csdn.net/grayrail/article/details/130453733 但该方法没有网格变形操作&#xff0c;就会导致每一段网格对象是无法连接的&#xff1a; 后来发现了SplineMesh方法可以比较好的解决这个问题&…
阅读更多...
【K8S系列】深入解析k8s 网络插件—kube-router

【K8S系列】深入解析k8s 网络插件—kube-router

序言 做一件事并不难&#xff0c;难的是在于坚持。坚持一下也不难&#xff0c;难的是坚持到底。 文章标记颜色说明&#xff1a; 黄色&#xff1a;重要标题红色&#xff1a;用来标记结论绿色&#xff1a;用来标记论点蓝色&#xff1a;用来标记论点 在现代容器化应用程序的世界中…
阅读更多...
横向AlGaN/GaN基SBD结构及物理模型数据库的开发

横向AlGaN/GaN基SBD结构及物理模型数据库的开发

GaN基功率器件凭借其临界电场高、电子饱和漂移速度大、热导率高等优良性能在大功率快充、充电桩、新能源汽车等领域具备广泛应用空间。为进一步助推半导体高频、高功率微电子器件的发展进程&#xff0c;天津赛米卡尔科技有限公司技术团队依托先进的半导体TCAD仿真平台成功开发出…
阅读更多...
【WebService】C#搭建的标准WebService接口，在使ESB模版作为参数无法获取参数数据

【WebService】C#搭建的标准WebService接口，在使ESB模版作为参数无法获取参数数据

一、问题说明 1.1 问题描述 使用C# 搭建WebService接口&#xff0c;并按照ESB平台人员的要求&#xff0c;将命名空间改为"http://esb.webservice",使用PostmanESB平台人员提供的入参示例进行测试时&#xff0c;callBussiness接口参数message始终为null。 以下是ES…
阅读更多...
如何采集淘宝数据？淘宝采集是什么意思？

如何采集淘宝数据？淘宝采集是什么意思？

对于淘宝商家和数据分析者来说&#xff0c;获取淘宝数据是关键之一。本文将深入探讨如何采集淘宝数据&#xff0c;包括采集的含义、方法和相关注意事项。 一、淘宝采集是什么意思 淘宝采集是指通过各种技术手段和工具&#xff0c;从淘宝平台上抓取、提取或获取数据的过程。这…
阅读更多...
LLMs 生成式人工智能项目生命周期备忘单Generative AI Project Lifecycle Cheat Sheet

LLMs 生成式人工智能项目生命周期备忘单Generative AI Project Lifecycle Cheat Sheet

到目前为止&#xff0c;在本课程中&#xff0c;从选择模型到微调模型&#xff0c;再到将其与人类偏好对齐&#xff0c;这一切都将在您部署应用程序之前发生。为了帮助您规划生成式AI项目生命周期的各个阶段&#xff0c;这个速查表提供了每个工作阶段所需的时间和精力的一些指示…
阅读更多...
SonarQube学习笔记三：直接使用sonar-scanner扫描器

SonarQube学习笔记三：直接使用sonar-scanner扫描器

目录 1.安装Sanner扫描器2.环境变量配置3.创建项目3.1 登录并创建项目3.2 输入项目名称信息3.3 选择分析仓库类型3.4 创建令牌3.5 保存令牌&#xff08;非必须&#xff09;3.6 选择构建技术方案3.6.1 .Net类项目3.6.2 Java类项目 3.7 获取Sonar检查结果3.8 在页面查看检查结果或…
阅读更多...
计算机网络——计算机网络的性能指标（下）-时延带宽积、往返时间、利用率、丢包率

计算机网络——计算机网络的性能指标（下）-时延带宽积、往返时间、利用率、丢包率

目录 时延带宽积 往返时间 利用率 丢包率 时延带宽积 时延带宽积等于传播时延乘带宽。假设时延带宽积是一个圆柱体&#xff0c;那么传播时延就是圆柱体的长&#xff0c;带宽就是圆柱体的圆面面积。 若发送端连续发送数据&#xff0c;则在所发送的第一个比特即将到达终点时&…
阅读更多...
回归算法全解析！一文读懂机器学习中的回归模型

回归算法全解析！一文读懂机器学习中的回归模型

目录 一、引言回归问题的重要性文章目的和结构概览 二、回归基础什么是回归问题例子&#xff1a; 回归与分类的区别例子&#xff1a; 回归问题的应用场景例子&#xff1a; 三、常见回归算法3.1 线性回归数学原理代码实现输出例子&#xff1a; 3.2 多项式回归数学原理代码实现输…
阅读更多...
【JavaEE】文件操作

【JavaEE】文件操作

文章目录 前言什么是文件树型结构组织和目录文件路径文件类型文件权限Java中的文件操作File 类的常见属性File 类常见构造方法File 类常用方法 前言 文件是我们日常生活中使用非常广泛的&#xff0c;我们使用任何一个程序都离不开文件操作&#xff0c;这个文件不仅仅指平时可以…
阅读更多...
Pyside6 安装和简单界面开发

Pyside6 安装和简单界面开发

Pyside6 安装和简单界面开发 Pyside6介绍Pysied6开发环境搭建Python安装Pysied6安装 Pyside6界面开发简单界面设计界面设计界面编译 编写界面初始化代码软件打包 Pyside6介绍 对于Python的GUI开发来说&#xff0c;Python自带的可视化编程模块的功能较弱&#xff0c;PySide是跨…
阅读更多...
关于Go语言的底层，Channel

关于Go语言的底层，Channel

1.Channel 介绍一下Channel&#xff08;有缓冲和无缓冲&#xff09; Go 语言中&#xff0c;不要通过共享内存来通信&#xff0c;而要通过通信来实现内存共享。Go 的CSP(Communicating Sequential Process)并发模型&#xff0c;中文可以叫做通信顺序进程&#xff0c;是通过 gor…
阅读更多...
Node.js 做 Web 后端的优势在哪？为什么是明智的选择？

Node.js 做 Web 后端的优势在哪？为什么是明智的选择？

当我们谈论构建强大的Web应用程序时&#xff0c;选择适当的后端技术至关重要。在如今的技术领域中&#xff0c;Node.js已经崭露头角&#xff0c;并且越来越多的开发者和企业选择将其作为首选的后端开发工具。但是&#xff0c;Node.js究竟有哪些优势&#xff0c;使得它成为众多开…
阅读更多...
SpringBoot整合POI实现Excel文件读写操作

SpringBoot整合POI实现Excel文件读写操作

1.环境准备 1、导入sql脚本&#xff1a; create database if not exists springboot default charset utf8mb4;use springboot;create table if not exists user (id bigint(20) primary key auto_increment comment 主键id,username varchar(255) not null comment 用…
阅读更多...
NSSCTF做题（7）

NSSCTF做题（7）

[第五空间 2021]pklovecloud 反序列化 <?php include flag.php; class pkshow { function echo_name() { return "Pk very safe^.^"; } } class acp { protected $cinder; public $neutron; …
阅读更多...
《要么孤独 要么庸俗》 笔记

《要么孤独 要么庸俗》 笔记

人往往比自己想象的更愚蠢 我的生存原则或意志行事原则是什么&#xff1f;尝试考察自己的生命年轮 一个明智的人不会被表面稳定现象欺骗&#xff0c;还能预测事物发展趋向 由于只能理解结果而不是原因&#xff0c;会错误的认为结果会一直持续下去 很多事情需要时间来兑现&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023