虽然标题中的排序算法往往被认为是低效率的算法.但并不意味着这些算法完全没有可取之处。本次不再探讨这些算法的基本原理，仅仅比较算法的性能，并贴出实现这些算法的源代码：
还是先肝代码吧（手动狗头）：
# include"iostream" # include "vector" # include "ctime" # include "cstdlib" using namespace std; void insert_sort(vector<int> & ); void ChooseSort(vector<int> &); void BubbleSort(vector<int> &); void CombSort(vector<int> & ); int main() { const int MAX_NUMBER = 3000;//生成的随机数的个数 const int MIN_VALUE = 1; //随机数值的下界 const int MAX_VALUE = 20000;//随机数值的上界 vector<int> a; a.reserve(MAX_NUMBER);//预先分配内存你，预防迭代器的失效。否则内存搬移，迭代器容易失效 // 采用控制台输入的方式 //int temp; //while (cin >> temp) //{ // a.push_back(temp); // if (cin.get() == ' ') //注意这种用法，用的很多。 // { // break; // } //} //采用随机数生成法。 srand((unsigned)time(NULL));//根据时钟生成不同的种子，保证每次运行程序产生不同的随机数 for (int i = 1; i <= MAX_NUMBER; i++) { int temp; temp = (rand() % (MAX_VALUE - MIN_VALUE + 1)) + MIN_VALUE;//生成[MIN_VALUE，MAX_VALUE]之间的整数随机数 a.push_back(temp); } //cout << "The initial order: "; 数据量太大，不适合输出 //vector<int>::iterator ia = a.begin(); //for (; ia != a.end(); ia++) //{ // cout << *ia << " "; //} //cout << endl; vector<int> b(a); vector<int> c(a); vector<int> d(a); //show the initial order of the vector //cout << "The initial order before Sorting : "; //vector<int> ::iterator ia = a.begin(); //for (; ia != a.end(); ia++) //{ //cout << *ia << " "; //} //cout << endl; // 插入排序测试 clock_t start, finish; double runtime; start = clock(); insert_sort(a); finish = clock(); runtime = (double)(finish - start) / CLOCKS_PER_SEC; cout << "The time of Insert Sort algorithm is：" << runtime << "s" << endl; // 选择排序测试 start = clock(); ChooseSort(b); finish = clock(); runtime = (double)(finish - start) / CLOCKS_PER_SEC; cout << "The time of Choose Sort algorithm is：" << runtime << "s" << endl; // 冒泡排序测试 start = clock(); BubbleSort(c); finish = clock(); runtime = (double)(finish - start) / CLOCKS_PER_SEC; cout << "The time of Bubble Sort algorithm is：" << runtime << "s" << endl; // 梳排序测试 start = clock(); CombSort(d); finish = clock(); runtime = (double)(finish - start) / CLOCKS_PER_SEC; cout << "The time of Comb Sort algorithm is：" << runtime << "s" << endl; //cout << "The new order after Comb Sorting : "; //vector<int> ::iterator id = d.begin(); //for (; id != d.end(); id++) //{ // cout << *id << " "; //} //cout << endl; system("pause"); return 0; } //插入排序 void insert_sort( vector<int> & sort_a) ///注意，采用vector<int> 是可以作为参数进行传递的,那么是否可以作为返回类型使用呢？ { int a_size ,temp; a_size = sort_a.size(); for (int i = 1,j; i < a_size; i++)//注意，将j放在这里声明，不要放在下一个循环中声明，否则会造成多次声明？（但是作用域没变，多次声明应该被禁止，所以没有多次声明？） { temp = sort_a[i]; for (j = i; (j > 0) && (sort_a[j - 1] > temp); j--)//这里先后顺序的差别，导致了数组的越界， { sort_a[j] = sort_a[j-1]; } sort_a[j] = temp; } //return sort_a;//说明可以将vector<int> 本身作为函数的返回值使用,但是需要清楚的是：返回的时候，内存实际上发生了局部变量复制，所以是否考虑返回引用？？？ } //选择排序 void ChooseSort(vector<int> & sort_a) { int a_size,MinNum; a_size = sort_a.size(); for (int i = 0, j; i < a_size; i++) { int Loc = i; MinNum = sort_a[i];//本质是随机迭代器的使用 //temp = sort_a[i]; for (j = i+1; j < a_size; j++) { if (sort_a[j] < MinNum) { MinNum = sort_a[j]; Loc = j; } } //sort_a[i] = MinNum;//用于交换，但是本身自带的函数可以实现 //sort_a[Loc] = temp; if (i != Loc) { swap(sort_a[i], sort_a[Loc]);//vector自带的东西 } } } //冒泡排序 void BubbleSort(vector<int> & sort_a) { int a_size; a_size = sort_a.size(); for (int j = 0; j < a_size-1; j++) { for (int i = 0; i < a_size - 1-j; i++) { if (sort_a[i]>sort_a[i + 1]) swap(sort_a[i], sort_a[i + 1]); } } } //梳排序 void CombSort(vector<int> & sort_a) { int step,j,k; step = sort_a.size(); while ((step = int(step / 1.3)) >0) { for (j = sort_a.size() - 1; j >= step; j--) { k = j - step; if (sort_a[j] < sort_a[k]) { swap(sort_a[j], sort_a[k]); } } } }
补充：由于之前对梳排序未做任何的说明，在此简要的说明一下梳排序：梳排序的本质仍然是冒泡排序，差异在于，梳排序的冒泡对象并不是相邻元素，而是距离为step的元素，而step是一个变量（右大变小），即“梳子”间隙逐渐变小。而梳排序迭代的终止条件是：当step变成1，即退化为传统的冒泡后，执行一次，则得到正确的顺序。
在此，我们给出上述四种排序的测试结果：
| 5000 | 10000 | 15000 | 20000 | |
| 插入 | 0.839s | 3.427 | 7.716s | 13.648s |
| 选择 | 0.667s | 2.276 | 5.321s | 9.208s |
| 冒泡 | 2.320s | 9.177 | 20.823s | 36.542s |
| 梳 | 0.016s | 0.042 | 0.057s | 0.079s |
上述表格中的(5000,10000,....表示数据规模，程序中随机生成的随机数，我们可以看到，测试结果表明：按照速度而言，算法的时间性能上：梳>>选择>插入>冒泡（>表示优于）；（冒泡辣鸡实锤（开个玩笑）），即算法性能上，梳排序的性能要远远高于其他的方式。我们通过观察算法执行时间，梳状排序时间复杂度并不是O（n2），似乎比这个时间复杂度要低，实际上也的确如此。而对于插入，选择，冒泡而言，尽管时间复杂度都是O（n2），但是毕竟还是有所差异，当数据更莫更大的时候，这种差异将会更加明显，但是无疑，冒泡排序时间复杂度真的高，冒泡排序的最好，最差，平均时间复杂度都是相同的，都是O（n2）。
疑问：在学习梳排序的时候，见有描述称其为不稳定的算法，不知为何不稳定，望高手能予指点，谢谢！！