目录

排序

选择排序 O(n2)

不稳定:48429

归并排序 O(n log n) 稳定

插入排序 O(n2)

堆排序 O(n log n)

希尔排序 O(n log2 n)

图书馆排序 O(n log n)

冒泡排序 O(n2)

优化:

基数排序 O(n · k)

快速排序 O(n log n)【分治】 不稳定

桶排序 O(n + k)

计数排序 O(n + k)

鸽巢排序 O(n + D)


排序

什么是稳定排序算法:数据先后次序不变

选择排序 O(n2) 归并排序 O(n log n)插入排序 O(n2) 堆排序 O(n log n)希尔排序 O(n log2 n) 图书馆排序 O(n log n)冒泡排序 O(n2) 基数排序 O(n · k)快速排序 O(n log n) 桶排序 O(n + k)计数排序 O(n + k)鸽巢排序 O(n + D):

选择排序 O(n2)

► 先找出最小值,将其与第一个位置的元素进行交换

► 对剩余的数据重复以上过程,直至排序结束

不稳定:48429

归并排序 O(n log n) 稳定

归并:如果有两个分别有序的数组,可以用双指针合并成一个完全有序的数组

可以递归写

也可以从0开始

归并1-1  1-1  1-1  1-1

归并   2-2          2-2

归并         4-4

完成!

插入排序 O(n2)

假设前面 k 个元素已经按顺序排好了,在排第 k+1个元素时,将其插入到前面已排好的 k 个元素中,使得插入后得到的 k+1 个元素组成的序列仍按值有序。

堆排序 O(n log n)

希尔排序 O(n log2 n)

基本过程描述如下:

① 把序列按照某个增量(gap)分成几个子序列,对这几个子序列进行插入排序。

② 不断缩小增量,扩大每个子序列的元素数量,并对每个子序列进行插入排序。

③ 当增量为 1 时,子序列就是整个序列,而此时序列已经基本有序了,因此只需做少量的比较和移动就可以完成对整个序列的排序

出发点:插入排序在元素基本有序的情况下,效率很高。

gap:初始值设为 n/2,然后不断减半。

图书馆排序 O(n log n)

冒泡排序 O(n2)

► 走访需要排序的序列,比较相邻的两个元素,如果他们的顺序错误就把他们交换过来。

► 不断重复上述过程,直到没有元素需要交换

具体过程:

► 将第 1 个和第 2 个元素进行比较,如果前者大于后者,则交换两者 的位置,否则位置不变;然后将第 2 个元素与第 3 个元素进行比较, 如果前者大于后者,则交换两者的位置,否则位置不变;依此类推, 直到最后两个元素比较完毕为止。这就是第一轮冒泡过程,这个过程 结束后,最大的元素就“浮”到了最后一个位置上。

► 对前面 n-1 个元素进行第二轮冒泡排序,结束后,这 n-1 个元素中 的最大值就被安放在了第 n-1个位置上。

……执行n-1轮

优化:

简单优化:

如果在某轮冒泡过程中没有发生元素交换,这说明整个序列已经排好序了,这时就不用再进行后面的冒泡过程,可以直接结束程序

进一步优化:

假设有 100 个数组成的数组,仅前面10个无序,后面90个都已排好序且都大于前面10个数字,那么在第一轮冒泡过程后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经有序了,记录下这位置,第二轮遍历是只要到这个位置就可以了。记录每轮遍历最后发生交换的位置,下次遍历只需到此位置为止

基数排序 O(n · k)

先排个位,再排十位,再排百味(30次)

快速排序 O(n log n)【分治】 不稳定

快速排序采用的是分而治之思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题,然后递归求解这些子问题,最后将这些子问题的解组合为原问题的解

1.以第一个元素为基准书,使得基准书左边只有比他小的,右边只有比他大的

2.然后对基准书两边的数组分别进行操作1

分治:分成相同的子问题,用递归求解;子问题相互独立

dp:子问题不一定相同,具有最优子结构;子问题相互依赖

桶排序 O(n + k)

计数排序 O(n + k)

鸽巢排序 O(n + D)

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部