資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 排序程式？
梳狀排序和氣泡排序的基本思想是相同的。換句話說，梳狀排序是對氣泡排序的改進。在氣泡排序技術中，在每個階段，將專案與下一個專案進行比較。但對於梳狀排序，專案按特定間隙進行排序。完成每個階段後，間隙會減少。這種排序的減小因數或收縮因數為 1.3。這意味著完成每個階段後，間隙將除以 1.3。最佳情況下的時間複雜度為 O(n log n)。平均情況為 O(n2/2nP)（p 是增量數量），最壞情況為 O(n2)。
演算法
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 << "Enter elements:" << 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 Enter elements: 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
更新於：2019 年 7 月 30 日
287 次瀏覽
廣告