在上节博客中,我们学习了插入排序和选择排序,那么本次我们继续学习冒泡排序和希尔排序。什么是冒泡排序呢?它是每次从后向前进行(假设为第 i 次),j = n - 1, n - 2, ... , i, 两两比较 V[j-1] 和 V[j] 的关键字;如果发生逆序,则交换 V[j-1] 和 V[j]。下来我们看看第 i 次冒泡排序示例,如下图所示
我们来看看具体是怎么实现的,如下所示
我们看到它是两两比较,小的放在前面。类似于冒水泡,轻的漂浮在上面。下来我们来看看具体源码的实现
template < typename T > static void Bubble(T array[], int len, bool min2max = true) { bool exchange = true; for(int i=0; (i<len) && exchange; i++) { exchange = false; for(int j=len-1; j>i; j--) { if( min2max ? (array[j] < array[j-1]) : (array[j] > array[j-1]) ) { Swap(array[j], array[j-1]); exchange = true; } } } }
测试代码如下
#include <iostream> #include "Sort.h" using namespace std; using namespace DTLib; int main() { int array[] = {3, 2, 4, 1, 5}; Sort::Bubble(array, 5); for(int i=0; i<5; i++) { cout << array[i] << endl; } }
我们来看看运行结果
我们来试试在 Bubble 后面加上 false 参数,看看效果
下来我们来继续看看希尔排序,那么它的基本思想是什么呢?将待排序列划分为若干组,在每一组内进行插入排序,以使整个序列基本有序,然后再对整个序列进行插入排序。希尔排序示例如下
我们来看看具体是怎么实现的,如下所示
它是利用插入排序来实现的,之所以这么实现,是因为这样的效率比之前的几种能高点。下来我们来看看具体源码的实现
template < typename T > static void Shell(T array[], int len, bool min2max = true) { int d = len; do { d = d / 3 + 1; // 之所以这样写是因为经过数学推导,这样的效率是最高的。也可以写成 d--; for(int i=d; i<len; i+=d) { int k = i; T e = array[i]; for(int j=i-d; (j>=0) && (min2max ? (array[j]>e) : (array[j]<e)); j-=d) { array[j+d] = array[j]; k = j; } if( k != i ) { array[k] = e; } } } while( d > 1 ); }
我们先来看看不加参数 false的效果(从小到大排序)
再来看看从大到小的排序
我们看到已经正确实现了。通过对冒泡排序和希尔排序的学习,总结如下:1、冒泡排序每次从后向前将较小的元素交互到位;2、冒泡排序是一种稳定的排序方法,其复杂度为O(n2);3、希尔排序通过分组的方式进行多次插入排序,它是一种不稳定排序,其复杂度为O(n3/2)。
网页名称:冒泡排序和希尔排序(三十一)-创新互联
网站链接:https://www.cdcxhl.com/article6/eoeog.html
成都网站建设公司_创新互联,为您提供品牌网站制作、商城网站、定制开发、外贸网站建设、服务器托管、网站策划
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联