梳状排序的 C++ 程序?
server side programmingprogrammingc++
梳状排序和冒泡排序的基本思想相同。换句话说，梳状排序是对冒泡排序的改进。在冒泡排序技术中，每个阶段都会将项目与下一个项目进行比较。但对于梳状排序，项目按特定间隙排序。完成每个阶段后，间隙会减小。此排序的减小因子或收缩因子为 1.3。这意味着完成每个阶段后，间隙除以 1.3。最佳情况下的时间复杂度为 O(n log n)。平均情况下为 O(n2/2nP)(p 为增量数)，最坏情况下为 O(n2)。
算法
CombSort(array, size)
输入 −一个数据数组，以及数组中的总数
输出 − 排序后的数组
开始 gap := size flag := true while the gap ≠ 1 OR flag = true do gap = floor(gap/1.3) //除法后的 floor 值 if gap < 1 then gap := 1 flag = false for i := 0 to size – gap -1 do if array[i] > array[i+gap] then 将 array[i] 与 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; //用数组大小初始化间隙大小
bool flag = true;
while(gap != 1 || flag == true){
gap = (gap*10)/13; //通过收缩因子最小化间隙
if(gap<1)
gap = 1;
flag = false;
for(int i = 0; i<size-gap; i++){ //比较有间隙的元素
if(array[i] > array[i+gap]){
swap(array[i], array[i+gap]);
flag = true;
}
}
}
}
int main(){
int n;
cout << "输入元素数量:";
cin >> n;
int arr[n]; //创建一个具有给定元素数量的数组
cout << "输入元素:" << endl;
for(int i = 0; i<n; i++){
cin >> arr[i];
}
cout << "排序前数组:";
display(arr, n);
combSort(arr, n);
cout << "排序后数组:";
display(arr, n);
}
输出
输入元素数量:10 输入元素: 108 96 23 74 12 56 85 42 13 47 排序前数组:108 96 23 74 12 56 85 42 13 47 排序后数组:12 13 23 42 47 56 74 85 96 108
