3-17(排序)
排序:
就是使一串数据,按照其中的某个或某些关键字大小,递增或递减的排序操作。
1、插入排序
直接插入排序:在一个有序的序列中插入数据,使其序列仍然有序。
时间复杂度为O(N^2),最好情况为O(N)。
空间复杂度为O(1)
是一种稳定的排序算法。
希尔排序:先选定一个整数gap,把待排序的数据分为若干组,并对每一组进行排序。也就是直接插入排序的优化,根据gap大小,先进行了一次预排序,再将gap依次改变直到为1,其排序就是直接插入排序了。gap一定为:gap=gap/n+1;加1是为了gap一定会等于1.
当gap>1时,都是预排序,当gap=1时,就为直接插入排序。
时间复杂度为O(N^1.3)
是不稳定的排序。
2、选择排序
思想:每次在待排序数据中选出最小或最大的数据,存放在序列的起始位置。
直接选择排序:效率非常低,
时间复杂度为O(N^2);
空间复杂度为O(1);
排序算法不是稳定的。
堆排序:是利用建堆来排序的。
如果需要降序,则建小堆,如果升序,则建大堆。
时间复杂度为O(N*logN)
空间复杂度为O(1);
是不稳定的排序算法。
3、交换排序
冒泡排序:就是将数据一一比较,每次比较完成都会产生一个数,在其自己位置上,需要比较n-1次。
时间复杂度为O(N^2)。
空间复杂度为O(1)。
时稳定的排序算法。
快速排序
时间复杂度为O(N*logN)
空间复杂度为O(logN)
不稳定的排序算法。
hoare法(左右指针法)
就是将begin和end依次移动,如果升序,则begin这段找大与key,end找小于key的,找到就互换,知道begin==end。
最右边做key,左边先走,左边做key,右边先走。因为这样做,一定可以确定最后停的位置会和key交换。
挖坑法:
就是找左/右一端为key,使其为一个空位,在其右/左找个数插入其坑位,这样被插入数据的位置就变为坑位,再在左/右找个数插入,知道begin==end。
前后指针法
定义2个变量prev和cur,cur=begin,prev=begin-1;cur找小,遇到小,则prev前进一个,再互换cur和prev的值。遇到大,则cur前进,prev不变。
你的鼓励让我更有动力
赞赏
0人进行了赞赏支持
更多相关文章
- 2021-03-17:手写代码:单链表插入排序。
- 排序算法——选择排序
- 排序算法——冒泡排序
- 2021-03-16:手写代码:单链表归并排序。
- BAT iOS算法面试题(汇总)
- 必读|spark的重分区及排序
- 2021-03-15:手写代码:单链表选择排序。
- 2021-03-14:手写代码:单链表冒泡排序。
- 二维数组排序-搜索-增删改查-多维数组递归