梳状排序

梳齿排序和气泡排序的基本思想是相同的。换句话说，梳齿排序是对气泡排序的改进。在气泡分选技术中，将项目与每个阶段中的下一个项目进行比较。但是，对于梳子排序，项目将按特定的间隙进行排序。完成每个阶段后，差距会减小。此类的减少因子或收缩因子为1.3。这意味着在完成每个阶段后，间隙将除以1.3。

梳子分类技术的复杂性

• 时间复杂度： 最佳情况下为O（n log n）。一般情况下为O（n ^ 2/2 ^ p）（p为递增数），最坏情况下为O（n ^ 2）。

• 空间复杂度： O(1)

输入输出

Input:
A list of unsorted data: 108 96 23 74 12 56 85 42 13 47
Output:
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108

算法

CombSort(array, size)

输入-数据数组，以及数组中的总数

输出- 排序的数组

Begin
   gap := size
   flag := true
   while the gap ≠ 1 OR flag = true do
      gap = floor(gap/1.3) //the the floor value after division
      if gap < 1 then
         gap := 1
      flag = false

      for i := 0 to size – gap -1 do
         if array[i] > array[i+gap] then
            swap array[i] with array[i+gap]
            flag = true;
      done
   done
End

示例

#include<iostream>
#include<algorithm>
using namespace std;

void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void combSort(int *array, int size) {
   int gap = size; //initialize gap size with size of array
   bool flag = true;

   while(gap != 1 || flag == true) {
      gap = (gap*10)/13; //minimize gap by shrink factor
      if(gap<1)
         gap = 1;
      flag = false;

      for(int i = 0; i<size-gap; i++) { //compare elements with gap
         if(array[i] > array[i+gap]) {
            swap(array[i], array[i+gap]);
            flag = true;
         }
      }
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n]; //create an array with given number of elements
   cout << "输入元素：" << endl;

   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   combSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

输出结果

Enter the number of elements: 10
输入元素：
108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108