决战排序之巅(一)

2023-12-07 15:30
文章标签 排序 之巅 决战

本文主要是介绍决战排序之巅(一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

决战排序之巅

    • 插入排序
      • 直接插入排序 void InsertSort(int* arr, int n)
      • 希尔排序 void ShellSort(int* arr, int n)
      • 测试插入排序
        • 测试函数 void verify(int* arr, int n)
        • 测试 InsertSort
        • 测试 ShellSort
        • 测试速度 InsertSort & ShellSort
    • 选择排序
      • 直接选择排序 void SelectSort(int* arr,int n)
      • 堆排序 void HeapSort(int* arr,int n)
        • 堆向下调整 void HeapDown(int* arr, int father,int size)
        • 堆排序 void HeapSort(int* arr,int n)
      • 测试选择排序
        • 测试 SelectSort
        • 测试 HeapSort
        • 测试速度 SelectSort & HeapSort
    • 希尔 VS 堆排 (Debug版本)
      • 说明
      • 1w rand( ) 数据测试
      • 10w rand( ) 数据测试
      • 10w rand( ) + i 数据测试
      • 100w rand( ) 数据测试
      • 100w rand( ) + i 数据测试
      • 1000w rand( ) 数据测试
      • 1000w rand( ) + i 数据测试
      • 测试代码如下:
    • 结语

欢迎来到决战排序之巅栏目,
本期我们将带来 插入排序(希尔) 与 选择排序(堆排) 的实现与比较

请添加图片描述
排序要常用的Swap函数(交换两个数值)

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

插入排序

直接插入排序 void InsertSort(int* arr, int n)

基本思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。
插入流程如下所示:

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

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

直接插入排序分析
特性:元素集合越接近与有序,直接插入排序算法的时间效率越高。
时间复杂度:O(N^2)
空间复杂度:O(N)
稳定性:稳定

希尔排序 void ShellSort(int* arr, int n)

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

void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;while (end >= 0){if (arr[end + gap] < arr[end]){Swap(&arr[end + gap], &arr[end]);end -= gap;}else{break;}}}}
}

希尔排序分析:
1.希尔排序是对直接插入排序的优化。
2.但gap > 1是程序对进行预排序,目的是使数组逐渐趋向于有序化,。当gap==1时数组就已经接近有序了,便可以很快的排好。对于整体而言,这样可以达到优化的效果。
3.希尔排序的gap取值有很多种取法,例如,最初Shell所提出的gap = [n/2] , gap = [gap/2],还有后来Knuth所提出的gap = [gap/3] + 1,还有人提出都取奇数,也有人提出各gap互质。但没有一种主张得到证明,因为Shell排序的时间度分析极其困难。在Knuth所著的**《计算机程序设计技巧》中利用大量试验资料得出,当n很大时,关键码平均比较次数和对象平均移动次数大约在 [ n 1.25 , 1.6 n 1.25 ] [ n^ {1.25} , 1.6n^{1.25}] [n1.25,1.6n1.25]范围内,这是 利用直接插入排序作为子序列方法 的情况下得到的。而我们以上代码的gap就是按照Knuth**提出的方式取值的。
稳定性:不稳定

测试插入排序

测试函数 void verify(int* arr, int n)
void verify(int* arr, int n)
{for (int i = 1; i < n; i++){assert(arr[i] >= arr[i - 1]);}
}

以排非降序为例,若全为非降序则程序顺利通过,否则由assert函数终止程序并告知有误。

测试 InsertSort

我们先利用malloc开辟一个可存储10000个int类型的数组,再利用循环将数组内的数全置为随机数,再进行排序并检验。
在这里插入图片描述

我们运行后可以看到程序顺利通过,这说明测试成功,InsertSort正确无误。

测试 ShellSort

同理测试ShellSort.
在这里插入图片描述

可以看到ShellSort也是正确无误的。
测试代码:

void test_Sort()
{int n = 10000;int* arr = (int*)malloc(sizeof(int) * n); assert(arr);for (int i = 0; i < n; i++){arr[i] = rand();}ShellSort(arr, n);verify(arr, n);
}int main()
{srand((unsigned int)time(NULL));test_Sort();return 0;
}
测试速度 InsertSort & ShellSort

先写一个numcreate函数来开辟空间。

int* numcreate(int n)
{int* arr = (int*)malloc(sizeof(int) * n);assert(arr);return arr;
}

开辟两个可储存10w int类型的数组,并利用rand( )函数为他们附上相同的值,再利用clock()函数来记录时间,最后比较即可。
在这里插入图片描述
我们可以看到插入排序用了5512μs,而希尔排序只用了13μs,所以恭喜ShellSort在速度上战胜了InsertSort,代码如下:

test()
{int n = 100000;int* arr1 = numcreate(n);int* arr2 = numcreate(n);for (int i = 0; i < n; i++){arr2[i] = arr1[i] = rand();}int begin1 = clock();InsertSort(arr1, n);int end1 = clock();int begin2 = clock();ShellSort(arr2, n);int end2 = clock();printf("Insertsort : %d\n", end1 - begin1);printf("ShellSort  : %d\n", end2 - begin2);free(arr1);free(arr2);
}

选择排序

直接选择排序 void SelectSort(int* arr,int n)

基本思想:每次从待排数据中选出最小(最大)的值,再将其与起始位置的值交换,如此反复直到待排数据排完为止。
优化思路:每次选出最大值和最小值,最大值与待排数据末尾交换,最小值与待排数据起始位置交换,再反复循环即可。

实现步骤:
1.先确定数据开始位置begin与结束位置end
2.利用for循环找到[begin,end]区间的最大最小值,再分别交换,之后更新beginend
3.利用while循环来判断待排数据完成的条件
4.需要注意的是:当最大值为begin时,我们在交换时先交换了minibegin位置的数据,所以在进行maxiend前,我们要对maxi重新赋值,因为最大值被交换到了mini的位置,所以要maxi = mini

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

直接选择排序分析:
特性:思路通俗易懂,但效率不高,且实际应用不高
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:不稳定

堆排序 void HeapSort(int* arr,int n)

概念:堆排序是利用堆这种数据结构所设计的一种算法结构,通过逐个比较自身节点与左右子节点的大小来进行选择排序,这是选择排序的一种,它是通过堆来进行选择数据的。
方法:排升序建大堆,排降序建小堆。(本篇文章以排升序为例)
代码如下:

堆向下调整 void HeapDown(int* arr, int father,int size)

这里的size表示要调整数组的结束下标,father代表父节点即开始调整的位置,arr代表要调整的数组。

void HeapDown(int* arr, int father,int size)
{int child = father * 2 + 1;while (child < size){if (child + 1 < size && arr[child + 1] > arr[child]){child++;}if (arr[father] < arr[child]){Swap(&arr[father], &arr[child]);father = child;child = child * 2 + 1;}else{break;}}
}

先选出最大的子节点,在与父亲进行比较,若父节点小于子节点则进行交换,直到子节点要小于父节点的值,或者child>=size即子节点的下标值大于size结束下标的值就跳出循环。

堆排序 void HeapSort(int* arr,int n)

利用大堆的特性,堆顶一定为堆中的最大值,所以我们可以利用循环取出堆顶与堆中的最后一个数进行交换,在向下调整堆中 0 ~ n-1-i的数据位置,使得堆顶又重新变成下标为0~n-1-i 时的最大值,在依次循环,最后就排好了一个升序。
代码如下:

void HeapSort(int* arr, int n)
{int i = 0;for (i = (n - 1 - 1) / 2 ; i >=0 ; i--){HeapDown(arr, i, n);}//建堆for (i = 0; i < n - 1 ; i++){Swap(&arr[0], &arr[n - i - 1]);HeapDown(arr, 0, n - i - 1);}//排序
}

堆排序:
特点:堆排序利用堆来选择数据进行排序,这样效率就快很多了。
时间复杂度:O(N*logN)
空间复杂度:O(1)
稳定性:不稳定

测试选择排序

测试 SelectSort

相同的方法测试10w个 数据,成功。

测试 HeapSort

在这里插入图片描述
相同的方法测试100w个 数据,成功。

void test_Sort()
{int n = 1000000;int* arr = (int*)malloc(sizeof(int) * n); for (int i = 0; i < n; i++){arr[i] = rand();}HeapSort(arr, n);verify(arr, n);
}int main()
{srand((unsigned int)time(NULL));test_Sort();return 0;
}
测试速度 SelectSort & HeapSort

希尔 VS 堆排 (Debug版本)

说明

以下会分别对1w,10w,100w,1000w的数据进行100次的排序比较,并计算出排一趟的平均值。

rand( ) 生成随机数:rand( )函数生成的随机数区间为[0 , 32767] , rand()在10w以上量级的数据中会有较多的重复项。
rand( ) + i 生成随机数:它可以有效地避免rand( )在10w以上量级生成区间的问题,但是随着 i 越大,它生成的整体来看是较为有序的。

介绍就到这里了,让我们来看看这100次排序中,谁才是你心目中的排序呢?
PS:100次只是一个小小的测试数据,有兴趣的朋友可以在自己电脑上测试更多的来比较哦。

1w rand( ) 数据测试

在这里插入图片描述

10w rand( ) 数据测试

在这里插入图片描述

10w rand( ) + i 数据测试

在这里插入图片描述

100w rand( ) 数据测试

在这里插入图片描述

100w rand( ) + i 数据测试

在这里插入图片描述

1000w rand( ) 数据测试

在这里插入图片描述

1000w rand( ) + i 数据测试

在这里插入图片描述

测试代码如下:

int* numcreate(int n)
{int* arr = (int*)malloc(sizeof(int) * n);assert(arr);return arr;
}void Ultimate_Test()
{int n = 10000000, count = 100;int timeShell = 0, timeHeap = 0;for (int a = 0; a < count; a++){int* arr1 = numcreate(n);int* arr2 = numcreate(n);for (int i = 0; i < n; i++) arr1[i] = arr2[i] = rand() + i;int begin1 = clock();ShellSort(arr1, n);int end1 = clock();int begin2 = clock();HeapSort(arr2, n);int end2 = clock();timeShell += end1 - begin1;timeHeap += end2 - begin2;free(arr1);free(arr2);}printf("ShellSort : %.2f\n", 1.0 * timeShell / count);printf("HeapSort  : %.2f\n", 1.0 * timeHeap / count);}int main()
{srand((unsigned int)time(NULL));Ultimate_Test();return 0;
}

结语

看完之后,谁才是你心目中的排序呢?
欢迎留言,让我们一起来期待在下一期 《决战排序之巅(二)》

以上就是本期的全部内容喜欢请多多关注吧!!!

这篇关于决战排序之巅(一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/466383

相关文章

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图