赞
踩
目录
什么是稳定排序算法:数据先后次序不变
选择排序 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):
► 先找出最小值,将其与第一个位置的元素进行交换
► 对剩余的数据重复以上过程,直至排序结束
归并:如果有两个分别有序的数组,可以用双指针合并成一个完全有序的数组
可以递归写
也可以从0开始
归并1-1 1-1 1-1 1-1
归并 2-2 2-2
归并 4-4
完成!
假设前面 k 个元素已经按顺序排好了,在排第 k+1个元素时,将其插入到前面已排好的 k 个元素中,使得插入后得到的 k+1 个元素组成的序列仍按值有序。
基本过程描述如下:
① 把序列按照某个增量(gap)分成几个子序列,对这几个子序列进行插入排序。
② 不断缩小增量,扩大每个子序列的元素数量,并对每个子序列进行插入排序。
③ 当增量为 1 时,子序列就是整个序列,而此时序列已经基本有序了,因此只需做少量的比较和移动就可以完成对整个序列的排序
出发点:插入排序在元素基本有序的情况下,效率很高。
gap:初始值设为 n/2,然后不断减半。
► 走访需要排序的序列,比较相邻的两个元素,如果他们的顺序错误就把他们交换过来。
► 不断重复上述过程,直到没有元素需要交换
具体过程:
► 将第 1 个和第 2 个元素进行比较,如果前者大于后者,则交换两者 的位置,否则位置不变;然后将第 2 个元素与第 3 个元素进行比较, 如果前者大于后者,则交换两者的位置,否则位置不变;依此类推, 直到最后两个元素比较完毕为止。这就是第一轮冒泡过程,这个过程 结束后,最大的元素就“浮”到了最后一个位置上。
► 对前面 n-1 个元素进行第二轮冒泡排序,结束后,这 n-1 个元素中 的最大值就被安放在了第 n-1个位置上。
……执行n-1轮
简单优化:
如果在某轮冒泡过程中没有发生元素交换,这说明整个序列已经排好序了,这时就不用再进行后面的冒泡过程,可以直接结束程序
进一步优化:
假设有 100 个数组成的数组,仅前面10个无序,后面90个都已排好序且都大于前面10个数字,那么在第一轮冒泡过程后,最后发生交换的位置必定小于10,且这个位置之后的数据必定已经有序了,记录下这位置,第二轮遍历是只要到这个位置就可以了。记录每轮遍历最后发生交换的位置,下次遍历只需到此位置为止
先排个位,再排十位,再排百味(30次)
快速排序采用的是分而治之思想:将原问题分解为若干个规模更小但结构与原问题相似的子问题,然后递归求解这些子问题,最后将这些子问题的解组合为原问题的解
1.以第一个元素为基准书,使得基准书左边只有比他小的,右边只有比他大的
2.然后对基准书两边的数组分别进行操作1
分治:分成相同的子问题,用递归求解;子问题相互独立
dp:子问题不一定相同,具有最优子结构;子问题相互依赖
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。