数据结构与算法

pengkingli 2020-05-20

数据结构与算法

关于算法的代码写了一些在:https://gitee.com/yuan_yi_xiang/data_structure_algorithm欢迎指正

基础的数据结构:

数组、链表、栈、队列

基础排序算法:

冒泡排序o(n2)、插入排序o(n2)、选择排序o(n2)

归并排序和快速排序都是分治思想,时间复杂度都为nlogn但快速排序的空间消耗较归并排序少

快速排序代码:https://gitee.com/yuan_yi_xiang/data_structure_algorithm/blob/master/src/%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/QuickSort.java

线性排序

如果是给大量数据进行排序,内存不够用的时候可以用

桶排序o(n):如果要排序的数据有 n 个,我们把它们均匀地划分到 m 个桶内,每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序,时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk),因为 k=n/m,所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时,log(n/m) 就是一个非常小的常量,这个时候桶排序的时间复杂度接近 O(n)。

但是要求划分的桶也是有序的,如果划分在一个桶内的数据较多无法进入内存,可以继续划分

计数排序:很像通排序,有大量的数据但是数据很多都是重复的,举个例子我们都经历过高考,高考查分数系统你还记得吗?我们查分数的时候,系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生,如何通过成绩快速排序得出名次呢?考生的满分是 900 分,最小是 0 分,这个数据的范围很小,所以我们可以分成 901 个桶,对应分数从 0 分到 900 分。根据考生的成绩,我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生,所以并不需要再进行排序。我们只需要依次扫描每个桶,将桶内的考生依次输出到一个数组中,就实现了 50 万考生的排序。因为只涉及扫描遍历操作,所以时间复杂度是 O(n)。

数据结构与算法

使用极客时间学习的引用。

将a数组中的找到最大的值,比如这里是5,就建立大小为6的数组保存0-5的个数,然后依次相加,就能得到对应小于等于这个数总共有几个数,就能得出数本身的下标。

代码:https://gitee.com/yuan_yi_xiang/data_structure_algorithm/blob/master/src/%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95/CountingSort.java

后面会持续更新,可以一起学习。评论欢迎指正

相关推荐