希尔排序/选择排序

2024-09-08 08:52
文章标签 选择 排序 希尔

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

前言:

本篇主要对常见的排序算法进行简要分析,代码中均以数组 arr[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 } 为例,进行升序排列。

常见的排序算法有如下:

选择排序中,直接选择排序没有任何实际与教育意义,而堆排序在先前文章中有提及,不在考虑。

1:插入排序

1.1 :直接插入排序

1.1.1 :代码

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

1.1.2:图例分析上述代码

首次进入 for 循环时,如图一所示:

注:end 对应数组下标,tmp 对应数组元素

图一

此时 end = 0,进入 while 循环;此时 arr[end] = 5 ,tmp = 3 ,满足 if  条件,将数组第一个元素的值赋值给第二个元素,end-- 后为 -1,不满足 while 循环条件,结束while 循环。

当第一次跳出while循环时,此时数组中的元素如图二

图二

此时并没有得到我们想要的数组,下标 0和1 的元素重复 ,我们需要将 tmp 的值传递到 下标0 处,而通过 end+1 便可以访问 下标0处,因此 arr[end + 1] = tmp;  该条语句的目的就是为了得到正确排列的数组。

第二次进入 for 循环时,如图三所示:

图三:

此时 end = i = 1,而 tmp = 9,进入while循环后,不满足 if 条件,因此直接结束。

第三次进入for循环时,如图四所示:

图四:

此时 end = i = 2 ,而 tmp = 6,进入while循环后,满足 if 条件,元素 6 会被 9 替代,而 end-- 指向前一个位置处,此时如图五所示

图五:

此时end = 1 再次进入while循环时,此时不在满足 if 条件 ,结束 while 循环,通过最后一步 end+1,我们可以访问被代替元素的前一个元素的下标位置处,即下标2处,再将 tmp 赋值给 arr[end+1]即arr[2]我们可以得到正确的排列如图六:

图六

第四次进入循环时,如图七所示:

图七:

此时 end = 3,tmp = 2,进入循环后,因为 2 小于 前面所有元素,因此不断循环直至end = -1,如图八所示:

图八:

再次将tmp的值赋值给 arr[end+1] 便可以得到正确的排序。

1.1.3:直接插入排序的特点

①、元素越接近有序,直接插入排序算法的时间效率越高

②、时间复杂度为O(N^2)

③、空间复杂度为O(1)

1.2:希尔排序

1.2.1:思路

希尔排序是在直接插入排序的基础进行的优化,前面所说,元素越接近有序,直接插入排序算法的时间效率越高,希尔排序正是按着这个特性,先尽可能的让数组元素有序,再进行排序。

因此希尔排序的思路为:

先将数组内的元素按间隔排序,这个间隔一般为 n/3+1,n为数组内元素个数,并且每排序完一次,gap = gap /3 +1 再按新的gap再次排序,直至 gap为1时,此时就变成了直接插入排序,但这是的数组已接近有序,因此时间复杂度会大大降低。

1.2.2:代码:

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;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}}
}

分析:

在直接插入排序的基础上,在外层又嵌套了一层while循环,这个while循环就是用来对gap进行限制,当gap较大时,此时每个元素间的间距(gap)比较大,当gap = 4 时,如下图

当外层while第一次循环结束时,如图所示,此时较原来相比,已接近有序,此时 gap = 2 再次循环。

当外层while第二次循环结束时,如图所示,数组元素变得更加有序。

最后当gap = 1时,此时就为直接插入排序。

1.2.3:希尔排序的特点:

时间复杂度 O(N^1.3)

2:交换排序

2.1:冒泡排序

2.1.1:代码

void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//升序if (arr[j] < arr[j + 1]){exchange = 1;swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

分析:

有着一定的教育意义,能够让初学者初步熟悉代码,时间复杂度为O(N^2),在有序的情况下,时间复杂度为O(N);

2.2:快速排序

快速排序一共有四种实现方式,前三种实现方式都是基于递归的思想,在找基准值上存在着区别,而第四种方法是借助堆,通过循环模拟递归的思想来实现。

2.2.1:基于递归思想实现快速排序

先前说到,递归实现快速排序只在找基准值的方法上存在区别,那么什么是基准值?我们所要找的基准值,以升序为例,就要是在数组中找到这样一个位置,他的左边的元素都小于它,右边的元素都大于它,这个元素对应的下标大小就为基准值

2.2.1.1:hoare法
找基准值的代码:
int _QuickSort3(int* arr, int left, int right)
{int keyi = left;left++;while (left <= right){while (left <= right && arr[right] > arr[keyi]){right--;}//while循环结束时,此时right下标处对应为较小元素while (left <= right && arr[left] < arr[keyi]){left++;}//while循环结束时,此时left下标处对应为较大元素if (left <= right)//当满足条件时,将left 和 right 对应下标的元素交换,得到相对有序数组{swap(&arr[left++], &arr[right--]);}}//上述循环结束时,此时right对应较小元素swap(&arr[keyi], &arr[right]);//将假设值与较小值交换return right;//返回基准值
}
图例分析:

未进入第一个while循环前,各变量对应关系如图一所示,以keyi作为参考值

图一:

当进入外层while循环后,right开始向右找较小值,left开始向左找较大值,当内层的两个while循环结束时,此时各变量对应关系如图二所示:

图二:

此时 left < right 交换两者下标对应元素后 left++,right--,各变量对应关系如图三所示:

图三:

此时left和while仍满足外层while循环条件,继续重复上述步骤直至如图四所示。

图四:

此时已经跳出外层循环,将 keyi 与 right 对应下标元素交换后,此时 right 左侧元素均小于 5,右侧元素均大于5,而right就是我们所找的基准值。

递归实现部分代码:
void QuickSort3(int* arr, int left, int right)
{if (left >= right){return;}int key = _QuickSort3(arr, left, right);QuickSort3(arr, left, key - 1);QuickSort3(arr, key+1, right);
}
递归过程:

对于初学者而言,在分析过程中容易忽略 left值 和 right值 的变化,在上述递归的过程中,可以看到,key的改变会影响下次递归 left 和 right 的值,正是 left 和 right 改变,才能使递归满足停止条件,从而返回。

注:其他问题。

1、为什么外层的 while 要去等号?

分析

以下图为案例:

我们顺着上述代码,最终第一次循环会来到如下位置:

此时left = right跳出循环,再将right对应的值与key对应值交换,此时得到如下图所示数组:

显然上图的基准值是不符合条件的,因此外层需要加上等号

2、为什么内层交换两个元素前,需要加该 if 条件

分析

以下图数组为例:

顺着代码,当第一次循环结束前,各个变量对应关系如图所示

此时若没有该 if 条件,right 和 left 的对应元素会再交换一次,这样就不符合基准值的条件,因此需要有该 if 条件,代码才能够正常运行。

2.2.1.2:挖坑法

前面所说,三种递归实现快速排序的方法只在找基准值的方法上有所不同,因此这里不再对其他代码过多追叙,直接分析找基准值部分的代码:

找基准值代码:
int _QuickSort2(int* arr, int left, int right)
{int hole = left;int keyi = arr[left];while (left < right){while (left < right && arr[right] > keyi){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] < keyi){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = keyi;return hole;
}
图例分析:

起始时,各个变量对应关系如图所示:

假设坑(hole)的位置在 left 处,并且将 left 处对应的元素临时存放在 keyi 中,我们先从 right 开始向左找比keyi小,找到第一个位置处时,将 hole 位置处的值赋为 right 位置处的值,同时将 hole 移动到 right 位置处,此时新坑位于 right 处,此时各变量对应关系如下图所示:

然后我们再从 left 向右开始找比keyi大的值,找到第一个位置处 9 时,我们重复上述的过程,把元素 9 赋值给 hole 位置处,然后把 hole 移到 left 位置处,此时各变量对应关系如下图所示:

注:其实此时我们能够发现,left 和 right 位置对应的值已经发生改变,第二次循环开始时,已然满足内层循环的 while 条件,因此 right 可以继续向左减减找小值,而 left 也能够向右加加找大值

重复上述过程,最终各个变量对应关系如下图:

注:为什么内层循环要多一个 left < right 的判定条件?

分析:可以看到,如果没有这个条件,left 会继续向右找大值,即到下标为5的位置处,会让 hole 多一次变化,而这一次变化,会导致所找的基准值发生错误,因此内层的 while 循环需要多这一个条件。当while循环结束时,我们再把临时值 keyi 赋值给 hole 位置处,此时 hole 位置就是对应基准值的位置,各个变量关系如下图所示

2.2.1.3:lumoto法
找基准值代码:
int _QuickSort(int* arr, int left, int right)
{int prev = left;int keyi = left;int cur = prev + 1;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[keyi], &arr[prev]);return prev;
}
图例分析:

起始时,各变量对应关系图下图:

定义一个前后变量 prev 和 cur,同时定义临时值 keyi = 5 。当 cur 中对应的值小于 keyi时,同时 ++prev 不等于 cur 时,我们让 prev 对应的值与 cur 对应的值交换,内层循环的 if 隐含着一些码字菜鸟(我)容易忽略的信息,为什么++prev 而不是 prev++,首先这个条件是为了避免重复交换,其次 ++prev 后此时虽然不满足 if 条件,但是 prev 的值还是 +1 了,因此此时 prev 和 cur 已经指向了同一个位置,只不过不会发生交换而已,各个变量关系如下图所示: 

判定完 if 条件后,让 cur 持续++。观察上述数组,能够发现,3 后面的两个元素均大于临时值 keyi,此时 prev会来到元素 2 的位置处,而 2 已经满足内层 if 条件,因此我们将 prev+1 后 与 cur 位置对应的元素交换,此时各个变量关系对应如图所示:

重复上述过程,最终各个变量的对应关系如图所示:

当外层 while 循环结束时,我们交换 下标0 与 prev位置对应的元素,即得到了我们想要的数组,同时 prev 为基准值对应的位置处。

2.2.1.4:递归版本快速排序的特性:

1.时间复杂度为:O(nlogn)

2.空间复杂度为:O(logn)  —— 这个空间复杂度来源与递归的层数,每次递归会像系统申请新的空间,同时原空间会被保留。

2.2.2:非递归版本的快速排序的实现

前言:非递归版本的快速排序是借助栈的方式来实现的,将数组首尾下标入队后,取栈内两个数据作为数组尾和头再出栈,通过lumoto方法找到该数组对应的基准值key,再将 left ~ key-1 的下标,以及 key+1 ~ right 的下标入堆,重复上述过程,直至堆中不再有任何元素。

注:因为传递的是数组的地址,入栈的也只是数组对应的下标,当出栈时,当然可以通过下标去访问原先的数组,同时令原先数组发生改变。

代码:
void QuickSortNonR(int* arr, int left, int right)
{ST s;STInit(&s);STPush(&s, left);STPush(&s, right);while (!BoolEmpty(&s)){int end = STTop(&s);STPop(&s);int begin = STTop(&s);STPop(&s);int prev = begin;int keyi = begin;int cur = prev + 1;while (cur <= end)     //找基准值同时对数组进行排序{if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}cur++;}swap(&arr[keyi], &arr[prev]);int key = prev;if (key - 1 > begin)   //模拟返回的过程,若不满足条件则不入栈{STPush(&s, begin);STPush(&s, key-1);}if (key + 1 < end){STPush(&s, key+1);STPush(&s, end);}}
}
图例演示一下这个while循环的过程:

初始时,将下标 0 和下标 8 入栈

由此我们开始分析while循环部分,以栈为空作为外层 while 循环的结束条件

进入外层 while 循环后取栈顶元素并且出栈,这种取元素再出栈的操作保证了我们能够取到我们想要的元素,同时将这两个元素作为 lumoto法找基准值中的 cur 的结束位置和 prev 初始大小。

注:注意入栈的顺序,入栈顺序会影响后续读取栈顶元素时,begin 和 end 的取值

当我们取到下标 0 和 8 时,通过下标访问数组元素,同时基于lumoto法实现找基准值的方法,这里不在过多追叙,此时各变量关系如图所示:

此时显然满足 begin < key - 1、 key+1 < end ,因此将下标 begin、key-1、key+1、end 分别入栈,当第二次进入循环时,首两次出栈会取到下标 key+1 和 end ,这正对应了2.2.2.1中提到的递归过程一样,left的值发生变化的过程,(编者菜,会觉得left一直等于0,其实正如刚才的递归过程一样,每个子节点的向右递归left值会发生改变),于是我们先对这对范围内的数组进行找基准值和排列操作,操作完成后,再次向栈中,push下标,直至不在满足 if 条件为止,不过此时栈中元素不为空,因为原先找的基准值 4 左边的数组尚未进行排序,接下来从栈中取出的元素,正是对左半部分进行找基准值和排序的操作,如此循环往复直至结束。

上图为对基准值右半部分的循环过程,可以看到当不满足 begin < key - 1、 key+1 < end 时,不再入栈,右半部分循环结束,此时栈中还保存着基准值左半部分的下标位置,取出栈内元素后,可以对左半部分进行找基准值和排列操作。

这篇关于希尔排序/选择排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

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

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

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

hdu 1285(拓扑排序)

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

cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈? cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte

如何选择SDR无线图传方案

在开源软件定义无线电(SDR)领域,有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案: 1. **OpenHD**:这是一个远程高清数字图像传输的开源解决方案,它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链,包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP(Universal Software Radio Periphera

《数据结构(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