ComboSort
Combosort是一个基于swap的排序, 和冒泡排序一样, 它改良了冒泡排序中只对相邻元素做比较然后swap的特点, 通过使用gap 表示两个数时间的index位置, 然后用gap除以一个经验定值1.3,获得当前比较的两个数的位置. gap从n一直减小到1, 然后完成排序.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> using namespace std; int findgap(int x) { x = (x * 10) / 13; return max(1, x); } void combosort(int a[], int l, int r) { int gap = r; bool swapped = true; while (gap != 1 || swapped) { gap = findgap(gap); swapped = false; for (int i = l; i < r - gap; i++) { if (a[i] > a[i + gap]) { swap(a[i], a[i+gap]); swapped = true; } } } } void sort(int a[], int n) { combosort(a, 0, n); } |