浅谈Java数据结构和算法
今天的突然看集合底层的时候发现了好多算法和数据结构。再次就比较一下和汇总一下。
数据结构分类:线性结构和非线性结构
问题一:
什么是线性和非线性;
我个人的理解是:数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构;
线性结构包括:数组,链表,队列,栈;
非线性结构包括:树,图,表;
详解:
一.线性结构
1.数组
特点:我们都知道数组中的元素在内存中连续存储的,可以根据是下标快速访问元素,因此,查询速度很快,然而插入和删除时,需要对元素移动空间,比较慢。
数组使用场景:频繁查询,很少增加和删除的情况。
2.链表
特点:元素可以不连续内存中,是以索引将数据联系起来的,当查询元素的时候需要从头开始查询,所以效率比较低,然而添加和删除的只需要修改索引就可以了
使用场景:少查询,需要频繁的插入或删除情况
3.队列
特点:先进先出,
使用场景:多线程阻塞队列管理非常有用
4.栈
特点:先进后出,就像一个箱子,
使用场景:实现递归以及表示式
5.数组与链表的区别
数组连续,链表不连续(从数据存储形式来说)
数组内存静态分配,链表动态分配
数组查询复杂度0(1),链表查询复杂度O(n)
数组添加或删除,复杂度o(n),链表添加删除,复杂度O(1)
数组从栈中分配内存。链表从堆中分配内存。
二。算法分类:
1)插入排序(直接插入排序、希尔排序)
2)交换排序(冒泡排序、快速排序)
3)选择排序(直接选择排序、堆排序)
4)归并排序
5)分配排序(基数排序)
所需辅助空间最多:归并排序
所需辅助空间最少:堆排序
平均速度最快:快速排序
不稳定:快速排序,希尔排序,堆排序。
1.直接插入排序
(1)基本思想:在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排
好顺序的,现在要把第n 个数插到前面的有序数中,使得这 n个数
也是排好顺序的。如此反复循环,直到全部排好顺序。
/**
* 插入排序法
*
* @param datas
*/
public static int[] sortInsert(int[] datas) {
for (int i = 1; i < datas.length; i++) {
int j = i - 1;
AlgorithmUtil.temp = datas[i];
for (; j >= 0 && AlgorithmUtil.temp < datas[j]; j--) {
datas[j + 1] = datas[j];
}
datas[j + 1] = AlgorithmUtil.temp;
}
return datas;
}
2.简单选择排序
(1)基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;
然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一
个数比较为止。
/**
* 选择排序
*
* @return
*/
public static int[] sortSelect(int[] datas) {
for (int i = 0; i < datas.length; i++) {
int index = i;
for (int j = i + 1; j < datas.length; j++) {
if (datas[j] < datas[index])
index = j;
}
if (i != index)
AlgorithmUtil.swap(datas, i, index);
}
return datas;
}
3.冒泡排序
(1)基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对
相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的
数比较后发现它们的排序与排序要求相反时,就将它们互换。
/**
* 冒泡排序
*
* @return
*/
public static int[] sortBubble(int[] datas) {
for (int i = 0; i < datas.length - 1; i++) {
for (int j = 0; j < datas.length - 1 - i; j++) {
if (datas[j] > datas[j + 1])
AlgorithmUtil.swap(datas, j, j + 1);
}
}
return datas;
}
4.快速排序
(1)基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,
将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其
排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
/**
* 快速排序;分割数组
*
* @param datas
*/
public static int QuickPartition(int[] datas, int left, int right) {
int pivot = datas[left];
while (left < right) {
while (left < right && datas[right] >= pivot)
--right;
datas[left] = datas[right]; // 将比枢轴小的元素移到低端,此时right位相当于空,等待低位比pivotkey大的数补上
while (left < right && datas[left] <= pivot)
++left;
datas[right] = datas[left]; // 将比枢轴大的元素移到高端,此时left位相当于空,等待高位比pivotkey小的数补上
}
datas[left] = pivot; // 当left == right,完成一趟快速排序,此时left位相当于空,等待pivotkey补上
return left;
} /**
* 快速排序;递归返回数组
*
* @param datas
*/
public static int[] sortQuick(int[] datas, int left, int right) {
if (left < right) {
int data = QuickPartition(datas, left, right);
sortQuick(datas, left, data - 1);
sortQuick(datas, data + 1, right);
}
return datas;
}
1.冒泡算法,2.选择算法,3.快速算法。4.插入算法,5.希尔算法,6.堆算法
public class AlgorithmUtil { public static int temp,index = 0; /**
* 临时值交换
*
* @param datas
* 数组
* @param i
* @param j
*/
public static void swap(int[] datas, int i, int j) {
temp = datas[i];
datas[i] = datas[j];
datas[j] = temp;
} /**
* 扩充数组长度
*
* @param datas
* @param value
* @return
*/
public static int[] expandArray(int[] datas, int value) {
if (datas.length <= index) {
int[] arrays = new int[datas.length * 2];
System.arraycopy(datas, 0, arrays, 0, datas.length);
datas = arrays;
}
datas[index] = value;
index++;
return datas;
}
}
目前记住。会冒泡。插入。选择。快速。算法。
最新文章
- JS详细入门教程(上)
- 在cwcity空间上安装phpmyadmin
- 进程物理内存远大于Xmx的问题分析
- Python小练习五
- C#集合类图继承关系一览表
- 数据库时间createtime字段 数据类型的选取
- SpringMVC使用静态资源
- 【总结】教你怎么将centos7打造成桌面系统
- ACM ICPC Team
- MPAndroidChart绘制图形表
- 高性能IO模型浅析(转)
- 手把手教你做一个Shell命令窗口
- orm总结
- Ehcache缓存配置以及基本使用
- <;Spark>;<;Tuning and Debugging>;
- 实验吧—隐写术——WP之 男神一般都很低调很低调的!!
- Smart Disk -- proposed by Liyuan Liu
- c++11——type_traits 类型萃取
- Java实现图片的裁剪
- TX 下常用的查询指令
热门文章
- 三. Java类与对象9. 源文件的声明规则
- Android中Context详解 ---- 你所不知道的Context(转)
- SQL SERVER 内存学习系列
- linux tail指令
- 在eclipse上部署openfire 3.9.1源码,並配置openfire
- python核心编程学习记录之多线程编程
- c++11 std::prev、std::next、std::advance与auto 使用
- iOS 执行时
- cocos2d-x 2.2.0 图片选中聚焦 ,图片描边 CCClippingNode 实现
- ES怎么进行字段添加索引,并保留原有数据