插入排序
插入排序适合对少量数据的排序
基本思想:每次处理就是将无序的数列中第一个元素与有序数列的元素从后到前比较,找到插入位置,将该元素插入到有序数列的适当的最终的位置上,是一种简单直观的排序算法
默认插入排序的初始数组从第 1 位开始存入
直接插入排序
属性 | 参数 |
---|---|
时间复杂度 | O(n2) |
空间复杂度 | O(1) |
稳定性 | 稳定 |
思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列
因为如果只有一个数的话是不用排序的,所以 n 个数只用给 n-1 个数找位置,所以总共需要循环 n-1 次。每一次循环过后有序序列变长,无序序列变短
1 | //在插入排序中一般从第一个位置存值,第0位用来存正在拿来比较的值(哨兵位) |
折半排序
属性 | 参数 |
---|---|
时间复杂度 | O(n2) |
空间复杂度 | O(1) |
稳定性 | 稳定 |
思想:在直接插入排序基础上将遍历查找插入位置改为二分查找来加快速度
1 | for(int i=2;i<=n;i++){ |
二路排序
属性 | 参数 |
---|---|
时间复杂度 | O(n2) |
空间复杂度 | O(n) |
稳定性 | 稳定 |
思想:在折半排序的基础上进一步改进,将排序由沿一个方向上移动改为沿两个方向上移动,如此进一步减少了移动次数
我们设定一个辅助数组
A
,大小为原数组 +1 ,将A[0]
设为原数组的第一个数,通过first
和last
指针指向有序序列的最小值和最大值(即头部和尾部)并且利用约瑟夫环使其成为一个循环数组进行两端插入
1 | //此算法不同于上述算法,多开了一个辅助数组,因此也不需要哨兵位,从0开始存值 |
希尔排序
属性 | 参数 |
---|---|
时间复杂度 | O(n1.3) |
空间复杂度 | O(1) |
稳定性 | 不稳定 |
引入:希尔排序是直接插入排序另一种更改思路,插入排序在对几乎已经排好序的数列操作时,效率高(即可以达到线性排序的效率)。但插入排序一般是低效的,因为插入排序每次只能将数据移动一位,所以希尔排序不再加快查找效率而是加快移动效率,通过设置不同增量可以让特别靠后的小数向前“跳”着到序列前面,又称“缩小增量排序”
思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序。随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个数列恰被分成一组形成有序序列
意义:希尔排序是第一个将排序的时间复杂度降至 O(n2) 以下的,该方法实质上是一种分组插入方法
注意:希尔排序相当于是根据不同增量进行宏观调,控但如此也变得不稳定了
增量分组没有特定的科学依据,比较玄学,但是分的好也就快点,D.L.Shell 建议是减半分组,例如:8 ,4 ,2 ,1 ,反正最后都是要进行一次间隔 1 的希尔插入
1 | const int t=4;//可以自己根据情况来改的 |
交换排序
交换排序也是只适合对少量数据的排序
基本思想:所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,每次交换将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动
默认交换排序的初始数组从第1位开始存入,第 0 位仍作为哨兵位用于交换操作:
1 | void swap(int x,int y){//这里定义swap不是STL函数而是手写模拟过程 |
冒泡排序
属性 | 参数 |
---|---|
时间复杂度 | O(n2) |
空间复杂度 | O(1) |
稳定性 | 稳定 |
思想:利用的比较交换,利用循环将第 i 小或者大的元素归位,归位操作利用的是对 n 个元素中相邻的两个进行比较,如果顺序正确就不交换,如果顺序错误就进行位置的交换。通过重复的循环访问数组,直到没有可以交换的元素
正如名字那样冒泡排序就好像冒水泡一样第 i 次循环通过交换过程使 i 小(大)的元素由序列一端浮向另一端,如果有 n 个数要排序那就要循环 n-1 次
1 | for(int i=1;i<n;i++){ |
冒泡排序优化
优化一
引入:假设我们现在排序 arr[]={1,2,3,4,5,6,7,8,10,9}
这组数据,按照上面的排序方式,第一趟排序后将 10 和 9 交换已经有序,接下来的8趟排序就是多余的,什么也没做
思想:我们可以在交换的地方加一个标记,如果那一趟排序没有交换元素,说明这组数据已经有序,不用再继续下去
1 | bool flag=true; |
优化二
引入:优化一仅仅适用于连片有序而整体无序的数据(例如:1 , 2 ,3 ,4 ,7 ,6 ,5 )。但是对于前面大部分是无序而后边小半部分有序的数据(1 ,2 ,5 ,7 ,4 ,3 ,6 ,8 ,9 ,10)排序效率也不可观,对于种类型数据,我们可以继续优化
思想:我们可以记下最后一次交换的位置,后边没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可
1 | int flag=n; |
鸡尾酒排序
引入:上述冒泡排序每次只能找出一个最大(小)值,其实好可以继续优化代码减少循环次数,鸡尾酒排序其实相当于冒泡排序的优化三
思想:一次排序可以确定两个值,正向扫描找到最大值交换到最后,反向扫描找到最小值交换到最前面
一次循环正反两次冒泡排序,同时可以用冒泡排序上优化一、二:
- 用一个标记变量记录是否发生了排序
- 设一个边界变量记录每次冒泡排序的边界,在正向排序找到一个关键值之后需要更新边界,反向排序的时候可以少找一位
1 | int bottom=1,top=n; |
快速排序
属性 | 参数 |
---|---|
时间复杂度 | O(nlog2n) |
空间复杂度 | O(nlog2n) |
稳定性 | 不稳定 |
思想:基于分治的思想,是冒泡排序的改进型。首先在数组中选择一个基准点(该基准点的选取可能影响快速排序的效率,后面讲解选取的方法),然后设两个指针( low
指向起始位置,high
指向末尾)分别从数组的两端扫描数组,首先从后半部分扫描,如果发现有元素比该基准点的值小,就交换 low
和 high
位置的值,然后从前半部分扫描,发现有元素大于基准点的值,就交换 low
和 high
位置的值,如此往复循环,直到 low>=high
,然后把基准点的值放到 high
这个位置。一次排序就完成了。以后采用递归的方式再分别对 hign
前半部分和后半部分排序,当前半部分和后半部分均有序时该数组就自然有序了。
意义:它是基于关键字比较的内部排序算法中速度最快者,快速排序因此而得名
快速排序主要消耗在区间的划分操作上,每一次划分(循环)结束也就确定了基准点在最终排好序的数列中的绝对位置,所以划分
k-1
次即完成了对k
个数的排序
1 | void quicksort(int low,int high){ |
选择排序
基本思想:首先在未排序序列中找到最大(小)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最大(小)元素,然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。选择排序也是一种简单直观的排序方法
同交换排序一样仍默认选择排序初始数组从第1位开始存入,第0位作为哨兵位用于交换操作:
1 | void swap(int x,int y){//这里定义swap不是STL函数而是手写模拟过程 |
简单选择排序
属性 | 参数 |
---|---|
时间复杂度 | O(n2) |
空间复杂度 | O(1) |
稳定性 | 不稳定 |
思想:每次从无序数列中选出最大(小)元素,然后放入有序数列的最末(前)端,该操作执行 n-1 次
1 | for(int i=1;i<=n;i++){ |
有一个小的优化:可以每次找出一个最大值和一个最小值,这样循环可以减少一半
堆排序
属性 | 参数 |
---|---|
时间复杂度 | O(nlog2n) |
空间复杂度 | O(1) |
稳定性 | 不稳定 |
引入:简单选择排序进行交换的次数很少,总共才 n-1 次,但是每次寻找最值的时候都要逐个位置进行比较导致有许多重复比较和无用比较。对于数量多的序列我们可以通过二叉树堆式建树可以有效减少比较次数(能利用完全二叉树特性的排序一般性能都不会太差)
堆的定义:堆是具有以下性质的完全二叉树——每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。如下图:
同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子:
该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:
1
2
3
4
5
6 >//若是从0开始存储
>大顶堆:arr[i]>=arr[2i+1]&&arr[i>=arr[2i+2]
>小顶堆:arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]
>//若是从1开始存储
>大顶堆:arr[i]>=arr[2i]&&arr[i]>=arr[2i+1]
>小顶堆:arr[i]<=arr[2i]&&arr[i]<=arr[2i+1]规律:堆的子节点又是一个小堆的堆顶,由 n 个元素组成的堆由 n/2 个中间节点和 n-(n/2) 个叶节点
思想:将待排序序列构造成一个大顶堆,此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆,这样会得到 n 个元素的次小值。如此反复执行 n-1 次,便能得到一个有序序列了
第i趟排序将序列前 n-i+1 个元素组成的子序列转换为一个堆,然后将堆得第一个元素与最后一个元素交换位置,排序需要进行一次堆的初始化和 n-1 次堆调整、堆顶与堆底交换,每次堆交换确定一个值的绝对位置
步骤:1.将原始序列转换为一个堆 2.将堆的第一个元素与堆的最后一个元素进行交换(相当于“去掉“一个最大(小)值)3.将“去掉”最大(小)值元素后剩余的元素组成的子序列重新转换一个新的堆
1 | void HeapAdjust(int s,int m){//s是堆的第一个元素,m是堆的最后一个元素 |
建堆的时候因为是无序的,所以凡是有子节点的(即构成堆的)都需要调整,所以从 n/2 位置开始向上注意每个节点调整。其中构建初始堆经推导复杂度为 O(n) ,在交换并重建堆的过程中,需交换 n-1次 ,而重建堆的过程中,根据完全二叉树的性质,
[log2(n-1),log2(n-2)...1]
逐步递减,近似为nlogn。所以堆排序时间复杂度一般认为就是 O(nlogn) 级。
STL排序
目录
所有函数均支持传入比较函数,并且执行给定区间是左开右闭 [begin,end)
排序函数 | 功能描述 |
---|---|
sort |
对给定区间所有元素进行不稳定排序(本质:快速排序) |
stable_sort |
对给定区间所有元素进行稳定排序(本质:归并排序) |
partial_sort |
对给定区间所有元素的部分区间元素排序 |
partial_sort_copy |
对给定区间复制并进行 partial_sort |
nth_element |
找出给定区间的指定位置对应的元素 |
is_sorted |
判断给定区间是否已经排好顺序 |
partition |
对给定区间所有元素按指定条件分类(符合条件的元素放前面) |
heap 堆排序 |
堆排序的STL实现,是一系列函数 |
stable_partition |
相对稳定的 partition |
比较函数 | 功能描述 |
---|---|
equal_to |
相等 |
not_equal_to |
不相等 |
less |
小于(升序、大顶堆) |
greater |
大于(降序、小顶堆) |
less_qual |
小于等于 |
greater_equal |
大于等于 |
cmp (自己取名字) |
自定义重载比较函数 |
注意:传入比较函数均是重载方式:
1 | vector<int>vect; |
详讲
sort()
和 stable_sort()
1 | bool cmp(int x,int y){ |
模板使用的是
sort()
,stable_sort()
同理
sort() |
stable_sort() |
|
---|---|---|
平均时间复杂度 | O(nlogn) | O(nlongn) |
本质 | 快速排序 | 归并排序 |
partial_sort()
和 nth_element()
partial_sort()
样例
1 | bool cmp(int x,int y){ |
nth_element()
样例
1 | bool cmp(int x,int y){ |
注意:函数中间的那个指定的是相对位置,因为数组从 0 开始编号,所以 b+3 是第四个位置,放的是第四大的数
partion()
和 stable_partition()
1 | bool IsOdd(int i){ |
1 | //另一个例子,找出数组中比平均值小的数并且按照降序排列 |
模板使用的是
partion()
,stable_partition()
同理
关于
bind1nd()
和bind2nd()
的讲解
首先,他们都在头文件<functional>
中定义。
其次,bind 就是绑定的意思,而1st就代表 first ,2nd就代表 second 。
再次,他们的声明是一样的,都是(const Operation& op, const T& x)
简单的说,
bind1st(const Operation& op, const T& x)
就是这么一个操作:x op value
,而bind2nd(const Operation& op, const T& x)
就是这么一个操作:value op x
,其中value
是被应用bind
的对象。这两个配接器都用于将一个二元算子转换成一个一元算子。下面来看一段代码吧!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 >
>using namespace std;
>signed main()
>{
vector<int> coll;
for(int i = 1; i <= 10; ++i){
coll.push_back(i);
}
//查找元素值大于10的元素的个数
//也就是使得10 < elem成立的元素个数
int res = count_if(coll.begin(), coll.end(), bind1st(less<int>(), 10));
/*less是二元函数对象,bind1st(less<int>(), 10)就是将10赋值给less模板中的left;
bind2nd(less<int>(), 10))中的10赋值给了right*/
cout << res << endl;
//查找元素值小于10的元素的个数(也可以看做第一个不满足条件的数的位置)
res = count_if(coll.begin(), coll.end(), bind2nd(less<int>(), 10));
cout << res << endl;
return 0;
>}
>/*输出结果:
>0
>9*/
heap
排序
make_heap()
:根据指定的迭代器区间以及一个可选的比较函数来创建一个 heap
(默认建立大顶堆)
1 | vector<int> vec{6,1,2,5,3,4}; |
push_heap()
:把指定区间的最后一个元素插入到 heap
中
1 | vec.push_back(200);//5 6 1 3 2 4 200 |
注意:使用 push_heap(f,l)
的话一定要确保 [f,l-1)
已经是一个堆(第 l 个元素是要排入堆中的元素),push_heap(f,l)
仅仅会把第 (l-1) 的数插入到 [f,l-1)
这个区间形成的堆中
pop_heap()
:弹出 heap
顶元素,将其放置于区间末尾
1 | vector<int>vec{6,1,2,5,3,4}; |
sort_heap()
:堆排序算法,通常通过反复调用 pop_heap()
交换堆顶和堆底来实现
1 | vector<int> vec{6,1,2,5,3,4}; |
heap()
使用示例:
1 | signed main() |
其他排序
归并排序
属性 | 参数 |
---|---|
时间复杂度 | O(nlog2n) |
空间复杂度 | O(n) |
稳定性 | 稳定 |
思想:该算法先采用分治法将复杂的多数量排序问题分为若干个简单的少数量排序问题递归求解,然后在将解决的问题逐渐合并最终得到整体排序问题答案
分:将问题分成一些小的问题然后递归求解
治:将分的阶段得到的各答案"修补"在一起
图解:先分而治之然后在将其合并
1 |
|
GNOME
排序(地精排序)
属性 | 参数 |
---|---|
时间复杂度 | O(n2) |
空间复杂度 | O(1) |
稳定性 | 稳定 |
思想:通过一层循环进行遍历,相邻的两个元素比较,如果两个元素逆序则交换。与冒泡排序不同的是他如果遇到一个交换操作的时候变为向前冒泡,直至不发生交换操作位置。所以地精排序可以说是冒泡排序和直接插入排序的组合
循环的指针
i
从0开始,进入循环。当i
是0的时候直接i++
,当i不为0的时候比比较下标为i
和i-1
的数值,如果正序就i++
,如果逆序就交换并且i--
。一直循环至i
到最后一个元素的位置。
图解
当前数组 | 操作 |
---|---|
[5, 3, 2, 4] | pos==0 直接 pos 自增 |
[5, 3, 2, 4] | a[pos]<a[pos-1] ,交换并且 pos>0 ,pos 自减 |
[3, 5, 2, 4] | a[pos]>=a[pos-1] , pos 自增 |
[3, 5, 2, 4] | a[pos]<a[pos-1] ,交换并且 pos>0 , pos 自减 |
[3, 2, 5, 4] | a[pos]<a[pos-1] ,交换并且 pos>0 , pos 自减 |
[2, 3, 5, 4] | pos==0 直接 pos 自增 |
[2, 3, 5, 4] | a[pos]>=a[pos-1] ,pos 自增 |
[2, 3, 5, 4] | a[pos]>=a[pos-1] , pos 自增 |
[2, 3, 5, 4] | a[pos]<a[pos-1] ,交换并且 pos>0 , pos 自减 |
[2, 3, 4, 5] | a[pos] >=a[pos-1] ,pos 自增 |
[2, 3, 4, 5] | a[pos]>=a[pos-1] ,pos 自增 |
[2, 3, 4, 5] | pos==length(a) ,排序完成 |
1 | //地精算法改进版 |
地精排序最显著的特点是代码只有一层循环,原版算法代码极短,但效率不高,改进后相当于插入排序的变种,不过条件判断多了,代码比标准的插入排序长
非比较排序
基础:非比较排序是一种基于桶排序思想的高效线性排序,适用对数据范围小但数量多的序列排序
意义:在一定情况下,非比较排序效率要比比较排序更高,是一种牺牲空间换取时间的做法
桶排序思想
桶排序是一种排序的思想,其实现包括计数排序和基数排序两种,冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序都是基于比较的排序,桶排序提出了一种新的思路,即基于数据状态的排序
注意:桶是一种容器,这个容器可以用多种数据结构实现,包括数组、队列或者栈
算法实现:计数排序和基数排序
步骤:1.得到无序数组的取值范围
2.根据取值范围创建对应数量的桶
3.遍历数组,把每个元素放到对应的桶中
(4)按照顺序遍历桶中的每个元素,依次放到数组中,即可完成数组的排序
计数排序( MSD
)
属性 | 参数 |
---|---|
时间复杂度 | O(n+k) |
空间复杂度 | O(n+k) |
稳定性 | 稳定 |
思想:将出现的数放入指定的桶中,然后按照桶的顺序依次输出里面的数即排好了顺序
步骤:1.找出无序数组的最大值,创建一个长度为数据中最大值 +1 的空数组
2.遍历原数组,统计每个元素出现的次数
3.遍历桶,即用于元素个数统计的数组,得到有序的数组
1 | void CountSort(int arr[],int n){//范围为0-20 |
基数排序( LSD
)
属性 | 参数 |
---|---|
时间复杂度 | O(n*k) |
空间复杂度 | O(n+k) |
稳定性 | 稳定 |
计数排序是每个桶只存储单一键值,而基数排序是根据键值的每位数字来分配桶
思想:将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数
- [ ] 代码还不会,待整理 😓
排序总结
本博客总结的排序都是内部排序(只运用内存进行排序)
排序方法 | 时间复杂度(最好) | 时间复杂度(最坏) | 时间复杂度(平均) | 空间复杂读 | 稳定性 |
---|---|---|---|---|---|
插入排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
希尔排序 | O(n) | O(n2) | O(n1.3) | O(1) | 不稳定 |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 |
快速排序 | O(nlong2n) | O(n2) | O(nlog2n) | O(nlog2n) | 不稳定 |
归并排序 | O(n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
地精排序 | O(n2^) | O(n2) | O(n2) | O(1) | 稳定 |
计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
神级排序
Bogo排序,又被称为猴子排序,是一种恶搞排序算法,它将一切交给了上帝,其算法就是坑爹的将元素随机打乱,然后紧紧检查其是否符合排列顺序,若否,则继续进行随机打乱,继续检查结果,直到符合排列顺序。
Bogo排序的最坏时间复杂度为 O(∞),一辈子也不能输出排序结果,平均时间复杂度为 O(n·n!)。
然而,有个看似笑话的方法声称可以用 O(n) 实现Bogo排序,依照量子理论的平行宇宙解释,使用量子随机性随机地重新排列元素,不同的可能性将在不同的宇宙中展开,总有一种可能猴子得到了正确的顺序,量子计算机找到了这个宇宙后,就开始毁灭其他排序不成功的宇宙,剩下一个观察者可以看到的正确顺序的宇宙
如果想要迈出这个看似荒诞,但令人无比兴奋的"高效算法"的第一步,请先证明"平行宇宙解释"的正确性
1 | BOOL BogoSort(datatype *array, int size){ |