浅谈JAVA数据结构和算法

曾经终败给现在 2023-07-01 08:44 65阅读 0赞

浅谈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;  
    \}  
    \}