1949啦网--小小 痛苦,是因为能力和欲望不匹配造成的

数据结构与算法

今天的突然看集合底层的时候发现了好多算法和数据结构。再次就比较一下和汇总一下。

数据结构分类:线性结构和非线性结构

问题一:

什么是线性和非线性;

我个人的理解是:数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构;

线性结构包括:数组,链表,队列,栈;

非线性结构包括:树,图,表;

详解:

一:线性结构

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;  

}  

}  

目前记住。会冒泡。插入。选择。快速。算法。

原文链接:https://www.qiquanji.com/post/8421.html

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。

微信扫码关注

更新实时通知

作者:xialibing 分类:网页教程 浏览: