梳状排序
梳齿排序和气泡排序的基本思想是相同的。换句话说，梳齿排序是对气泡排序的改进。在气泡分选技术中，将项目与每个阶段中的下一个项目进行比较。但是，对于梳子排序，项目将按特定的间隙进行排序。完成每个阶段后，差距会减小。此类的减少因子或收缩因子为1.3。这意味着在完成每个阶段后，间隙将除以1.3。
梳子分类技术的复杂性
时间复杂度： 最佳情况下为O（nlogn）。一般情况下为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