计数排序

​ 计数排序是一个非基于比较的整数排序算法,用空间换时间,优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围)。

基本思想及实现

基本思想: 假设输入的线性表L的长度为n,L=L1,L2,..,Ln;线性表的元素属于有限偏序集S,|S|=k且k=O(n),S={S1,S2,..Sk};则计数排序可以描述如下:

  • ① 扫描整个集合S,对每一个Si∈S,找到在线性表L中小于等于Si的元素的个数T(Si);
  • ② 扫描整个线性表L,对L中的每一个元素Li,将Li放在输出线性表的第T(Li)个位置上,并将T(Li)减1。

阅读全文

快速排序

​ 快速排序是采用分治法(Divide and Conquer)的应用。和归并排序不同的是,她不需要额外的存储空间,时间复杂度: T(n) = Θ(nlgn),最坏情况下是:T(n) = Θ(n²)。

基本原理及实现

基本原理: 使用递归、分治的思想,每次调用排序方法,随机选取一个key值,结果保证:key值所在数组中的位置,且能保证key左侧位置的数据总小于key值;右侧位置数据总大于key值

  • ① 当数组为空时,数组不需要排序,算法结束。
  • ② 选取一个key值,可以是带排序数组中任意位置的元素,这里选第一个元素。
  • ③ 遍历数组(角标j),将所有比key值小的元素移动到数组前边(角标i)。遍历结束时,i即是中间位置。
  • ④ 将key值与角标i位置元素位置互换。
  • ⑤ 递归对i位置左侧、右侧数组进行快速排序。

阅读全文

二分查找

​ 二分查找算法也称为折半搜索、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。算法是建立在有序数组基础上的。时间复杂度: T(n) = Θ(logn)。

原理及实现

基本原理:使用递归、分治的思想

  • ① 当数组为空时,说明数组中不存在需查找的元素。
  • ② 用有序数组的中间位置元素与需查找元素进行大小比较,如果相等,则查找结束。
  • ③ 如果中间位置元素大于需查找元素,则从数组左侧位置进行递归查找。
  • ④ 如果中间位置元素小于需查找元素,则从数组右侧位置进行递归查找。

阅读全文

归并排序

​ 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。需要额外的存储空间,时间复杂度: T(n) = Θ(nlgn)。

阅读全文

插入排序

​ 每次将一个待排序的记录,按其大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。时间复杂度 T(n) = Θ(n²)。

原理及实现

基本原理:对待排序数组a[n],假设第i(i∈[1,n])个元素左侧已排序,右侧未排序。

  • ① 从i位置左侧已排序数组位置中,逆序遍历,查找元素a[i]的目标位置,即第一个比a[i]小的元素后边targetPos(或者第一个位置)。
  • ② 移动元素:将数组元素[targetPos + 1 .. i - 1] 整体向后移动一位。
  • ③ 将第i(i∈[1,n])个元素a[i]放置到[targetPos + 1]位置。
  • ④ 遍历执行①、②、③操作,直到最后一个元素a[n]。

阅读全文