天津网站建设公司排名,四方坪网站建设,搭建一个电商网站需要多少费用,wordpress 中文图片不显示#x1f525;个人主页#xff1a; Quitecoder #x1f525;专栏: 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节#xff1a;排序 目录 1.排序的基本概念与分类1.1什么是排序的稳定性#xff1f;1.2内排序与外排序内排序外排序 2.插入排序2.1实现插入排序2.3稳定性…
个人主页 Quitecoder 专栏: 数据结构与算法 欢迎大家来到初阶数据结构的最后一小节排序 目录 1.排序的基本概念与分类1.1什么是排序的稳定性1.2内排序与外排序内排序外排序 2.插入排序2.1实现插入排序2.3稳定性分析 3.希尔排序3.1预排序代码实现3.2希尔排序代码实现3.3时间复杂度分析 4.clock函数总结 1.排序的基本概念与分类 排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中排序是数据处理中非常基本且重要的操作它可以帮助人们更有效地理解和分析数据。排序的顺序通常是升序或降序也可以按照数字、字母、大小或其他标准进行 常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序、堆排序等等
1.1什么是排序的稳定性 排序的稳定性是指在排序过程中具有相等键值的元素在排序前后保持相同顺序的特性。简单来说如果排序前两个相等的元素A和BA出现在B之前在排序后A仍然出现在B之前那么这种排序算法就是稳定的反之如果排序后A和B的顺序发生了变化这种排序算法就是不稳定的。 稳定性在某些情况下很重要尤其是当排序的键值是复合的即基于多个字段进行排序时。在这种情况下保持相等元素的初始顺序可能对保持数据的某种有意义的顺序非常关键。例如在对一组人按出生日期排序时如果有两个人出生日期相同我们可能会希望他们在排序后保持按姓名的顺序如果使用稳定的排序算法就可以保证这一点。
1.2内排序与外排序
根据在排序过程中待排序的记录是否全部被放置在内存中排序分为:内排序和外排序。
内排序
内排序是指所有需要排序的数据都加载到内存中进行排序的过程。这种排序方式适用于数据量不是非常大能够一次性装入内存的情况。内排序的优点是速度快因为内存的访问速度远高于磁盘或其他存储设备。常见的内排序算法包括快速排序、归并排序、堆排序、冒泡排序、选择排序、插入排序等。
外排序
外排序是指当需要排序的数据量非常大一次性无法全部加载到内存中时使用的排序方法。这种情况下数据通常存储在磁盘或其他外部存储设备上排序过程中需要多次在内存和存储设备之间交换数据。外排序的一个典型例子是归并排序的一个变种它将数据分成多个小块首先对每个小块进行排序内排序然后将这些已排序的小块合并成一个有序的整体。外排序适用于大规模数据处理但速度通常会比内排序慢
接下来我们来介绍两种排序直接插入排序与希尔排序
2.插入排序
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 扑克牌是我们都玩过的游戏拿到这组牌我们进行理牌将3和4移动到5的左侧再将⒉移动到最左侧顺序就算是理好了。这里的理牌方法就是直接插入排序法。
2.1实现插入排序
思路 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 首先构造函数
void InsertSort(int *a,int n);假设这里有数据1 5 8 6
我们认为在0到end这一段有序把end1的数插入数组
这里的end代表已排序序列的最后一个元素的索引。将插入的数据依次往前比较如果比前面的数字end大则放在end后面如果比前面的数字小则让前面的数字往后移动则这里用变量tmp存放要插入的值前面的数字移动后end减一继续比较
这里还有一种情况 这里要插入1遇到7向前移动end–当移动到最前面的位置时end减为-1 只考虑单趟排序可实现代码如下
int end;
int tmp a[end 1];
while (end 0)
{if (tmp a[end]){a[end 1] a[end];end--;}elsebreak;
}
a[end1]tmp;这里跳出循环有两种情况
找到插入位置当tmp大于等于a[end]这表明tmp应该插入在a[end]的后面因为在tmp之前的元素包括a[end]自己都已经排序好了并且都是小于等于tmp的。这就是tmp的正确位置在这种情况下我们执行break语句跳出循环并将tmp放置在end 1的位置达到有序序列的起点当循环保持进行end值在每次迭代中不断递减如果tmp小于所有已排序的元素end可能会变成-1这意味着tmp比有序序列中所有现有的元素都要小应该被放在整个序列的最开始位置。
在这两种跳出循环的情况下我们总是需要执行a[end 1] tmp;来将tmp元素放置到正确的位置上。因为无论是找到合适的插入点还是tmp成为新的最小元素我们都需要将它实际插入到有序序列中这就是为什么这行代码放在循环之外确保跳出循环后我们执行最终的插入动作。
考虑单趟排序之后我们来进行整个过程
void InsertSort(int *a,int n)
{for (int i 0; i n; i){int endi;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}elsebreak;}a[end 1] tmp;}
}通过将数组分为已排序部分和未排序部分来工作。从未排序部分取出的值被放置在已排序部分的正确位置。最初已排序部分只包含数组的第一个元素。
end最初被设置为当前索引i并将用于通过已排序部分向后遍历以找到tmp值的正确插入点。
我们进行代码测试
插入排序算法的时间复杂度取决于输入数组中元素的初始排序状态
最坏情况 如果数组是完全逆序的那么每次插入操作都需要将元素移到已排序部分的开头。这就意味着对于第i个元素可能需要进行i次比较和移动。这种情况下算法的时间复杂度是O(N2)因为需要进行总计约1 2 3 … (n-1)次比较这是一个n(n-1)/2的等差数列最好情况 这种情况发生在数组已经完全有序时。在这种情况下每次比较后很快就会找到插入位置在已排序元素的末尾不需要进行额外的移动。因此最好情况下插入排序的时间复杂度是O(N)因为外层循环只会遍历一次数组内层循环不会进行任何实际的比较和移动操作。
插入排序的空间复杂度为O(1)因为它是一个原地排序算法不需要额外的存储空间来排序。
2.3稳定性分析
在插入排序中每个新元素被插入到已经排序的序列中在找到合适的插入位置之前它不会交换到任何具有相同值的元素前面。我们来逐步分析插入排序算法来说明其稳定性
排序初始时认为第一个元素自成一个已排序的序列从第二个元素开始取出未排序的下一个元素在已排序的序列中从后向前扫描如果当前扫描到的元素大于新元素待插入那么将扫描到的元素向后移动一个位置重复步骤3直到找到一个元素小于或等于新元素的位置或者序列已经扫描完毕将新元素插入到这个位置后面
在步骤4中插入排序的算法逻辑保证了如果存在相等的元素新元素待插入将被放置在相等元素的后面。因此原始顺序得以保持插入排序被认为是稳定的
3.希尔排序
希尔排序是一种基于插入排序的算法通过引入增量的概念来改进插入排序的性能
希尔排序的基本思想是将原始列表分成多个子列表先对每个子列表进行插入排序然后逐渐减少子列表的数量使整个列表趋向于部分有序**最后当整个列表作为一个子列表进行插入排序时由于已经部分有序所以排序效率高。**这个过程中每次排序的子列表是通过选择不同的“增量”来确定的。
实现思路
预排序直接插入排序
预排序 根据当前增量数组被分为若干子序列这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。
假设当前增量为3 首先增量为3我们将数组元素分为增量3个子序列每个子序列由原数组中相隔增量位置上的元素组成。所以我们有如下子序列
子序列1: 9, 6, 3, 0子序列2: 8, 5, 2子序列3: 7, 4, 1
然后对每个子序列进行独立的插入排序
子序列1排序后0, 3, 6, 9子序列2排序后2, 5, 8子序列3排序后1, 4, 7
现在将排序后的子序列放回原数组中数组变化为 完成了一轮希尔排序此时整个数组并不完全有序但是已经比原始的数组更接近有序了。然后减小增量通常是将原来的增量除以2如果增量序列选择为原始的版本现在选择下一个增量为 1因为 3/2 不为整数所以直接减到 1进行最后的常规插入排序。
现在整个数组就是一个子序列进行常规的插入排序。
0 2 1 3 5 4 6 8 7 9 - 初始
0 2 1 3 5 4 6 8 7 9 - 第1个元素不动因为它已经在正确的位置
0 1 2 3 5 4 6 8 7 9 - 将2和1交换
0 1 2 3 5 4 6 8 7 9 - 3已经在正确位置
0 1 2 3 5 4 6 8 7 9 - 第5个元素5不动因为它左边的元素全部小于5
0 1 2 3 4 5 6 8 7 9 - 将5和4交换
0 1 2 3 4 5 6 8 7 9 - 第7个元素6不动因为它左边的元素全部小于6
0 1 2 3 4 5 6 8 7 9 - 第8个元素8不动因为它左边的元素全部小于8
0 1 2 3 4 5 6 7 8 9 - 将8和7交换
0 1 2 3 4 5 6 7 8 9 - 第10个元素9不动因为它左边的元素全部小于93.1预排序代码实现
我们现在控制实现单趟排序
int gap 3;
int end;
int tmp a[end gap];
while (end 0)
{if (tmp a[end]){a[end gap] a[end];end-gap;}elsebreak;
}
a[end gap] tmp;与前面代码不同的是这里对end所加减的均为gap
单次插入完成后我们来控制单个子序列的整个过程以蓝为例每实现一次排序下一次插入的数据为endgap
int gap 3;for (int i 0; 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;}elsebreak;}a[end gap] tmp;
}这里for循环的条件为in-gap防止数组越界
完成单个子序列的排序后我们再对整个子序列排序
int gap 3;
for (int j 0; j gap; j)
{for (int i 0; 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;}elsebreak;}a[end gap] tmp;}
}外层循环for (int j 0; j gap; j)意在对每个以gap为间隔的分组进行遍历。
j0, 这串代码三层循环的逻辑是按照每一组排序完成后再进行下一组排序的事实上我们可以不需要最外层的循环 代码优化
int gap 3;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;
}这里我们将原先代码中的i gap修改为i意味着这次不是按照一组一组进行了是一次排序完每个组的第二个元素再进行下一个元素的排序
3.2希尔排序代码实现
我们先对预排序的增量进行分析
gap越大大的值更快调到后面小的值更快调到前面越不接近有序gap越小大的值更慢调到后面小的值更慢调到前面越接近有序
当gap为1就是直接插入排序
所以在实现希尔排序时给gap固定值是行不通的 因此gap的值是应该随着n来变化的实现多次预排 void ShellSort(int* a, int n)
{int gap n;while (gap 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;}elsebreak;}a[end gap] tmp;}}
}这里无论gap是奇数还是偶数这里gap最终都会除以到值为1
在这里
gap1时是预排序目的让其接近有序gap1时是直接插入排序目的让其有序
在gap1时已经十分接近有序了
这里gap预排序次数还是有点多因此我们可以再次进行修改让gap每次除以3为了使gap最后能回到1我们进行加一处理
int gap n;
while (gap 1)
{gap gap / 31;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;}
}测试代码
3.3时间复杂度分析 希尔排序的时间复杂度并不固定它依赖于所选择的间隔序列增量序列。直到今天已经有多种不同的间隔序列被提出来每种都有自己的性能特点 不同的参考书中给了不同的解释 现代更高效的增量序列可以使希尔排序达到O(N log N)时间复杂度但是没有任何增量序列可以保证希尔排序在所有情况下都达到O(N log N)。最低的已知上限为O(N (log N)2)。 总的来说由于增量序列的不确定性希尔排序的时间复杂度不容易精确描述实际的时间复杂度取决于所选用的间隔序列以及待排序数组的初始排列状况。在实际应用中希尔排序的性能通常介于O(N)和O(N2)之间对于中等大小的数据集它可以提供非常不错的速度尤其是因为它比较简单易于实现且对于较小的数据集它一般比O(N log N)复杂度的算法更快。 4.clock函数
clock() 函数是time.h头文件中的一个函数用来返回程序启动到函数调用时之间的CPU时钟周期数。这个值通常用来帮助衡量程序或程序的某个部分的性能
我们可以用这个函数进一步对比两种排序占用的CPU时间
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);free(a1);free(a2);
}这里让随机生成十万个随机数分别用希尔排序和直接插入排序来进行排序测试两种算法的执行时间 我们可以发现希尔排序的执行时间相比于直接插入排序很有优势
总结
希尔排序和直接插入排序都是改进和优化了简单排序算法的典型例子。直接插入排序以其简洁和对于小规模数据集的高效性而著称特别适合几乎已经排序好的数据。而希尔排序则通过引入“增量”的概念允许交换距离较远的元素从而大幅度提高了对大规模数据集的排序效率。两者都在计算机科学的排序算法领域中占有重要地位不仅展示了算法设计的基本原则也为更复杂排序算法的发展奠定了基础。
本节内容到此结束感谢大家的观看
