基础排序算法详解与优化
文章图片存储在github
,网速不佳的朋友,请看 或者 来我的技术小站
1. 谈谈基础排序
常见的基础排序有选择排序、冒泡排序和插入排序。众所周知,他们的时间复杂度是 o(n*n)。
但是,现在要重新认识一下基础排序算法,尤其是“插入排序”:在近乎有序的情况下,插入排序的时间复杂度可以降低到 o(n)的程度。
因此,在处理系统日志的任务中,因为日志记录是按照时间排序,但偶尔会有几条是乱序,此时使用插入排序再好不过。而对于高级排序算法,一个常见的优化就是利用插入排序做局部数据排序优化。
2. 算法实现
排序算法被封装在了sortbase.h
中的sortbase
命名空间中,以实现模板化和防止命名冲突。如下图所示:
2.1 选择排序
假设从小到大排序,那么,刚开始指针指向第一个数据,选择从当前指针所指向数据到最后一个数据间最小的数据,将它放在指针位置。
指针后移一位,重复上述步骤,直到指针移动到最后一个数据。
这种重复保证了每次,指针前面的数据都是从小到大排好顺序的数据。所以,从头到尾扫描一遍,自然排好序了。
代码如下:
template <typename t> void selectionsort(t arr[], int n) { int minindex = -1; for(int i = 0; i < n; i++) { minindex = i; for(int j = i+1; j < n; ++j) { if(arr[j] < arr[minindex]) { minindex = j; } } swap(arr[i], arr[minindex]); } }
2.2 冒泡排序
假设排序是从小到大排序。
我一直感觉冒泡排序是和选择排序反过来了(如果说错请指正)。因为选择排序是每次选择最小的数据,放到当前指针位置;而冒泡排序是把不停交换相邻数据,直到把最大的数据“冒泡”到应该到的位置。
优化的地方是:记录每次交换的最后位置,在此之后的元素在下一轮扫描中均不考虑。因为交换的最后位置之后的元素已经是从小到大排序好了的。
在实现过程中,因为需要不停交换相邻两个数据,因此,消耗了很多额外时间。
template <typename t> void bubblesort(t arr[], int n) { int newn; do { newn = 0; for(int i = 1; i < n; i++) { if(arr[i-1] > arr[i]) { swap(arr[i-1], arr[i]); // 优化 newn = i; } } n = newn; // 不再考虑 newn 后的数据 } while (newn > 0); }
2.3 插入排序
插入排序容易和上面两个算法搞混。可以类比打扑克牌时候的对扑克牌进行排序:我们会先排序前 1 张、然后是前 2 张、前 3 张 ... 一直到前 n 张。算法实现显然是双重循环,如下所示:
template <typename t> void insertionsort(t arr[], int n) { for(int i = 1; i < n; i++) { for(int j = i ; j > 0; j--) { if(arr[j - 1] > arr[j]) { swap(arr[j], arr[j - 1]); } else { break; // 优化:已经保证之前都是正常排序,直接跳出即可 } } } }
显然,插入排序也能在局部排好序的情况下跳出循环(代码中的优化),以减少算法消耗时间。
然而上述算法其实跑分并比不上选择排序,因为swap(arr[j], arr[j - 1]);
这行代码交换了一次,相当于赋值 3 次,在大数据量情况下,比较消耗时间。
优化: 内层循环,每次保存arr[i]
, 在检测到当前数据大于arr[i]
的时候,后移一位当前元素arr[j] = arr[j-1];
。当跳出内层循环时,直接将保存的arr[i]
赋值给arr[j]
即可。
template <typename t> void insertionsort(t arr[], int n) { for(int i = 1; i < n; i++) { t e = arr[i]; int j = i ; for(; j > 0 && arr[j-1] > e; j--) { arr[j] = arr[j-1]; } arr[j] = e; } }
3. 性能测试
首先利用 sorttesthelper::generaterandomarray
函数生成大量无序随机数据,然后进行排序和时间测定。代码如下:
#include <iostream> #include "sorthelper.h" #include "sortbase.h" #include "sortadvance.h" using namespace std; int main() { int n = 50000, left = 0, right = n; int *arr = sorttesthelper::generaterandomarray<int>(n, left, right); int *brr = sorttesthelper::copyarray<int>(arr, n); int *crr = sorttesthelper::copyarray<int>(arr, n); sorttesthelper::testsort<int>(arr, n, sortbase::selectionsort<int>, "selection sort"); sorttesthelper::testsort<int>(brr, n, sortbase::insertionsort<int>, "insertion sort"); sorttesthelper::testsort<int>(crr, n, sortbase::bubblesort<int>, "bubble sort"); delete[] brr; delete[] arr; delete[] crr; return 0; }
运行结果如下图所示:
除了大量无序随机数据,类似于系统日志的数据就是基本有序的大量数据。此时,测试代码如下:
#include <iostream> #include "sorthelper.h" #include "sortbase.h" #include "sortadvance.h" using namespace std; int main() { int n = 50000, left = 0, right = n; int *arr = sorttesthelper::generatenearlyorderedarray<int>(n, 10); int *brr = sorttesthelper::copyarray<int>(arr, n); int *crr = sorttesthelper::copyarray<int>(arr, n); sorttesthelper::testsort<int>(arr, n, sortbase::selectionsort<int>, "selection sort"); sorttesthelper::testsort<int>(brr, n, sortbase::insertionsort<int>, "insertion sort"); sorttesthelper::testsort<int>(crr, n, sortbase::bubblesort<int>, "bubble sort"); delete[] brr; delete[] arr; delete[] crr; return 0; }
如图所示,插入排序的只用了 0.002 秒。在这种数据情况下,插入排序的时间复杂度近似 o(n),绝对快于高级排序的 o(nlogn)。除此之外,还保证了稳定性。
4. 感谢
本篇博客是总结于慕课网的的笔记,liuyubobobo 老师人和讲课都很 nice,欢迎去买他的课程。
5. 更多内容
- 快速排序和归并排序:
- 堆与堆排序:
上一篇: 三星的可折叠手机产品好事将近 预计今年现身明年上市
下一篇: List排序方法