测试代码文件 ----注释为数据时间结论 1 #include " pch.h " 2 #include " sort.h " 3 #include iostream 4 #includectime 5 #includerandom 6 #includealgorithm 7 #includefunctional 8 #includeiomanip 9 using namespace std; 10 bool tes
测试代码文件 ----注释为数据时间结论
1 #include"pch.h" 2 #include"sort.h" 3 #include <iostream> 4 #include<ctime> 5 #include<random> 6 #include<algorithm> 7 #include<functional> 8 #include<iomanip> 9 using namespace std; 10 bool test() 11 { 12 13 14 const int num = 10000; 15 int ori[num]; 16 int answer[num]; 17 for (int i = 0; i < num; i++) 18 { 19 ori[i] = rand() % 1000; 20 answer[i] = ori[i]; 21 } 22 /*cout << "原队列： "; 23 for (auto i : ori) 24 cout << i << ‘ ‘; 25 cout << endl;*/ 26 27 std::sort(answer, answer + num); 28 /*cout << "正确队： "; 29 for (auto i : answer) 30 cout << i << ‘ ‘; 31 cout << endl;*/ 32 33 34 //quicksort(ori,sizeof(ori)/sizeof(int)); //2s 35 //selectsort(ori, sizeof(ori) / sizeof(int)); //14s 比想象中差 36 //mergesort(ori, sizeof(ori) / sizeof(int)); //2s~3s 37 //insertsort(ori, sizeof(ori) / sizeof(int)); //8s 38 //bubblesort(ori, sizeof(ori) / sizeof(int)); //29s 大数组下效率奇差 39 //hsort(ori, sizeof(ori) / sizeof(int)); //2s 40 heapsort(ori, sizeof(ori) / sizeof(int)); //3~4s由于运行环境不同，开的程序多了， 41 //且加了接口，没有直接映射故应该跟merge一个档次
//以前测试过，heapsort比较交换次数比直接insert小很多
42 43 /*cout << "后队列： "; 44 for (auto i : ori) 45 cout << i << ‘ ‘; 46 cout << endl;*/ 47 48 //校对 49 bool a = true; 50 for (int i = 0; i < num; i++) 51 { 52 if (ori[i] != answer[i]) 53 { 54 a = false; 55 break; 56 } 57 } 58 if (!a) 59 { 60 exception e("排序错误"); 61 throw e; 62 } 63 return a; 64 65 } 66 void testSortWithTime() 67 { 68 69 clock_t start, finish; 70 start = clock(); 71 //随机数种子为定值，保证了各个排序的所有测试数据都是一样的 72 srand(time(NULL)); 73 int i = 100; 74 try { 75 while (--i) 76 { 77 78 test(); 79 } 80 } 81 catch (exception e) 82 { 83 cout << e.what() << endl; 84 } 85 finish = clock(); 86 double total = (finish - start) / CLOCKS_PER_SEC; 87 if (!i) 88 cout << "程序正确执行 " << endl; 89 else 90 { 91 cout << "程序未能正确执行 " << endl; 92 } 93 cout << "耗时\t" << total << " second" << endl; 94 return; 95 }
通用头文件
1 #pragma once 2 3 void selectsort(int *p, int num); 4 5 void Qsort(int *p, int low, int high); 6 void quicksort(int * p, int count); 7 8 9 void msort(int *p, int head1, int tail1, int head2, int tail2); 10 void mesort(int *p, int head, int tail); 11 void mergesort(int *p, int num); 12 13 void insertsort(int *p, int num); 14 15 void bubblesort(int *p, int num); 16 17 18 void hsort(int *p,int num); 19 void heapsort(int*p,int num); 20 21 //测试函数 22 bool test(); 23 void testSortWithTime();
1.插入排序
1 #include"pch.h" 2 #include"sort.h" 3 void insertsort(int *p, int num) 4 { 5 if (p == nullptr || num < 2)return; 6 7 8 for (int i = 1; i < num; i++) 9 { 10 int temp = p[i]; 11 int j = i ; 12 for (; j > 0; ) 13 { 14 15 //必须用原来的数值，也就是temp进行比较，而非p【j】 16 if (temp < p[j - 1]) 17 { 18 p[j] = p[j - 1]; 19 --j; 20 } 21 else break; 22 } 23 if (j != i) 24 { 25 p[j] = temp; 26 } 27 } 28 }
2.冒泡排序-------每次排序就是一个最重（大）的元素下落，与其说冒泡，数组大时效率极低（即使每轮有结束的机会），不如说是低端的选择排序，
好歹选择排序（同样是选一个元素，不过是选择最小的罢了，挡板在前）才交换一次，冒泡排序交换多次，挡板移动
1 #include"pch.h" 2 #include"sort.h" 3 void bubblesort(int *p, int num) 4 { 5 int temp; 6 int time; 7 8 //i为次轮将要排序的挡板，即次轮排序结束后，i不参与下轮比较 9 for (int i = num - 1; i > 0; --i) 10 { 11 time = 0; 12 //j<=i 即i此论是要比较的 13 for (int j = 1; j <=i; j++) 14 { 15 if (p[j] < p[j - 1]) 16 { 17 temp = p[j]; 18 p[j] = p[j - 1]; 19 p[j - 1] = temp; 20 ++time; 21 22 } 23 24 } 25 if (!time)break; 26 } 27 }
3.选择排序--------------------------挡板在前，没回选一个最小的固定其位置，然后移动挡板，与冒泡排序不同的地方，可能就输在数组大致有序时，
冒泡可以强行结束（冒泡排序在完全反序时效率感人肺腑）
1 #include"pch.h" 2 #include"sort.h" 3 4 void selectsort(int *p, int num) 5 { 6 7 int temp, min; 8 for (int i = 0; i < num - 1; i++) 9 { 10 min = i; 11 for (int j = i + 1; j < num; j++) 12 { 13 if (p[min] > p[j]) 14 min = j; 15 } 16 if (min != i) 17 { 18 temp = p[min]; 19 p[min] = p[i]; 20 p[i] = temp; 21 } 22 23 } 24 }
4.希尔排序
原理可以视为多趟的插入排序，与插入排序不同的是，插入排序一次元素移动只会减少一点无序度（因为其是相邻交换），而希尔排序可能
会降低多点无序度（因为跨度不一样，也因为跨度不一样，所以其是不稳定排序的），每次希尔排序都选择一个跨度，直至为1则停止。希尔排序skip数组的要求是
逐个降低，且出1意外，任意俩个数的乘积不等于第三个数，最好连最大公因数都维持为1，减少没必要的排序。
1.选择跨度进行单跨度为skip的插入排序
2.单跨度插入排序，跨度为skip
2.1）选择开始元素start，进行从0开始，到跨度大小即结束（不要等于大于skip，因为没有意义，重复排序了，如选择了start=skip+1，那么选择start=1完成的时候，start=skip+1就已经是有序的）
2.2）选择start后，注意skip的大小进行跨步递增，也要注意跨步递减（防止越界为负数，这跟插入排序是一样的，只不过插入排序默认0为边界，而希尔排序的每次插入排序是动态边界），
3.但跨度的插入排序后，选择下一个skip，进行排序，直至结束
PS：希尔排序的效率很大程度上取决于skip数组，必须递减（否则没意义），无最小公因数，以减少无意义比较，其为不稳定排序，某种程度上说，乱序越能体现其速度
1 #include"pch.h" 2 #include"sort.h" 3 void hsort(int *p, int num) { 4 //跨步数组必须有序，且最后必须为1,最好使得数组内除了1以外的成员间 5 //任意俩者的乘积不等于第三者 6 if (p == nullptr)return; 7 int skip_arry[] = { 1,2,3,5,7,11 }; 8 int size = sizeof(skip_arry) / sizeof(int); 9 int skip; 10 for (int i=size-1;i>=0;--i) 11 { 12 skip = skip_arry[i]; 13 //检测跨步，进行剪枝 14 if (skip >= num)continue; 15 16 //size趟跨步为skip的插入排序 17 //j<k的原因是，当j=skip时，以0开头的skip跨步的结果， 18 //就已经使得以skip开头skip跨步的序列变成有序，故没必要 19 20 21 //以下进行的是以j为起点，跨步为skip的插入排序 22 for (int j = 0; j < skip ; j++) 23 { 24 25 // 26 for (int k=skip+j; k < num; k += skip) 27 { 28 int temp = p[k]; 29 int h = k; 30 //懒得用for，while比较干脆 31 //h不可能小于j，等于j时立刻停止 32 //一般插入排序将j作为0的原因是，0就是边界，这时需要调整 33 while (h > j) 34 { 35 if (temp < p[h - skip]) 36 { 37 p[h] = p[h - skip]; 38 h -= skip; 39 } 40 else break; 41 42 }//end while 43 if (h != k) //插入的元素位置发生了变换 44 { 45 p[h] = temp; 46 } 47 }//end 以下进行的是以j为起点，跨步为skip的插入排序 48 49 }//end 跨步skip_array[i] 50 51 }//end sort 52 }
5.归并排序
new俩个数组，递归对其使用归并，直至这俩个数组是有序时返回；然后合并，非长简单，且是稳定排序（只要传入的头一个位置在相等时优先插入有序队列即可），但需要一定的内存空间
理论上下面的算法实现可以进行优化，下面的算法实现是new左右俩边数组大小后再进行递归调用，排序归并使得其有序，
以下代码实际上在最大占用时，占用了约2倍原数组内存空间用以存数（1+0.5+0.25+0.125+........），而实际上可以减少到1倍的原数组内存空间占用（0.5+0.25+0.125+0.0625.....），
因为其是分步的，左边有序化时，右边并没有卵用，可以不new，减少最大内存占用峰值
为先new左边数组大小，调用递归，使其有序----new右边数组大小，调用递归，使得右边有序-----------归并俩个数组，使其有序
1 #include"pch.h" 2 #include"sort.h" 3 /**********************************************************************************************************************************************************************/ 4 5 /* 6 归并排序主要是有序序列的合并和无序数列的二分递归 7 传递实际下标，有利于直接进行逻辑思考 8 使用双链表，浪费了多一个指针，但是不用下标计算来计算去，考虑越界也比较简单 9 */ 10 11 //采用实际下标进行传值 12 void msort(int *p, int head1, int tail1, int head2, int tail2) 13 { 14 int x = tail1 - head1 + 1; 15 int y = tail2 - head2 + 1; 16 int *p1 = new int[x]; 17 int *p2 = new int[y]; 18 for (int i = 0; i < x; i++) 19 { 20 p1[i] = p[head1 + i]; 21 } 22 for (int j = 0; j < y; j++) 23 { 24 p2[j] = p[head2 + j]; 25 } 26 27 int i = 0; 28 int j = 0; 29 int k = head1; 30 31 32 while ((i < x) && (j < y)) 33 { 34 if (p1[i] < p2[j]) 35 { 36 p[k] = p1[i]; 37 ++i; 38 ++k; 39 } 40 else 41 { 42 p[k] = p2[j]; 43 ++j; 44 ++k; 45 } 46 } 47 48 49 //归并余下 50 if (i == x) 51 { 52 for (; j < y;) 53 { 54 p[k] = p2[j]; 55 ++k; 56 ++j; 57 } 58 } 59 else 60 { 61 for (; i < x;) 62 { 63 p[k] = p1[i]; 64 ++k; 65 ++i; 66 } 67 68 } 69 delete[]p1; 70 delete[]p2; 71 72 } 73 74 //对一段数列进行排序并归并 75 void mesort(int *p, int head, int tail) 76 { 77 if (head >= tail)return; 78 79 //防止越界 80 int mid = head + (tail - head) / 2; 81 82 83 mesort(p, head, mid); 84 mesort(p, mid + 1, tail); 85 msort(p, head, mid, mid + 1, tail); 86 87 } 88 89 90 // 用做排序统一接口 91 void mergesort(int *p, int num) 92 { 93 mesort(p, 0, num - 1); 94 }
6.堆排序
以下排序习惯了不用0元素作为开始元素，因为这样方便计算，用0元素要进行相应的二叉树对应子树映射，非常麻烦，故如果实在是0地址有元素，则申请内存进行简单搬移搞定
当然也可以用脑子去映射（我大概没有这玩意），也可以黑科技，不对0位置的元素进行排序，排序完成后1-n是有序的，进行一次插入排序，移动0位置的元素即可（最恶劣情况可能移动n次）
1 #include"pch.h" 2 #include"sort.h" 3 4 void adjust(int *p, int place, int num) 5 { 6 if (p == nullptr)return; 7 int left = 2 * place; 8 if ( left > num)return; 9 int righ = left + 1; 10 if (righ > num) 11 { 12 if (p[place] < p[left]) 13 { 14 int temp = p[place]; 15 p[place] = p[left]; 16 p[left] = temp; 17 adjust(p,left,num); 18 } 19 return; 20 } 21 else 22 { 23 int max = (p[left]>p[righ]?left:righ); 24 if (p[place] < p[max]) 25 { 26 int temp=p[place]; 27 p[place] = p[max]; 28 p[max] = temp; 29 adjust(p,max,num); 30 } 31 return; 32 } 33 34 } 35 void realheapsort(int *p,int num) 36 { 37 //为了方便计算，这里是num实际上是表示数组的最大下标； 38 //且以下标1开始 39 //just a interface 40 41 int mid = (1 + num) / 2; 42 for (int i = mid; i >= 1; --i) 43 { 44 adjust(p, i, num); 45 } 46 int temp; 47 while (num > 1) 48 { 49 temp = p[num]; 50 p[num] = p[1]; 51 p[1] = temp; 52 --num; 53 adjust(p, 1, num); 54 } 55 return; 56 } 57 void heapsort(int *p, int num) 58 { 59 int *pp = new int[num + 1]; 60 for (int i = 0; i < num; i++) 61 { 62 pp[i + 1] = p[i]; 63 } 64 realheapsort(pp, num); 65 for (int i = 0; i < num; i++) 66 { 67 p[i] = pp[i+1]; 68 } 69 delete[]pp; 70 return; 71 72 73 }
7.快速排序
快速排序排序后，浮标元素左边是恒小于等于他，右边恒大于等于他，其效率很大程度取决与一开始的浮标元素选取，如果是在待排序数组内位于中间值，那么就能减少排序次数，
而下面的代码为了省事，直接选第一个作为浮标，然后直接从后面进行排序。可以多值取中后（任选多个值，取得一个中间值），将其与第一位元素交换，在进行快速排序，减少比较交换次数
由于 浮标元素左边是恒小于等于他，右边恒大于等于他 ，那么浮标经过一次快速排序过程后，其在整个序列中就是“”相对位置有序的“”，因此，其下标n就是代表其整个序列的第n+1位元素，
可以用来在算法题中快速得出第n位元素
1 #include "pch.h" 2 #include"sort.h" 3 4 void Qsort(int *p, int low, int high) 5 { 6 if (low >= high)return; 7 int point = low; 8 int temp = p[point]; 9 int nlow = low; 10 int nhigh = high; 11 while (low < high) 12 { 13 14 while (low < high) 15 { 16 //必须设置为>=不然，在重复序列中，其会无限循环 17 // p[mid]=p[low]=p[high] ,三个无限互换 18 if (p[high] >= temp) 19 --high; 20 else break; 21 } 22 p[point] = p[high]; 23 point = high; 24 25 26 while (low < high) 27 { 28 if (p[low] <= temp) 29 ++low; 30 else break; 31 } 32 p[point] = p[low]; 33 point = low; 34 35 36 } 37 p[point] = temp; 38 Qsort(p, nlow, point - 1); 39 Qsort(p, point + 1, nhigh); 40 41 42 } 43 44 void quicksort(int * p, int count) 45 { 46 Qsort(p, 0, count - 1); 47 }