加强企业网站建设的通知,淘宝网站做淘宝客,自建站怎么搭建,wordpress底部footer欢迎来到繁星的CSDN#xff0c;本期的内容主要包括冒泡排序(BubbleSort#xff09;#xff0c;直接插入排序(InsertSort)#xff0c;以及插入排序进阶版希尔排序#xff08;ShellSort#xff09;。 废话不多说#xff0c;直接上正题#xff01;
一、冒泡排序 冒泡排序… 欢迎来到繁星的CSDN本期的内容主要包括冒泡排序(BubbleSort直接插入排序(InsertSort)以及插入排序进阶版希尔排序ShellSort。 废话不多说直接上正题
一、冒泡排序 冒泡排序是我们的老朋友了我们最初模拟实现qsort的时候就是用它来模拟的尽管qsort的底层原理实际是quicksort即快排。 上代码
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){// 单趟int flag 0;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);flag 1;}}if (flag 0){break;}}
} 代码相当简单其思想就是通过两两之间的比较每一趟都将最大的数据放在数组的最后。 缺点是冒泡排序的速度相当慢原因不仅仅在于比较的次数恒定n*(n1)/2次)更在于如果数据量庞大各个数据移动的速度也相当慢。 实际意义聊胜于无但却很好地帮我们入门各大排序算法这是它仍然活跃的意义。 二、直接插入排序 我们一般会叫它插入排序在此加入“直接”二字是为了区分它和希尔排序。 插入排序的思路也是较为简单的。 面对一个有n个元素的数组如果前n-1个元素都有序那么第n个元素通过和前面所有元素比较就能得到该元素在数组中的位置。有一点数学归纳法的思想在里面。 上代码
void InsertSort(int* a, int n)
{// [0, n-1]for (int i 0; i n - 1; i){// [0, n-2]是最后一组// [0,end]有序 end1位置的值插入[0,end]保持有序int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
} 由于一个元素一定有序所以第一个元素不用排序。而从第二个元素开始通过比较不断插入到前面的数组中使前n项都有序如此往复便可使得整个数组有序。 相比于冒泡排序插入排序少了大量重复的交换数值的工作而是一步到位得到数据的最终位置尽管时常需要将所有数据后移但代码中只是赋值而非交换效率比冒泡高的多。 两者运行时间差别 此处数据为10000个 尽管如此我们在实际工作中也很少使用直接插入排序即使时间比冒泡排序少的多其时间复杂度仍为O(n^2)。但不得不指出它仍有应用后续在快排的时候将会提到。
三、希尔排序 希尔排序是插入排序的优化版本优化到可以和快速排序一较高下。 希尔排序主要做两件事1、预排序。2、插入排序。 由插入排序的代码可知当数组越趋近于有序比较和赋值的次数也越来越少。所以预排序的目的就是使得整个数组接近有序。 上代码
void ShellSort(int* a, int n)
{int gap n;while (gap 1){// 1保证最后一个gap一定是1// gap 1时是预排序// gap 1时是插入排序gap gap / 3 1;for (size_t i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
} 要点解释 1、gap代表的含义是下标相减为gap的元素为一组进行插入排序。此举的意义是使得On^2)的复杂度造成的影响尽可能小因为a*(n/a)^2小于n^2a为任意整数。 2、而当gap等于1时再进行排序就是插入排序了。 3、gap的大小实际上由写代码的人自己决定没有一定gap越大或者gap越小的效果最好但可以确定的是经过预排序的插排会比直接插排要更快。 4、上述代码中的gap是一个效果较好的gap可以参照并直接使用。 本篇内容到此结束谢谢大家的观看 觉得写的还不错的可以点点关注收藏和赞一键三连。 我们下期再见~ 往期栏目 一文带你入门二叉树-CSDN博客 栈和队列的介绍与实现-CSDN博客 设计扫雷游戏_扫雷游戏设计-CSDN博客
