安卓软件制作网站,网站ui设计之道,专业做图表的网站,网站建设情况调研报告目录
1.插入排序
插入排序的时间复杂度#xff1a;
2.希尔排序
希尔排序的时间复杂度#xff1a;
3.选择排序
选择排序的时间复杂度#xff1a; 所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的…目录
1.插入排序
插入排序的时间复杂度
2.希尔排序
希尔排序的时间复杂度
3.选择排序
选择排序的时间复杂度 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。排序在生活中的作用很大例如某宝中的价格排行榜、销量排行榜国内外的财富排行榜、院校排行榜等等都是使用排序完成的。
下面我们看看常见的排序都有哪些 1.插入排序 基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 插入排序的过程如下 假设我们有如下一个数组 具体实现代码如下 while (end 0)
{//挪数据if (tmp a[end]){a[end 1] a[end];end--;}else{break;}
}
//交换数据
a[end 1] tmp; tmp中存放的是33小于1010往后挪一位3小于5,5往后挪一位......当end到2时tmp小于2退出循环此时5 7 10都已经往后挪了一位数组中的元素应该是2 5 5 7 10我们把tmp中存放的3和2后面的5交换即可。 以上只是一个数据的插入排序要实现整个数组的排序我们需要对数组的每个数据都往前插入排序一下 void InsertSort(int* a, int n)
{for (int i 1; i n; i){int end i - 1;int tmp a[i];while (end 0){if (tmp a[end]){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
} 插入排序的时间复杂度
假设我们要排升序当要排的数据刚好是降序时时间复杂度最大为O(N^2)因为此时排序的次数是等差数列。
当要排的数据刚好是升序的时候是最好的情况时间复杂度最小但是我们在排之前并不知道数据是升序所以至少要排N次时间复杂度为O(N)。
总结一下 时间复杂度最好O(N^2) 时间复杂度最坏O(N) 而我们之前学过的冒泡排序时间复杂度是O(N^2)所以插入排序优于冒泡排序。
2.希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有数据分成n/gap个组所有距离为gap的数据分在同一组内并对每一组内的数据进行排序最后再进行一次gap1的分组和排序。 希尔排序有两个过程 1. 预排序 -- 使接近有序。 2. 插入排序 即先进行预排序是数据接近有序然后使用一次插入排序使数据有序。希尔排序实际就是对插入排序的优化。 预排序 下面我们先来对红色组进行排序 for (int i 0; i n - gap; igap)
{int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end end - gap;}else{break;}}a[end gap] tmp;
} 注意下标 i 不能越界所以 i n - gap。 以上代码只能完成对红色组的排序下面我们来将三个组都排好序 只需在外面再加一层循环即可。 for (int j 0; j gap; j)
{for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end end - gap;}else{break;}}a[end gap] tmp;}
} 这样三组数据都排好序完成了预排序但是上述代码有似乎还可以简化 for (int 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 end - gap;}else{break;}}a[end gap] tmp;
} 只需将igap改为i即可当igap时我们是将三组分开排序的先排完红色组再排蓝色组最后排绿色组而当i时我们是多组并排的方式这样明显效率更高。 插入排序 以上就是预排序的过程预排序完数据变成了1 02 3 3 4 6 5 7 9 8还需要一次插入排序现在我们先来思考一个问题gap的值只能给3吗 当然不是gap可以任意给值只不过给的值不同预排序出来的数据次序就不同。 我们可以令gapngapgap/31 这样每次使用的gap都在变化而且能确保最后一次的gap一定是1也就确保了最后一次一定进行的是插入排序。 最终代码如下 void ShellSort(int* a, int n)
{//gap 1 预排序//gap 1 直接插入排序int gap n;while (gap 1){gap gap / 3 1;for (int 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;}}
} 希尔排序的时间复杂度
希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定
《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 3.选择排序 基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 选择排序过程如下图所示 上图中是把待选数据遍历一遍每次选出最小的数据放在前面其实我们可以对其优化一下把待选数据遍历一遍每次同时选出最大和最小的数据把最小的数据放在前面最大的数据放在后面。 代码如下 void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;int mini begin;int maxi end;while (beginend){for (int i begin; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);Swap(a[end], a[maxi]);begin;end--;}
} 问题来了上述代码对吗 运行一下就会发现 诶不对啊那到底哪里出错了呢 下面我们举个极端的例子 经过遍历以后发现最大数的下标maxi和begin重合了那我们交换时就出现问题了最小数0确实放在了前面但是最大数的位置也变了下面再想把最大数放在后面此时的下标就不能再用了所以我们在交换a[begin]和a[mini]的值后要将最大数的下标更改: void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int mini begin;int maxi end;for (int i begin; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);//如果发生重叠就更改下标if (begin maxi){maxi mini;}Swap(a[end], a[maxi]);begin;end--;}
} 选择排序的时间复杂度 选择排序的时间复杂度很简单就是O(N^2)它每排一个数据都要遍历后面的数据一遍遍历次数是等差数列前面的章节中学过等差数列的时间复杂度是O(N^2)虽然上述的代码进行优化将遍历次数减半为N^2/2但是量级没变还是O(N^2)。 今天就学习这三种排序冒泡排序、堆排序在之前的章节中已经讲解过下节我们继续学习快速排序和归并排序未完待续。。。
