梳排序和希尔排序的区别

在本教程中，我们将讨论梳排序、希尔排序以及它们之间的区别。

梳排序是冒泡排序的一个更复杂的版本。冒泡排序会评估所有相邻的值，而梳排序则消除了列表末尾的所有“乌龟值”或小值。

它是一种对比排序算法，主要对冒泡排序进行了改进。为了对待排序数组进行排序，冒泡排序使用相邻元素之间的比较。因此，在冒泡排序中，被比较的元素之间的间隙大小为1。通过使用大于1的间隙，梳排序的性能优于冒泡排序。梳排序的间隙从一个较大的值开始，并以1.3的因子递减。这意味着每完成一个阶段，间隙就会除以收缩因子1.3。这个迭代过程会一直重复，直到间隙等于1为止。

通过在200,000个随机列表上运行梳排序，发现收缩因子为1.3。梳排序的性能优于冒泡排序，尽管其在平均和最坏情况下的时间复杂度仍为O(n²)。

希尔排序是插入排序的一种扩展，它通过评估相隔多个位置的元素来解决插入排序的缺点。

它是插入排序算法的扩展版本。希尔排序降低了插入排序的平均时间复杂度。它是一种对比和原地排序算法，与插入排序类似。希尔排序对于中等规模的数据集效果很好。

在插入排序中，元素一次只能向前移动一个位置。将一个元素移动到较远的位置需要多次移动，这增加了算法的处理时间。然而，希尔排序消除了插入排序的这个缺点。它还允许移动和交换相距较远的元素。

梳排序的实现

让我们看一些用不同编程语言编写的梳排序代码。

C 语言

输出

以下代码的输出将是 -

Before sorting array elements are - 
49 11 24 44 29 27 2 
After sorting array elements are - 
2 11 24 27 29 44 49

C++ 程序

输出

以下代码的输出将是 -

Before sorting array elements are - 
49 11 24 44 29 27 2 
After sorting array elements are - 
2 11 24 27 29 44 49

时间复杂度

• 最佳情况： θ(n log n)。
• 平均情况： Ω(n2/2p)；p = 增量数。
• 最坏情况： O(n²)。

梳排序的空间复杂度为O(1)。

希尔排序的实现

让我们看一些用不同编程语言编写的希尔排序代码。

C 语言

输出

以下代码的输出将是 -

Before sorting array elements are - 
33 31 40 8 12 17 25 42 
After applying shell sort, the array elements are - 
8 12 17 25 31 33 40 42

C++ 程序

输出

以下代码的输出将是 -

Before sorting array elements are - 
33 31 40 8 12 17 25 42 
After applying shell sort, the array elements are - 
8 12 17 25 31 33 40 42

时间复杂度

• 最佳情况： O(n*logn)。
• 平均情况： O(n*log(n)²)。
• 最坏情况： O(n²)。

希尔排序的空间复杂度为O(1)。

梳排序 vs. 希尔排序

文章到此结束。希望您觉得这篇文章有用且内容丰富。