专业做网站较好的公司,wordpress 页眉修改,阿里云 win wordpress 伪静态,WordPress公众号扫码登录文章目录 8.内部排序(上)(1).排序基础#1.为什么是内部排序#2.排序的稳定性 (2).冒泡排序#1.算法思想#2.代码实现#3.稳定性与时间复杂度分析 (3).选择排序#1.算法思想#2.代码实现#3.稳定性与时间复杂度分析 (4).插入排序#1.算法思想#2.代码实现#3.稳定性与时间复杂度分析 (5).希… 文章目录 8.内部排序(上)(1).排序基础#1.为什么是内部排序#2.排序的稳定性 (2).冒泡排序#1.算法思想#2.代码实现#3.稳定性与时间复杂度分析 (3).选择排序#1.算法思想#2.代码实现#3.稳定性与时间复杂度分析 (4).插入排序#1.算法思想#2.代码实现#3.稳定性与时间复杂度分析 (5).希尔排序#1.算法思想#2.代码实现#3.稳定性和时间复杂度分析 小结 8.内部排序(上) 所以其实学会对一组数据进行排序是我们很自然的想法比如我们在玩扑克牌的时候随机摸了一组牌为了之后打起来方便你可能也会按照花色和数字进行排序所以让我们来了解一下排序吧
(1).排序基础
#1.为什么是内部排序 与内部排序相对的就是外部排序在数据量极其庞大的情况下我们可能无法一次性将待排序的数据全部载入内存再排序而这种涉及到内存与外存数据交换的排序方式就称为外部排序与之相对的就是内部排序我们可以很简单的一次性把所有数据载入内存用各种方式完成排序。 外部排序的流程比较复杂因此基于数据结构这门课的这系列博客当中我们会简要介绍内部排序的基本内容。
#2.排序的稳定性 排序算法是具有稳定性的说法的在待排序的数据当中基于排序规则相同的一系列数据如果能在排序完成后保持原有的顺序则称这种排序算法是稳定的 例如5, 1, 2(1), 4(1), 4(2), 2(2), 4(3)稳定排序的结果应当是1,2(1), 2(2), 4(1), 4(2), 4(3), 5
(2).冒泡排序
#1.算法思想 冒泡排序是相当自然的排序方法假设从小到大排序我们从左往右依次比较相邻的元素如果满足左边小于等于右边就继续比较下面两个元素如果顺序错误则交换两个元素继续交换
#2.代码实现 如此继续下去可以保证每轮都能找出一个最大值并且将它放在最后这样的过程就好像一个个泡泡从水底逐渐冒到了水面上故称为冒泡排序它的代码实现如下
#include iostream
#include vector
using namespace std;void bubble_sort(vectorint v)
{bool isSort{ false };for (int i v.size() - 1; i 0; i--) {for (int j 0; j i; j) {if (v[j] v[j 1]) {int tmp{ v[j 1] };v[j 1] v[j];v[j] tmp;isSort true;}}if (!isSort) break;}
}int main()
{vectorint v{ 3, 2, 3, 5, 6, 7, 8, 9, 1, 23 };bubble_sort(v);for (auto i : v) {cout i ;}cout endl;return 0;
}#3.稳定性与时间复杂度分析 我们每次将冒泡的上界减一然后每次再找到位置错误的进行交换一直这样循环下去即可。接下来分析一下冒泡排序的时间复杂度我们有两重循环可以得到 T ( n ) ∑ k 1 n ( n − k ) n ( n − 1 ) 2 ⇒ O ( T ( n ) ) O ( n 2 ) T(n) \sum_{k1}^n (n-k) \frac{n(n-1)}{2}\Rightarrow O(T(n))O(n^2) T(n)k1∑n(n−k)2n(n−1)⇒O(T(n))O(n2) 所以冒泡排序是比较基本的 O ( n 2 ) O(n^2) O(n2)排序算法然后是稳定性其实这个好说因为在冒泡排序中我们只涉及到前后两个顺序错误元素的交换因此相同的元素在这个过程中是不会被交换的所以冒泡排序是一种稳定的排序方式。
(3).选择排序
#1.算法思想 选择排序则要更接近我们自己尝试排序的过程比如3, 2, 3, 5, 6, 7, 8, 9, 1, 23这个序列我们首先找到最小值1放到最前面1, 3, 2, 3, 5, 6, 7, 8, 9, 23然后从1后取第二个最小值放到第二个位置1, 2, 3, 3, 5, 6, 7, 8, 9, 23然后就这么做下去吧每次找出最小值或者最大值放到上一次放的下一个位置就可以完成整个排序流程了这就是插入排序。
#2.代码实现 每次选择一个最小或最大的值出来放到头或尾去因此这个算法称为选择排序。
#include iostream
#include vector
using namespace std;void selection_sort(vectorint v)
{for (int i 0; i v.size() - 1; i) {int min_idx{ i };for (int j i 1; j v.size(); j) {if (v[min_idx] v[j]) {min_idx j;}}int tmp{ v[i] };v[i] v[min_idx];v[min_idx] tmp;}
}int main()
{vectorint v{ 3, 2, 3, 5, 6, 7, 8, 9, 1, 23 };selection_sort(v);for (auto i : v) {cout i ;}cout endl;return 0;
}这段代码主要也就做了两件事找后续值的最小值以及放到对应的位置上去。
#3.稳定性与时间复杂度分析 还是先看看时间复杂度吧这里就不推了其实还是和冒泡排序相似的过程选择排序的时间复杂度仍然是 O ( n 2 ) O(n^2) O(n2)所以我们想要突破 O ( n 2 ) O(n^2) O(n2)的时间复杂度好像非常困难啊。 然后是稳定性选择排序实际上是一种不稳定的排序方式比如我们前面写的代码对于这个序列1, 2, 3, 2, 1当i走到1的时候2会与后面的1进行一次交换而这样做之后就破坏了原本两个2的顺序这样就导致选择排序变得不稳定了起来比如
(4).插入排序
#1.算法思想 插入排序在我们玩扑克牌的时候比较常用比如我们拿到了一副牌A,7,4,2,Q,9,J那我们可能会这么排首先A不动看到7也不动再到4插到A和7之间再把2插入A和4之间就这么做下去直到变成A,2,4,7,9,J,Q这样的顺序这就是插入排序我们依次向后遍历然后找到对应元素在前面已经有序的序列中的位置插入进去这就是插入排序的基本流程
#2.代码实现 我们这里把找到合适的位置和移动合在一起可以减少一次遍历的开销
#include iostream
#include vector
using namespace std;void insertion_sort(vectorint v)
{for (int i 1; i v.size(); i) {int tmp{ v[i] };int j i - 1;for (; j 0 tmp v[j]; j--) {v[j 1] v[j];}v[j 1] tmp;}
}int main()
{vectorint v{ 1, 2, 3, 2, 1 };insertion_sort(v);for (auto i : v) {cout i ;}cout endl;return 0;
}#3.稳定性与时间复杂度分析 插入排序的复杂度同样为 O ( n 2 ) O(n^2) O(n2)不过插入排序对于基本有序的序列插入排序的移动和查找操作次数非常少所以之后在设计你自己的排序方式的时候可以尝试在基本有序的情况下使用插入排序优化而在比较混乱的情况下采取更快的排序方式。 稳定性其实很好分析我们的排序过程中不存在直接交换两个点的过程只是依次向左交换因此插入排序可以保证稳定性。 还有一个点需要注意的点插入排序对于链式存储也是比较容易的因为不涉及到点的随机访问。对了对于数组的实现我们或许还可以使用二分查找的方式更快地找到插入的位置不过时间复杂度是不会变的哦
(5).希尔排序
#1.算法思想 希尔排序是一种基于插入排序的修改法则我们在插入排序的过程中每次往前移动一个位置而如果能一次移动更多位置或许排序的速度就能被优化了。 因此希尔排序(递减增量排序)就出现了我们给出 d 0 , d 1 , d 2 , . . . , d t − 1 d_0,d_1,d_2,...,d_{t-1} d0,d1,d2,...,dt−1这么一系列严格递减的正整数增量且 d t − 1 1 d_{t-1}1 dt−11 每次排序的时候对整个序列按照增量为 d i d_i di进行分组然后对不同的分组分别进行排序直到最后再用增量为1的序列对所有数据进行一次排序。 需要注意的是我们可以保证这么排序一定至少不会让时间复杂度变高因为插入排序本身对于基本有序的数据的排序时间复杂度就会更低。
#2.代码实现 基本上我们只需要在基本的插入排序前面加一层对于递减增减的序列就好了然后把对应的j-1改成j-delta就好了
#include iostream
#include vector
using namespace std;void shell_sort(vectorint v)
{vectorint d{ 7, 5, 3, 1 };for (int delta 0; delta d.size(); delta) {int h d[delta];for (int i h; i v.size(); i) {int tmp{ v[i] };int k{ i - h };for (; k 0 tmp v[k]; k - h) {v[k h] v[k];}v[k h] tmp;}}
}int main()
{vectorint v{ 1, 2, 3, 2, 1, 2, 3, 2, 1 };shell_sort(v);for (auto i : v) {cout i ;}cout endl;return 0;
}#3.稳定性和时间复杂度分析 希尔排序的时间复杂度很难分析它的时间复杂度基本基于你的增量序列选择这里要注意增量序列要避免出现因子比如9和3同时出现就会多一次没有必要的排序。 Knuth在1969年推荐了这样一个序列 d i 1 3 d i 1 d_{i1}3d_i1 di13di1经过分析比较的次数不超过 O ( n 3 2 ) O(n^{\frac{3}{2}}) O(n23)我们终于突破了 O ( n 2 ) O(n^2) O(n2)!
小结 最近实在是太忙今天只能暂时先把内部排序的上半部分发出来了下半部分我们会讲讲归并排序、快速排序和基数排序的内容。
