排序算法14：梳状排序

介绍：

梳子排序是对气泡排序的改进

如您所知，冒泡排序将对相邻元素进行排序，梳齿排序将使用间隙对元素进行排序。

每次通过时，间隙将减小1.3，直到达到1.。

从而对数组进行排序。

让我们了解梳理排序将有助于示例：

最初，数组如下所示：

最初的差距为10。

因此，我们比较第一个和最后一个元素。如果最后一个元素小于第一个元素，则交换元素。

从上图可以看出，1小于8。因此，交换：

现在将差距减少1.3。因此10 / 1.3 =7。这将是第2遍。在第2遍中，我们比较间隙为7的所有元素，并执行如下所示的类似检查。

下图将向您展示从步骤2开始执行的步骤顺序：

现在，第二遍结束时的最终数组如下：

现在将差距减少1.3。所以7 / 1.3 = 5

第三遍的步骤顺序如下：

第四关再次将差距减小1.3。即5 / 1.3 = 3

我们需要在步骤4的末尾执行类似的操作。数组如下所示：

再次将差距减小1.3，即3 / 1.3 =2。在第5遍结束时，结果将是：

再次将间隙减小1.3，即2 / 1.3 = 1。

在第6遍结束时，结果如下：

这是最终结果。

C ++中Comb Sort的实现

#include<iostream>

using namespace std;

void combSort(int *array, int length) 
{
   int gap = length; 
   bool flag = true;

   while(gap != 1 || flag == true) 
   {
   	//reduce the gap by 1.3
      gap = (gap)/1.3; 
      if(gap<1)
         gap = 1;
      flag = false;

      //check the elements that are "gap" distance
      for(int i = 0; i< length - gap; i++) 
      { 
         if(array[i] > array[ i + gap ]) 
         {
            swap(array[i], array[ i + gap ]);
            flag = true;
         }
      }
   }
}


int main()
{
	int arr[] = {5, 4, 3, 2, 1, 9, 8, 7, 6, 10};

	combSort(arr, 10);

	cout<<"The sorted order is \n";

	for (int i = 0; i < 10; ++i)
	{
		cout<<" "<<arr[i]<<" ";
	}
	cout<<endl;

	return 0;
}

输出：

The sorted order is
 1  2  3  4  5  6  7  8  9  10

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：