`
chasewinds
  • 浏览: 15999 次
  • 性别: Icon_minigender_1
  • 来自: 西安
文章分类
社区版块
存档分类
最新评论

数据结构有必要复习下了

阅读更多
声明:本文是转载

数据结构有必要复习下了


以下是我写的一些算法的实现,请多指教:

import java.util.Arrays;

public class 常用算法实现 {
    /**
     * 数据交换的方法
     * @param v
     * @param i
     * @param j
     */
    public static void swap(int[] v, int i, int j) {
        int temp = v[i];
        v[i] = v[j];
        v[j] = temp;
    }
   
   
    /**
     * 冒泡排序
     *
     * 使用场景:对已经经过初步排序的数据使用比较好
     *
     * 原理:扫描数据交换数据位置 对当前还未排好序的范围内的全部结点, 自上而下对相邻的两个结点依次进行比较和调整,
     * 让键值大的结点往下沉,键值小的结点往上冒。 即,每当两相邻比较后发现它们的排列顺序与排序要求相反时,就将它们互换。
     *
     * 时间复杂度:n的平方 空间复杂度:1
     *
     * 在冒泡排序中的核心部分是 for(i=0;i<n-1;i++) for(j=0;j<n-1-i;j++) if(a[j+1]<a[j])
     * swap(a[j],a[j+1]);
     */
    public static void bubbleUp(int list[]) {
        System.out.println("初始字符串:" + Arrays.toString(list));
        for (int i = 0; i < list.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < list.length - i - 1; j++) {
                if (list[j] < list[j + 1]) {
                    swap(list,j,j+1);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
            System.out.println("第" + (i + 1) + "次排列:" + Arrays.toString(list));
        }
        System.out.println("最终排列结果:" + Arrays.toString(list));
    }

    /**
     * 选择排序算法
     *
     * 试用场景:数据量比较少的情况下可以使用
     *
     * 原理:这是一个比较简单的算法,他的原理是,首先找到最小的数据 和第一个数据交换,然后再 找到次小的数据和第二个交换,以此类推.直到将数据排列好为止
     *
     * 时间复杂度: 2的n次方
     *
     * 空间复杂度:1
     *
     * @param args
     */
    public static void selectSort(int list[]) {
        System.out.println("初始字符串:" + Arrays.toString(list));
        for (int i = 0; i < list.length - 1; i++) {
            int min = list[i];
            for (int j = i + 1; j < list.length; j++) {
                if (min > list[j]) {
                    min = list[j];
                    swap(list,j,i);

                }
            }
            System.out.println("第" + (i + 1) + "次排列:" + Arrays.toString(list));
        }
        System.out.println("最终排列结果:" + Arrays.toString(list));
    }

    /**
     * 插入排序法 试用场景:数据量比较少的情况下 原理:是一种简单直观的排序算法; 从后到前在已排序数据中找到合适的位置插入进去
     * 初始可认为第一个数据已排序
     *
     * 时间复杂度:n的平方 空间复杂度: n
     *
     * @param args
     */
    public static void insertSort(int list[]) {
        System.out.println("初始字符串:" + Arrays.toString(list));
        // 注意:我们可认为第一个数据已排序,所以i是从1开始的
        for (int i = 1; i < list.length; i++) {
            int temp = list[i];
            int j = i;
            while (j > 0 && list[j] < list[j - 1]) {
                list[j] = list[j - 1];
                j--;
            }
            list[j] = temp;
            System.out.println("第" + i + "次排列:" + Arrays.toString(list));
        }
        System.out.println("最终排列结果:" + Arrays.toString(list));
    }

    /**
     * 快速排序算法
     *
     * 试用场景:数据量比较大的地方,如果有大量重复数据就比较麻烦
     *
     * 原理:首先检查待排序数组,如果<2个 直接推出程序,如果有超过 两个的数据,就选择一个分割点,将数据分成两个部分,小于分割点的分
     * 到一组,大于分割点的放到一组,然后对两组数据进行排序
     *
     * 时间复杂度:快速排序 O(n log n) 空间复杂度:1 splitIndex 划分数据的界限 items 最后字符的位置
     *
     * @param args
     */
    public static void quickSort(int list[], int startIndex, int items) {
        int j, last;
        /* 若数组包含的元素个数少于两个 */
        if (startIndex >= items)
        return;
        swap(list, startIndex, (startIndex + items) / 2); /* 将划分子集的元素移动到V[0] */
        last = startIndex; /* 用last记录中比关键字小间的最右位置 */
        for (j = startIndex + 1; j <= items; j++) /* 划分子集 */
        {
            if (list[j] < list[startIndex]) {
                swap(list, ++last, j);
            }
        }
        quickSort(list, startIndex, items - 1);
        quickSort(list, startIndex + 1, items);
    }

    public static void main(String args[]) {
        int list[] = { 800, 20, 70, 90, 50, 500, 400, 100, 850, 999, 1000, 0,-400 };
         bubbleUp(list);
         selectSort(list);
         insertSort(list);

    }
}


分享到:
评论

相关推荐

    计算机考研数据结构复习指导Word版

    这份"计算机考研数据结构复习指导Word版"提供了一条有效的学习路径,帮助考生们精准定位并攻克这个领域的关键点。 复习指导文档《复习指导(数据结构部分).doc》可能涵盖了以下内容: 1. **基本概念**:数据结构...

    数据结构与算法复习提纲(详细版)

    数据结构与算法复习提纲(详细版)是一个深入学习计算机科学基础的重要指南,它涵盖了从数学预备知识到高级数据结构及算法分析的核心内容。以下是对标题、描述以及部分章节内容的详细解读,旨在帮助读者更好地理解和...

    南邮数据结构考研复习指导

    本复习指导旨在帮助学生高效备考,深入理解并掌握数据结构的基本概念、算法设计与分析技巧。 数据结构是研究数据如何在计算机中存储和组织的学科。它涉及到如何有效地组织和管理大量数据,以便于快速访问和处理。在...

    C语言版数据结构复习练习题

    2. **链表**:链表是一种动态数据结构,每个元素(节点)包含数据和指向下一个节点的指针。链表分为单链表、双链表和循环链表等类型,提供了比数组更灵活的插入和删除操作。 3. **栈**:栈是一种后进先出(LIFO)的...

    数据结构复习纲要,数据结构的重点复习

    这份“数据结构复习纲要”将为我们提供一个全面的学习框架,帮助我们理解并掌握这个关键领域的重点。 1. **数组**:数组是最基础的数据结构,它在内存中分配连续的空间来存储相同类型的数据元素。数组的优点是访问...

    数据结构期末复习

    在“南邮数据结构复习资料”中,我们可以预见到涵盖了一系列与数据结构相关的概念、算法和实际应用。这些知识点是计算机科学专业学生,尤其是准备期末考试的学生必须要掌握的。 首先,我们要理解什么是数据结构。...

    数据结构考试复习资料

    综上所述,本套复习资料构建了一个全面的数据结构学习框架,既包含了必要的理论知识,又不乏实践操作。初学者在使用这份资料时,应该遵循复习大纲的指引,逐步深入学习,并结合PPT进行形象化理解。在对理论知识有所...

    广工数据结构复习及试卷

    在“广工数据结构复习及试卷”中,我们可预期涵盖了一些关键概念和算法,这对于准备考试或进一步理解这门学科至关重要。 1. **数组**:数组是最基础的数据结构,它是一系列相同类型元素的集合,通过索引访问。了解...

    数据结构复习题

    通过做“数据结构复习题”中的题目,你可以深入理解这些概念,并提高实际问题解决能力。同时,还要注意理论与实践相结合,编写代码来实现这些数据结构和算法,以加深理解。祝你在考研路上一切顺利!

    数据结构复习内容和答案

    本资源“数据结构复习内容和答案”提供了全面的数据结构练习题及答案,共计1800题,涵盖了数据结构的所有重要概念和算法。 1. **数组**:数组是最基础的数据结构,它是一系列相同类型元素的集合,通过索引访问。...

    数据结构考研复习

    在数据结构的学习中,理解并能实现这些基本操作是基础,也是必要的。顺序表的操作通常包括插入、删除、查找等,这些操作的时间复杂度与数据结构的实现方式密切相关。对于数组实现的顺序表,由于所有元素都在连续的...

    数据结构各章复习资料

    数据结构作为计算机科学中的一项基础学科,其重要性不言而喻。它不仅涉及数据的存储...因此,定期的复习和整理所学知识点是十分必要的,只有这样,我们才能更好地把握数据结构的精髓,并在实际问题中游刃有余地应用。

    数据结构复习资料

    同时,了解数据结构在操作系统、数据库、网络和人工智能等领域的应用也是必要的。 在复习过程中,可以结合实际问题进行练习,如构建和操作数据结构,解决相关的编程挑战。通过这种方式,不仅能巩固理论知识,还能...

    南邮数据结构C语言期末复习

    本文旨在对南邮数据结构C语言课程期末复习进行梳理,系统地回顾和巩固课程中所涉及的关键知识点,帮助学生更好地准备期末考试。 首先,单链表作为线性表的一种实现方式,其灵活性体现在元素的动态添加和删除。在...

    数据结构复习 方便你的数据机构复习

    数据结构是计算机科学中的核心课程,它探讨了数据在计算机中的组织和管理方式。本复习内容涵盖了《数据结构》的重要...数据结构的知识将对后续的编程和软件开发工作产生深远影响,因此深入理解和熟练掌握是非常必要的。

    数据结构考研复习纲要.pdf

    同时,复习时可以参考《全国硕士研究生入学统一考试计算机学科专业基础综合考试大纲解析(2013年版)》以及《数据结构学习指导与典型题解》和《数据结构与算法—学习指导与习题解析》等书籍,这些资料能帮助考生理解和...

    数据结构总复习.docx

    本复习资料涵盖了数据结构的主要方面,包括基本概念、线性表、栈与队列、串、数组与广义表、树与二叉树以及图。 首先,数据元素是数据的基本组成单元,而数据结构则是一组具有特定关系的数据元素集合。数据类型不仅...

    数据结构课后习题 期末复习

    在数据结构的学习过程中,理解这些基本概念和理论之后,通过大量的练习和复习来巩固知识点是十分必要的。例如,线性表的操作包括查找、插入和删除等,这些操作在顺序存储和链式存储的线性表中实现方式有所不同,因此...

Global site tag (gtag.js) - Google Analytics