梳齿排序的C ++程序？

  • Z时代
  • 2024-01-10
  • 分类：综合

梳齿排序和气泡排序的基本思想是相同的。换句话说，梳齿排序是对气泡排序的改进。在气泡分选技术中，将项目与每个阶段中的下一个项目进行比较。但是，对于梳子排序，项目将按特定的间隙进行排序。完成每个阶段后，差距会减小。此类的减少因子或收缩因子为1.3。这意味着在完成每个阶段后，间隙将除以1.3。最佳情况下，时间复杂度为O（n log n）。一般情况下为O（n 2 / 2n P）（p为增量数），最坏情况下为O（n 2）。

算法

CombSort（数组，大小）

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

输出 -排序的数组

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

以上是 梳齿排序的C ++程序？ 的全部内容， 来源链接： utcz.com/z/326805.html

回到顶部