该和排序算法做个了结了
15种排序算法动态演示
这个视频是在网上看到的。
<iframe allowfullscreen="true" frameborder="0" height="500px" src="https://v.qq.com/txp/iframe/player.html?vid=t0396emm8oy" width="100%"></iframe> 那我们就跟着视频来写出这15种排序算法吧。这15种排序分别是:1.简单选择排序
2.插入排序
3.快速排序
4.合并排序
5.堆排序
6.基数排序
7.最高有效位排序
8.内省排序
9.适应性归并排序
10.希尔排序(缩小增量,插入排序的改进版)
11.冒泡排序
12.鸡尾酒排序(定向冒泡,选择排序的一种)
13.地精排序(写法最简单的排序)
14.双调排序
15.Bogo排序(等量子计算时代唯一的算法,穷举法)
选择排序
简单选择排序
简单选择排序,每次找到一个最小的。放到前面。
效率自然是 O(n2)
胜者树
类似线段树,先建树,然后区间最值,最后能得到最小值。取出。
然后删掉这个数,更新区间,得到次小。循环···
更新方法就是线段树的pushUp
插入排序
直接插入排序
加哨兵的核心:
for(int i=2;i<n;i++){
vt[0]=vt[i];
int j=i-1;//从i的前一个开始往前找
for(;vt[j]>vt[0];j--)
vt[j+1] = vt[j];//找到比哨兵大的就后移(大的在后嘛)
vt[j+1] = vt[0];//循环走完 j+1的位置就是i的归宿 因为j的位置是比小的
//这么一轮下来,[1,i]这一段就是有序的了
}
作用
-
把每次要插入的目标放到vt[0]的位置,
-
让循环的结束条件
vt[j]>vt[0]
一定可以结束。因为当目标值是最小的时候,第一个元素vt[1]都比目标大,vt[1]会后移到vt[2]上。
j--
则 j就变成了0 。vt[0]>vt[0]
不成立,循环结束。且要插入的位置正是 0+1 = 1。目标值放在了位置1上。
复杂度分析:
- 最好比较n-1次 移动0次
- 最坏比较(n+2)(n-1)/2次 移动(n+2)(n-1)/2次
- 平均:(n^2)/4 时间复杂度O(n^2)
折半插入
寻找位置的过程用折半查找,
平均比较次数 nlogn 移动次数 n^2/4
时间复杂度O(N2)
二路插入
用一个辅助链表,减少移动的次数。
最终移动次数 \(n^2/8\) ,相当于以第一个元素为哨兵分成了两个比它大、小的部分,再移动这两个部分。
复杂度\(O(n^2)\)
希尔排序
不稳定
分别选Delta10\5\3\1为增量。然后对每个位置的数进行插入排序。
实验数据表明 效率约为 N^1.3
交换类排序
冒泡排序
每一轮排序:都将【无序序列】中,关键字最大的那个一上升到【有序序列】中。
优化结束条件:本轮没有进行交换。
复杂度
-
最好
比较 n-1 移动 0
-
最坏
比较 n(n-1)/2 移动 3n(n-1)/2
-
O(n2)
快速排序
核心就是i和j两个坐标的移动:
while (i<j){
while (a[j]>=temp && i<j)
j--;
a[i] = a[j];
while (a[i]<=temp && i<j)
i++;
a[j] = a[i];
}
注意的地方:
-
进入快排,先把传入的i和j两个参数存起啦,最后递归的时候要用
-
大于等于,一定要带等于!!!不然肯定死循环(只有里面有一样的数,i和j就永远不会进入++和--。
-
关于快排的稳定性:
之前想错了。稳定性和比较时带不带>=号没关系。因为在和其他元素比较时,a也会被移动。
优化
-
对于有序的情况,快排退化成On2,因此不采用每个区间的第一个元素作为“标杆”,而是用区间[i,j]的首、中、尾三个元素做比较,来做为标杆进行排序。
重点来了!
怎么让这个元素做标杆呢!我之前还在傻傻地改代码!!!
其实只要在原来的快排代码上,选出标杆之后,把标杆位置的数和i位置的数swap一下就行了啊!!!这样还是从第一个数做标杆。但第一个数已经成了我们想用的那个。
- x,y,z如何判断y是不是中间值呢?
if(y>=x&&y<=z)
是不对的。还要||(y<=x&&y>=z)
- x,y,z如何判断y是不是中间值呢?
合并排序
-
归并的拆分的递归思路特别好。要记住两个函数参数怎么设。
-
归并要用 i,m,m+1,j
而不要用 i,m-1,m,j
举个例子 i=1,j=2
用第一个(1,1,2,2) 没问题吧
用第二个(1,0,1,2) 看到没,后面又成了1,2. 会无限循环进入1,2
-
合并时的条件是(i<=m && m+1<=j)
要带上等于号!
因为不能保证两个式子都是小于的。万一有一个等于就无法进入合并了。
比如(1,2,3,3) 虽然(3,3)不用处理,但是(1,2)要处理啊。
-
需要占用空间啊(要有个临时数组去合并结果)。
堆排序
https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
v = {9999,6,9,5,6,8,2,0};//0的位置没用
void sift(int low, int high){
int i = low, j = i*2;
int x = v[i];
while (j<=high){
if(j<high && v[j]<v[j+1])
j = j+1;//右孩子大则j指向右孩子
if(x < v[j]){//如果x小
v[i] = v[j];//大的上来
i = j; //i下移一层看
j = i*2; //j继续当i的儿子
} else
break;
}
v[i] = x;
}
void heapSort(int n){
int i;
int temp;
for(i=n/2; i>=1; i--)
sift(i,n);
for(i=n; i>=2; --i){
temp = v[1]; //备份当前最大值
v[1] = v[i]; //把小的顶上来
v[i] = temp; //最大的归位了
sift(1,i-1);
}
}
空间复杂:只用到了一个temp,为O(1)
相对于快排,堆排序的优点在于最坏也是Ologn的(毕竟是树)
堆排序适合记录数很多的情况。经典的例子是10000个中找出最小的10个。
如果记录数少,则不提倡堆排序。
基数排序
http://www.cs.usfca.edu/~galles/visualization/RadixSort.html
我完全按照算法的思想。把数一次次存到map里写出来的。
貌似正规的写法不用这么「扯」。
说下我的写法吧:
-
按个位数当下标key,先全存到第一个map里
-
建立一个allMap,根据最高位数exp,往allMap里存map。
-
遍历上一层的map。因为上一层的map是按个位数排好序的。
取出这个数。判断它的十位。存到这一层的map里。
-
map里如果value是存的vector,那不需要初始化就可以直接push_back的。
比如,
map[1].push_back(99);
这种写法是没错的。
最高有效位排序
这和基数排序啥区别啊。就是从高位开始判断的基数排序?
内省排序
适应性归并排序
鸡尾酒排序
地精排序
双调排序
Bogo排序
完美排序
思想:
if
i位置比j位置小,二者交换。- 循环结束条件 i等于j
- 三分数组,先递归前2/3。再递归2/3。再递归前2/3
代码美观。
效率低。
最后看一个娱乐的。24中排序算法同时运行,拿个更快呢?
<iframe allowfullscreen="true" frameborder="0" height="500px" src="https://v.qq.com/txp/iframe/player.html?vid=x0528v6hypr" width="100%"></iframe> 标签:Sort,map,移动,--,位置,vt,排序 From: https://www.cnblogs.com/xuanshan/p/17552003.html