数据结构排序小结

排序类型小结

  • 💦 插入排序
    • 直接插入排序
    • 希尔排序
  • 💦 选择排序
    • 直接选择排序
    • 堆排序
  • 💦 交换排序
    • 冒泡排序
    • 快速排序🐾
      • ==霍尔版本==
      • ==补坑位版本==
      • ==前后指针版本==
      • ==非递归版本==
  • 💦 归并排序
      • ==递归版本==
      • ==非递归版本==
  • 💦 性能测试

💦 插入排序

直接插入排序

🔑 核心思想 🔑
请添加图片描述

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

❗ 过程:❕

当插入第 i(i>=1) 个元素时,前面的 array[0], array[1], … , array[i-1] 已经排好序,此时用 array[i] 的排序码与 array[i-1], array[i-2],… 的排序码顺序进行比较,找到插入位置即将 array[i] 插入,原来位置上的元素顺序后移

❗ 直接插入排序的特性总结:❕

1️⃣ 元素集合越接近有序,直接插入排序算法的时间效率越高

2️⃣ 时间复杂度:O(N^2)

3️⃣ 空间复杂度:O(1),它是一种稳定的排序算法

4️⃣ 稳定性:稳定
  
🐾代码实现:

void InsertSort(int* a, int n)
{//注意这里的n-1for (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;}
}

希尔排序

希尔排序 (缩小增量排序)

🔑 核心思想 🔑

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

在这里插入图片描述

🤖希尔排序的时间复杂度并不好计算,因为 gap 的取值方法很多,导致很难去计算,因此在好些数中给出的希尔排序的时间复杂度都不固定,官方给出的时间复杂度是 O(N1.3)

以下是其粗略的计算方法,可见非常复杂

在这里插入图片描述
🐾代码实现

//希尔排序
void ShellSort(int* a, int n)
{int gap = n;//gap>1时是预排,目的是让他接近有序//gap==1是直接插入排序,目的是让他有序while (gap > 1){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 -= gap;}elsebreak;}a[end + gap] = tmp;}}
}

❗ 希尔排序特性总结 ❕

1️⃣ 希尔排序是对直接插入排序的优化

2️⃣ 当 gap > 1 时都是预排序,目的是让数组更接近于有序。当 gap == 1 时,其实就是直接插入排序,且数组已经接近有序的了。整体而言,可以达到优化的效果,我们实现后可以进行性能测试的对比

3️⃣ 希尔排序的时间复杂度并不好计算,因为 gap 的取值方法很多,导致很难去计算,因此在好些数中给出的希尔排序的时间复杂度都不固定,官方给出的时间复杂度是 O(N1.3)

4️⃣ 稳定性:不稳定

💦 选择排序

直接选择排序

🔑 核心思想 🔑

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

❗ 过程:❕

1️⃣ 在元素集合 array[i] - array[n-1] 中选择关键码最大 (小) 的数据元素

2️⃣ 若它不是这组元素中的最后一个(或第一个)元素,则将它与这组元素中的最后一个(或第一个)元素交换

3️⃣ 在剩余的 array[i] - array[n-2] (array[i+1]–array[n-1]) 集合中,重复上述步骤,直到集合剩余 1 个元素

❗ 直接选择排序的特性总结:❕

1️⃣ 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用

2️⃣ 时间复杂度:O(N^2) - 最好 / 最坏都是如此,当数据极其无序时,比冒泡排序还要拉跨

3️⃣ 空间复杂度:O(1)

4️⃣ 稳定性:不稳定

❗ 动图演示:❕
请添加图片描述
🐾代码实现


//与上述动图一样的代码
void Swap(int* px, int* py)
{int temp = *px;*px = *py;*py = temp;
}
void SelectSort(int* a, int n)
{int i = 0;int begin = 0;while (begin < n){int mini = begin;//选最小for (i = begin; i < n; i++){if (a[i] < a[mini]){mini = i;}}//交换Swap(&a[begin], &a[mini]);//迭代begin++;}
}//优化版本,最大值最小值同时找
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){//一趟排序,将最大数最小数的下标都初始化成beginint 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的mini的交换使得max的值丢失//当maxi==begin时,maxi指向min,下一次交换就会出问题!!!if (maxi == begin){maxi = mini;}Swap(&a[end], &a[maxi]);//迭代++begin;--end;}
}

堆排序

🔑 核心思想 🔑

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

❗ 堆排序的特性总结:❕

1 堆排序使用堆来选数,效率就高了很多。

2. 时间复杂度:O(N*logN)

3.空间复杂度:O(1)

4.稳定性:不稳定

void Swap(int* px, int* py)
{int temp = *px;*px = *py;*py = temp;
}
//向上调整算法
void AdjustUp(int*a,int child)
{int parent=(child-1)/2;while(child > 0){//这里的符号决定调整为大堆还是小堆,这里以大堆为例if(a[child]>a[parent]){Swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}else{break;}}
}
//向下调整算法
void AdjustDown(int* a, int size, int parent)
{int child = parent * 2 + 1;while (child < size){//假设左孩子小,如果假设错了,更新一下//这样操作后,child指向的就是两个孩子中较小的那一个if (a[child+1] < a[child] && child + 1 < size){  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=0;i<n;i++){AdjustUp(a,i); }int end=n-1;while(end>0){//交换后最大的数就排好了Swap(&a[0],&a[end]);//将前面的数再调整,选出次小的数AdjustDown(a,end,0);end--;}
}

方法二:用向下调整算法建堆

void Swap(int* px, int* py)
{int temp = *px;*px = *py;*py = temp;
}//排升序
void HeapSort(int* a, int n)
{//建大堆int i = 0;//n-1就是最后一个元素下标,再-1,除以二就是其父节点,也就是倒数第一个非叶子节点//从这开始从下往上向下建堆for (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--;}
}
  • 倒着调整叶子节点不需要处理(因为叶子节点没有子节点无法向下比较),从倒数第一个非叶子节点开始,即最后一个节点的父节点开始调整,从下往上向下建堆。

  • 在HeapSort函数中,第一个循环调用了AdjustDown函数,将待排序数组构建成了一个大堆。但是,这个大堆并不是完全有序的,只是满足了大堆的性质,即每个节点的值都大于或等于其左右子节点的值。因此,需要进行第二个while循环,将大堆根中的元素依次取出,交换堆顶元素和数组末尾元素,并重新调整大堆,直到整个数组有序。

  • 第二个while循环中,将堆顶元素与数组末尾元素交换,然后将剩余元素重新调整为大根堆。这样,每次交换后,数组末尾的元素就是当前大根堆中的最大值,而剩余元素仍然满足大根堆的性质。重复以上步骤,直到整个数组有序。

💦 交换排序

冒泡排序

请添加图片描述

// 时间复杂度:O(N^2)
// 最好情况是多少:O(N)
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){//定义exchange可以优化冒泡排序,当数据已经有序时,可以提前结束排序bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}

快速排序🐾

🔑 核心思想 🔑

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

❗ 过程:❕

霍尔版本

请添加图片描述

1️⃣ 选出一个关键字 key,一般是头或者尾

2️⃣ 经过一次单趟后,key 放到了正确的位置,key 左边的值比 key 小,key 右边的值比 key 大

3️⃣ 再让 key 的左边区间有序、key 的右边区间有序

为什么相遇的位置的数不会比key大呢?
因为右边先走🐳🐳🐳🐳!!!
我们来分析一波,首先要明确R的任务是找小数,L的任务是找大数,相遇无非就分两种情况
1.R遇到L:这种情况下又分两种
第一种情况:L指向begin开始的位置,压根没动,这样当R走来是相遇于key这个位置,二者相等并不影响排序结果
第二种情况:R成功找到一个比key小的数,L也成功找到一个比key大的数,按照快排规则,此时L和R指向的数应该交换了,那么在交换后,L位置的数就比key要小了(这个过程可能不止一趟),最终R会与L相遇在L位置,这个位置的数必定是比key要小的
2.L遇到R:因为刚开始是R先走的,那么R停下一定是遇到了比key要小的数,(这个过程也可能不止一次)然后L开始向右走,与R在R位置相遇,这个位置的值一定是比key要小的

//简易版本
QuickSort(int* a,int begin,int end)
{if(begin>=end)return;//注意left的起始位置,如果这里left=begin+1,当数组有序时会出Bugint keyi=begin,left=begin,right=end;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[left],&a[keyi]);//更新下一次递归时区间边界keyi=left;//与二叉树的先序遍历有异曲同工之妙QuickSort(a,begin,keyi-1);QuickSort(a,keyi+1,end);
}

在这里插入图片描述

上述代码每次递归都将keyi的值给成begin左边,在最坏情况下,时间复杂度会成为O(N^2),并且调用函数次数与数据个数密切相关,当待排序的数组数据过多时会出现栈溢出,导致被覆盖的内存区域中的数据损坏,从而导致程序崩溃或运行不正常。

要想优化上述情况,就要使得每次选取的key尽量在中间,我们可以选begin,end,midi三个下表对应数组中的值的中位数,用GetMidi函数分装,返回中间值的下标,然后在主函数中交换a[begin]和a[midi]的值,这样操作后a[begin]的值在整个数组中处于更居中的位置,再递归子区间就会缩短递归的区间长度和次数,大大优化代码。

//优化代码
//三数取中函数
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin end midi三个数选中位数if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else//a[begin] > a[midi]{if (a[midi] > a[end])return midi;else if (a[begin] > a[end])return end;elsereturn begin;}
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;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[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

对于优化后的代码,还存在小区间占用过多栈空间的问题,如下图,假定在理想递归情况下,我们每次寻找的key都排到了数组中间,那么递归的函数栈空间展开就是一颗二叉树,当我们递归到二叉树后三层之后,开辟的栈空间居然占了整棵树的87.5%!!
然而后三层需要排的数据个数并不多,根本不需要浪费这么多空间,我们可以针对后三层单独采用插入排序进行再优化。
在这里插入图片描述

//对小区间处理的插入排序函数
void InsertSort(int* a, int n)
{//注意这里的n-1for (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;}
}
//找中位数函数
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin end midi三个数选中位数if (a[begin] < a[midi]){if (a[midi] < a[end])return midi;else if (a[begin] > a[end])return begin;elsereturn end;}else//a[begin] > a[midi]{if (a[midi] > a[end])return midi;else if (a[begin] > a[end])return end;elsereturn begin;}
}
//快排函数
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;//end-begin+1是数据个数,规定其小于10时采用插入排序if(end-begin+1<10)//注意这里的递归起始区间位置是a+beginInsertSort(a+begin,end-begin+1);else{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;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[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}
  • 下图是测试优化小区间后的快排效果,数字代表跑完程序所用的毫秒数,测试方法文末附有,我们对由10万个随机数构成的数组进行排序,为了使得对比更明显,我们在debug(调试版本)下进行对比,debug下,每个函数栈帧添加了许多调试信息,占用的空间更大,小区间优化的效果更加明显。而release(发布版本)对调试信息进行了优化,函数栈帧过多影响不大,多敲的代码可能还会降低排序速度,起到适得其反的效果。

在这里插入图片描述
可以看到效果是有的,但是不是非常明显,想要大幅度改进,还需要从思想上改变的新的方法

为了方便和后续新的方法对比,我们把霍尔版本的单趟排序抽离出来,定义为PartSort1函数

int PartSort1(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int left = begin, right = end;int keyi = begin;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[left], &a[keyi]);return left;
}
//函数 PartSort1 返回了 left 指针指向的值
//这个值表示基准值在分区后的位置。在快速排序算法中,
//这个值会被用来确定下一次分区的区间范围。
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;//end-begin+1是数据个数,规定其小于10时采用插入排序if(end-begin+1<10)//注意这里的递归起始区间位置是a+beginInsertSort(a+begin,end-begin+1);else{int keyi=PartSort1(a,begin,end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

补坑位版本

动图展示💦
请添加图片描述

注意,不同方法的快速排序第一趟排序的结果可能不同
在这里插入图片描述

//补坑位版本
int PartSort2(int* a,int begin,int end)
{int midi=GetMidi(a, begin, end);Swap(&a[midi],&a[begin]);int key=a[begin];int hole=begin;while(begin<end){//右边找小,找到后填到左边坑位while(begin<end && key>=a[end]){end--;}  a[hole]=a[end];hole=end;//左边找大,找到后填到右边坑位while(begin<end&&key<=a[begin]){begin++;}a[hole]=a[begin];hole=begin;}a[hole]=key;return hole;
}

前后指针版本

请添加图片描述
第一趟交换后的结果
在这里插入图片描述

  • 最开始prev和cur相邻的
  • 当cur遇到比key小的值,++perv,交换prev和cur位置的值
  • 当cur遇到比key的大的值以后,++cur
  • prev和cur之间的值都是比key大的值,prev之前的包括交换后prev上的值都比key小
  • 相当于把大的翻滚式往右边推,同时把小的换到左边
int PartSort3(int*a,int begin,int end)
{int midi=GetMidi(a,begin,end);Swap(&a[begin],&a[midi]);int prev=begin;int cur=prev+1;int key=a[begin];while(cur<=end){if(key<=a[cur]){cur++;}else{prev++;Swap(&a[prev],&a[cur]); cur++;}}Swap(&a[prev],&key);return prev;
}

ok了这个测试后也没啥问题
在这里插入图片描述
在这里插入图片描述

int PartSort3(int* a, int begin, int end)
{int midi = GetMidi(a, begin, end);Swap(&a[midi], &a[begin]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){//循环内部其实还可以进一步简化代码if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

非递归版本

通常我们将递归代码改为非递归有两种方式

  • 写成循环版本
  • 借助数据结构----栈

如果想将快排仅仅利用循环是不现实的,因为递归的子区间左右区间不好控制,这里我们需要借助栈的结构

1️⃣将begin和end压入栈中,利用单趟快排找到keyi并且pop掉这两个元素
2️⃣将由keyi分出的子区间压入栈中,并且让每次将出栈的左右区间的子区间进栈
3️⃣循环多次
4️⃣当分出的子区间左区间大于等于右区间不需要入栈在这里插入图片描述
在这里插入图片描述

void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);//第一次入栈要将整个数组的左右区间进栈STPush(&s, end);STPush(&s, begin);while(!STEmpty(&s)){//记录左右区间后出栈int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);//利用存好的左右区间进行一趟快排,找到keyiint keyi = PartSort3(a, left, right);// [left, keyi-1] keyi [keyi+1, right]//当子区间合法时,继续入栈if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi+1);}}STDestroy(&s);
}

💦 归并排序

基本思想: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

动图展示
请添加图片描述

在这里插入图片描述

递归版本

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);// [begin, mid][mid+1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;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++];}//将tmp数组中的值拷贝回去memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

小结

  • 主函数接受两个参数,一个整数数组a和一个整数n,n 表示数组的长度。

  • MergeSort 函数首先为tmp数组开辟待空间。

  • 调用_MergeSort函数进行排序。

  • 释放tmp的空间。

  • 在子函数中,首先计算中间位置mid,并递归地对数组的两部分进行排序。这是分治的思想,将大问题分解成小问题,使用四个指针begin1和begin2、end1和end2,分别指向两个部分的开始位置和结束位置,

  • 然后看三个while循环的比较插入过程,每次分割后两部分分别从头开始比较,把较小的插入tmp数组,某一部分的数全部插入数组后,结束第一个while循环。继续检查哪个数组还有剩余元素,剩下的都是较大的,直接插入tmp数组中。

  • 接下来,我们需要从最小的子序列到最大依次往上进行排序插入,所以这里引用递归的思想完成排序:

  • 在函数_MergeSort中,首先判断begin是否等于end,如果相等,则当前子序列只有一个元素,不需要排序,直接返回。

  • 如果不相等,则计算中间位置mid,然后递归调用_MergeSort函数对左半部分和右半部分进行排序。在排序完成后,将左半部分和右半部分合并成一个有序数组tmp。

  • 每层递归排序后,使用memcpy函数将临时数组tmp中的元素复制回原数组a中。

非递归版本

  • 归并排序不适合用栈来改造,归并排序类似于树的后序遍历,在返回时还需要合并这样的复杂操作,栈模拟递归是不能实现的,对比之前的快速排序的非递归版本,快速排序是前序遍历,即使返回时不做任何操作也可以达到排序目的。
  • 我们可以先将gap初始化为1,然后每次将gap乘以2,直到gap大于等于数组的长度为止。在每次循环中,我们将数组分成若干个大小为gap的子数组,然后对每个子数组进行排序和合并。这样,我们就可以通过循环来实现归并排序,而不需要使用递归。在这里插入图片描述
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}//通过gap控制归并的子数组大小实现非递归的归并排序int gap = 1;while (gap < n){printf("gap:%2d->", gap);for (size_t i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// 边界的处理if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//开始归并int j = begin1;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);
}

在这里插入图片描述
在这里插入图片描述

💦 性能测试

void TestInsertSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };InsertSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestBubbleSort()
{int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestShellSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };int a[] = { 13, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestSelectSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };int a[] = { 13, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1};SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestHeapSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };int a[] = { 13, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestQuickSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };//int a[] = {6,1,2,7,9,3,4,5,10,8};int a[] = { 6,1,2,6,7,9,3,4,6,10,8 };PrintArray(a, sizeof(a) / sizeof(int));//QuickSort(a, 0, sizeof(a) / sizeof(int)-1);QuickSortNonR(a, 0, sizeof(a) / sizeof(int) - 1);PrintArray(a, sizeof(a) / sizeof(int));
}void TestMergeSort()
{//int a[] = { 3, 2, 6, 8, 4, 6, 0, 9, 5, 7, 1 };//int a[] = {6,1,2,7,9,3,4,5,10,8};//int a[] = { 6,1,2,6,7,9,3,4,6,10,8 };int a[] = { 10,8,7,1,3,9,4,2,9,10,1,1,2,3};PrintArray(a, sizeof(a) / sizeof(int));MergeSortNonR(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestCountSort()
{int a[] = {1,3,9,1,5,1,2,3,-5,-5,-2 };PrintArray(a, sizeof(a) / sizeof(int));CountSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 10000000;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);int* a8 = (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];a8[i] = a1[i];}int begin1 = clock();//InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = 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);int end6 = clock();int begin7 = clock();//BubbleSort(a7, N);int end7 = clock();int begin8 = clock();CountSort(a8, N);int end8 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);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("BubbleSort:%d\n", end7 - begin7);printf("CountSort:%d\n", end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}int main()
{//TestInsertSort();//TestBubbleSort();//TestShellSort();//TestSelectSort();//TestHeapSort();//TestQuickSort();//TestMergeSort();//TestCountSort();TestOP();return 0;
}

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

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

相关文章

DDPM的一点笔记

1 Title Denoising Diffusion Probabilistic Models&#xff08;Jonathan Ho、Ajay Jain、Pieter Abbeel&#xff09; 2 Conclusion This paper present high quality image synthesis results using diffusion probabilistic models, a class of latent variable models insp…

利用nginx宝塔免费防火墙实现禁止国外IP访问网站

本章教程&#xff0c;主要介绍&#xff0c;如何利用nginx宝塔面板中的插件免费防火墙&#xff0c;实现一键禁止国外IP访问网站。 目录 一、安装宝塔插件 二、 开启防火墙 一、安装宝塔插件 在宝塔面板中的软件商店&#xff0c;搜索防火墙关键词&#xff0c;找到Nginx免费防火…

java日志框架总结(三 、Log4j日志框架)

一、简介 Log4j ( Logger For Java ) , Java 日志的记录包。 官方网站 。Log4j 是 Apache 的一个开源项目&#xff0c; 为Java提供了日志记录功能。能够让程序员非常方便的记录日志&#xff0c; 并且提供了多种适配方式&#xff0c;能满足各种需求。 使用Log4j 只需要导入一个…

第四篇:怎么写express的路由(接口+请求)

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 &#x1f4d8; 引言&#xff1a; &#x1f4…

python在线聊天室(带聊天保存)

python Socket在线聊天室(带聊天保存) 需求功能 1.聊天信息保存功能(服务端会把信息保存到一个txt里面) 2.使用pyqt5框架作为一个可视化界面 3.具备一个服务端和多个客户端的功能 4.具备离线加入黑名单(离线踢出) 5.具备在线加入黑名单(在线加入黑名单被踢出) 6.具备群聊功能…

无际线复选框

效果演示 实现了一个网格布局&#xff0c;其中每个网格是一个复选框&#xff0c;可以选择是否显示。每个复选框都有一个漂浮的天花板&#xff0c;表示它是一个房间的天花板。每个房间的天花板都有一个不同的形状和颜色&#xff0c;分别对应不同的房间。整个页面的背景是一个由两…

0127-2-Vue深入学习5—Vue-Router路由模式

1、Vue-Router三种路由模式&#xff1a; hash&#xff1a;#️⃣使用URL hash 值来做路由&#xff0c;支持所有路由器&#xff1b;history:&#x1f4d6;依赖HTML5 History API和服务器配置&#xff1b;abstract:⛓支持所有JS运行环境&#xff0c;Node.js服务端&#xff1b; 1.1…

安全防御{第三次作业(在第二次作业上添加点需求)}

目录 需求&#xff1a; 拓扑图&#xff1a; 注意&#xff1a;先打开防火墙web界面&#xff0c;在此不做演示 1.要求一&#xff1a;&#xff0c;生产区在工作时间内可以访问服务器区&#xff0c;仅可以访问http服务器 2.要求二&#xff1a;办公区全天可以访问服务器区&#…

使用一个定时器(timer_fd)管理多个定时事件

使用一个定时器(timer_fd)管理多个定时事件 使用 timerfd_xxx 系列函数可以很方便的与 select、poll、epoll 等IO复用函数相结合&#xff0c;实现基于事件的定时器功能。大体上有两种实现思路&#xff1a; 为每个定时事件创建一个 timer_fd&#xff0c;绑定对应的定时回调函数…

考研C语言刷题基础篇之分支循环结构基础(二)

目录 第一题分数求和 第二题&#xff1a;求10 个整数中最大值 第三题&#xff1a;在屏幕上输出9*9乘法口诀表 第四题&#xff1a;写一个代码&#xff1a;打印100~200之间的素数 第五题&#xff1a;求斐波那契数的第N个数 斐波那契数的概念&#xff1a;前两个数相加等于第三…

Objective-C方法的声明实现及调用

1.无参数的方法 1)声明 a.位置&#xff1a;在interface括弧的外面 b.语法&#xff1a; - (返回值类型)方法名称; interface Person : NSObject -(void) run; end 2)实现 a.位置&#xff1a;在implementation中实现 b.语法&#xff1a;加大括弧将方法实现的代码写在大括孤之中 …

Unity Mask合批情况验证

1.首先是两个Mask完全重合的情况下 每张图片使用的image都来自同一个图集 发现彼此之间是没有合批的&#xff0c;但是每个Mask内部是实现了合批的 经过计算此种情况的visiableList&#xff1a;mask1&#xff0c;IM1&#xff0c;IM2&#xff0c;mask2&#xff0c;IM3&#xf…

NoSQL基本内容

第一章 NoSQL 1.1 什么是NoSQL NoSQL&#xff08;Not Only SQL&#xff09;即不仅仅是SQL&#xff0c;泛指非关系型的数据库&#xff0c;它可以作为关系型数据库的良好补充。随着互联网web2.0网站的兴起&#xff0c;非关系型的数据库现在成了一个极其热门的新领域&#xff0c;…

c# cad2016选择封闭多段线获取多段线面积

在C#中&#xff0c;如果你想要通过AutoCAD .NET API来选择封闭多段线内部的其他闭合多段线并计算它们各自的面积&#xff0c;可以遵循以下基本步骤&#xff1a; 1、加载AutoCAD库&#xff1a; 确保你的C#项目引用了Autodesk.AutoCAD.Interop和Autodesk.AutoCAD.Interop.Common…

Jmeter连接数据库报错Cannot load JDBC driver class‘com.mysql.jdbc.Driver’解决

问题产生: 我在用jmeter连接数据库查询我的接口是否添加数据成功时,结果树响应Cannot load JDBC driver class com.mysql.jdbc.Driver 产生原因: 1、连接数据库的用户密码等信息使用的变量我放在了下面,导致没有取到用户名密码IP等信息,导致连接失败 2、jmeter没有JDB…

《动手学深度学习(PyTorch版)》笔记4.7

Chapter4 Multilayer Perceptron 4.7 Forward/Backward Propagation and Computational Graphs 本节将通过一些基本的数学和计算图&#xff0c;深入探讨反向传播的细节。首先&#xff0c;我们将重点放在带权重衰减&#xff08; L 2 L_2 L2​正则化&#xff09;的单隐藏层多层…

opencv#33 边缘检测

边缘检测原理 图像的每一行每一列都可以看成是一个连续的信号经过离散后得到的数值&#xff0c;例如上图左侧给出的图像由黑色到白色的一个信号&#xff0c;也就是图像中某一行像素变化是由黑色逐渐到白色&#xff0c;我们将其对应在一个坐标轴中&#xff0c;将像素值的大小对应…

【Java基础】聊聊你不知道反射的那些事

在编程语言中&#xff0c;反射是一个绕不过的一个话题&#xff0c;反射、注解、动态代理是支撑框架运行的核心技术。 在Spring中&#xff0c;IOC利用反射实现&#xff0c;创建对象。AOP利用动态代理实现&#xff0c;实现切面编程&#xff0c;配置利用注解实现。所以继上一篇&am…

代码随想录算法训练营第32天 | 122.买卖股票的最佳时机II 55.跳跃游戏 45.跳跃游戏II

买卖股票的最佳时机II 贪心思路 要想使用贪心算法解决此问题&#xff0c;意识到利润是可分解的很关键。比如[1,2,3,4,5]这个输入&#xff0c;最大利润为第一天买入&#xff0c;第五天卖出。这等效于第一天买入&#xff0c;第二天卖出&#xff0c;第二天再买入。。。 prices[4]…

HCS-华为云Stack-FusionSphere

HCS-华为云Stack-FusionSphere FusionSphere是华为面向多行业客户推出的云操作系统解决方案。 FusionSphere基于开放的OpenStack架构&#xff0c;并针对企业云计算数据中心场景进行设计和优化&#xff0c;提供了强大的虚拟化功能和资源池管理能力、丰富的云基础服务组件和工具…