【蓝桥杯-筑基篇】排序算法

这篇具有很好参考价值的文章主要介绍了【蓝桥杯-筑基篇】排序算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🍓系列专栏:蓝桥杯

🍉个人主页:个人主页

目录

前言:

一、冒泡排序

二、选择排序

三、插入排序

四、图书推荐


前言:

算法工具推荐:

 还在为数据结构发愁吗?这款可视化工具,帮助你更好的了解其数据结构数据结构和算法动态可视化 (Chinese) - VisuAlgo

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法

一、冒泡排序

1.什么是冒泡排序?

冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就象水底下的气泡一样逐渐向 上冒。

思想:

我们要把相邻的元素两两比较,当一个元素大于右侧相邻元素时,交换它们的位置;当一个元素小于右侧相邻元素时,位置不变

动图演示:

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法
 

                                      

2.冒泡排序代码实现

 代码1:

import java.util.Arrays;

public class bubble {
    public static void main(String[] args) {
        int arr[]={5,8,6,3,9,2,1,7};
        System.out.println("排序前:"+Arrays.toString(arr));
        BubbleSort(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
    }

    private static void BubbleSort(int[] arr) {
        int temp=0; //临时存储变量
        int n=0; //统计排序次数


        for (int i = 1; i < arr.length; i++) {
            n++;
            for (int j = 0; j < arr.length-i; j++) {

                if (arr[j]>arr[j+1]){
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;


                }

            }
            System.out.println("第"+n+"轮:"+Arrays.toString(arr));
        }
    }


}

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法

 3.冒泡排序代码优化

优化:
因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

代码2(第一次优化):

import java.util.Arrays;

public class bubble {
    public static void main(String[] args) {
        int arr[]={5,8,6,3,9,2,1,7};
        System.out.println("排序前:"+Arrays.toString(arr));
        BubbleSort(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
    }

    private static void BubbleSort(int[] arr) {
        int temp=0; //临时存储变量
        int n=0; //统计排序次数

        for (int i = 1; i < arr.length; i++) {
            n++;
            boolean flag=true;

            for (int j = 0; j < arr.length-i; j++) {


                if (arr[j]>arr[j+1]){
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                    flag=false;


                }

            }
            if (flag==true){
                break;
            }

            System.out.println("第"+n+"轮:"+Arrays.toString(arr));
        }
    }


}

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法

与第1版代码相比,第2版代码做了小小的改动,利用布尔变量flag作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,则说明数列已然有序,然后直接跳出大循环。

这只是冒泡序优化的第一步,我们还可以进一步来提开它的性能。为了说明问题,这次以一个新的数列为例。

为了说明问题,这次以一个新的数列为例

arr={3,4,2,1,5,6,7,8}

import java.util.Arrays;

public class bubble {
    public static void main(String[] args) {
        int arr[]={3,4,2,1,5,6,7,8};
        System.out.println("排序前:"+Arrays.toString(arr));
        BubbleSort(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
    }

    private static void BubbleSort(int[] arr) {
        int temp=0; //临时存储变量
        int n=0; //统计排序次数

        for (int i = 1; i < arr.length; i++) {
            n++;
            boolean flag=true;

            for (int j = 0; j < arr.length-i; j++) {
                System.out.println("排序:"+Arrays.toString(arr));

                if (arr[j]>arr[j+1]){
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                    flag=false;


                }

            }
            if (flag==true){
                break;
            }

            System.out.println("第"+n+"轮:"+Arrays.toString(arr));
        }
    }


}

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法

 第一轮中:

元素4和5比较,发现4小于5,所以位置不变。

元素5和6比较,发现5小于6,所以位置不变。

元素6和7比较,发现6小于7,所以位置不变。

元素7和8比较,发现7小于8,所以位置不变。
 

第二轮中:

元素3和4比较,发现3小于4,所以位置不变。

元素4和5比较,发现4小于5,所以位置不变。

元素5和6比较,发现5小于6,所位位置不变。

元素6和7比较,发现6小于7,所以位置不变。

元素7和8比较,发现7小于8,所以位置不变。

.................................................................

按照现有的逻辑,有序区的长度和排序的轮数是相等的。例如第1轮排序过后的有序区长度是1,第2轮排序过后的有序区长度是2....

实际上,数列真正的有序区可能会大于这个长度,如上述例子中在第2轮排序时,后面的5个元素实际上都已经属于有序区了。因此后面的多次元素比较是没有意义的。

那么,该如何避免这种情况呢?我们可以在每一轮排序后, 记录下来最后一次元素交换的位置,该位置即为无序数列的边界,再往后就是有序区了。

 4.冒泡排序代码再次优化

代码3:

import java.util.Arrays;

public class bubble {
    public static void main(String[] args) {
        int arr[]={3,4,2,1,5,6,7,8};
        System.out.println("排序前:"+Arrays.toString(arr));
        BubbleSort(arr);
        System.out.println("排序后:"+Arrays.toString(arr));
    }

    private static void BubbleSort(int[] arr) {
        int temp=0; //临时存储变量
        int n=0; //统计排序次数
        int lastIndex= 0;//记录最后一次交换的位置
        int sortBorder= arr.length-1;//无序数列的边界

        for (int i = 1; i < arr.length; i++) {
            n++;
            boolean flag=true;

            for (int j = 0; j < sortBorder; j++) {
                System.out.println("排序:"+Arrays.toString(arr));

                if (arr[j]>arr[j+1]){
                    temp=arr[j+1];
                    arr[j+1]=arr[j];
                    arr[j]=temp;
                    lastIndex=j;
                    flag=false;


                }

            }
            sortBorder=lastIndex;
            if (flag==true){
                break;
            }

            System.out.println("第"+n+"轮:"+Arrays.toString(arr));
        }
    }


}

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法
 

二、选择排序

基本介绍:

选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。

思想:

选择排序 (select sorting) 也是一种简单的排序方法。它的基本思想是: 第一次从 arr[0]~arr[n-1]中选取最小值,与arr[0]交换,第二次从 ar[1]~arr[n-1]中选取最小值,与 arr[1]交换,第三次从 ar[2]~arr[n-1]中选取最小值,与 arr[2]交换,.................,第 i 次从arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,.............,第n-1 次从arr[n-2] ~ arr [n-1]中选取最小值,与 arr[n-2]交换,总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列。

1.选择排序

    //普通选择排序
    public static void sort1(int[] array){
        int count = 0;//统计运行次数
        int cnt = 0; //交换次数
        for(int i=0;i<array.length-1;i++) {
            int min=array[i];
            int minIndex=i;
            count++;
            for(int j=i+1;j<array.length;j++){
                if(min>array[j]) {
                    min=array[j];
                    minIndex=j;
                }
            }
            if(minIndex!=i){
                cnt++;
                array[minIndex]=array[i];
                array[i]=min;
            }
 
 
        }
        System.out.println(Arrays.toString(array));
        System.out.println("运行次数:"+count+"次  交换次数:"+cnt);
 
    }

2.优化版

 
import java.util.Arrays;
import java.util.Random;
 
/**
 * 选择排序优化
 */
class SelectionSort2 {
    public static void main(String[] args) {
        //产生一个随机数组
        Random r = new Random();
        int arr[] = new int[2000];
        for(int i=0;i<arr.length;i++){
            arr[i] =r.nextInt(1000);
        }
 
//因为本优化版本每次循环找出最大以及最小值,所以执行执行:arr.length/2
        int ArrLength = (arr.length/2);
        int  temp1,temp2;
        long count = 0;
        //记录开始时间
        long startStamp = System.currentTimeMillis();
        //算法开始
        for(int j=0;j<ArrLength;j++){
            int minIndex = j;
            int maxIndex= j;
            for(int i=j;i<arr.length-j;i++){
                if (arr[minIndex] > arr[i]) {
                    minIndex = i;
                }
                if (arr[maxIndex] < arr[i]) {
                    maxIndex= i;
                }
                count++;
            }
            temp1  = arr[minIndex];
            arr[minIndex] = arr[j];
            arr[j] = temp1;
 
            if(j!=maxIndex) {	//maxIndex不能再原本的minIndex位置上
                temp2 = arr[maxIndex];
                arr[maxIndex] = arr[arr.length - j - 1];
            }else{
                temp2 = arr[minIndex];
                arr[minIndex] = arr[arr.length - j - 1];
            }
            arr[arr.length - j - 1] = temp2;
        }
        //计算算法结束时间
        long endStamp = System.currentTimeMillis();
        System.out.println("用时总长:"+(endStamp-startStamp));
        System.out.println("循环次数:"+count);
 
 
        System.out.println(Arrays.toString(arr));
    }
}

三、插入排序

插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n -1 个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

Java实现插入排序的代码如下:

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

上面的代码使用了两重循环,外层循环枚举未排序部分的元素,内层循环在已排序部分中找到适当的位置并进行插入。

这段代码的时间复杂度为O(n^2),空间复杂度为O(1)。

四、图书推荐

《经典算法的起源》是一本计算机算法方面的科普性书籍,作者以通俗易懂、引人入胜的叙述方式介绍各种算法思想,避免使用一些过于严谨的专业术语。比如,用“大海捞针”来形容一种搜索算法就非常形象,顾名思义,广大读者更容易理解该搜索策略。本书适合对计算机知识有兴趣的初中生、高中生或其他相关人员阅读。计算机专业一、二年级的大学生阅读此书,也会对相关知识的起源有深刻的印象。

本书的目的是向非专业人士介绍算法,使读者理解算法如何运作,而不是阐述算法在生活中的作用。有些书籍在某些方面做了杰出工作,如介绍如何改善大数据的处理,讨论将人工智能和计算设备融入日常生活对人类生存条件的改变。本书对“发生什么”不感兴趣,对“如何发生”感兴趣。为此,本书给出一些真实的算法,不仅描述它们做什么,更重要的是关注它们如何运作。本书将提供详细的解释说明,而非粗略的介绍。

【蓝桥杯-筑基篇】排序算法,蓝桥杯,算法,java,开发语言,数据结构,排序算法

 本书由机械工业出版社提供文章来源地址https://www.toymoban.com/news/detail-785916.html

到了这里,关于【蓝桥杯-筑基篇】排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法修炼之筑基篇——筑基一层中期(解决01背包,完全背包,多重背包)

    ✨ 博主: 命运之光​​​​​​ 🦄 专栏: 算法修炼之练气篇​​​​​ 🍓 专栏: 算法修炼之筑基篇 ✨ 博主的其他文章: 点击进入博主的主页​​​​​​ 前言: 学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的

    2024年02月08日
    浏览(32)
  • 百日筑基篇——python爬虫学习(一)

    百日筑基篇——python爬虫学习(一) 随着学习的深入,有关从各种不同的数据库中以及互联网上的海量信息,如何有选择性的爬取我们所需的数据以方便我们的数据分析工作,爬虫的学习是必要的。 Python爬虫是指使用Python编程语言编写的程序,通过模拟浏览器行为从网页中

    2024年02月13日
    浏览(50)
  • MySQL筑基篇之增删改查

    ✅作者简介:C/C++领域新星创作者,为C++和java奋斗中 ✨个人社区:微凉秋意社区 🔥系列专栏:MySql一点通 📃推荐一款模拟面试、刷题神器👉注册免费刷题 🔥前言 本文将承接前两篇MySQL专栏的博文,讲解数据库的 增删改查 操作,这里的查询确切的说应该是初级的查询,不

    2024年02月12日
    浏览(52)
  • 数据结构——排序算法(C语言)

    本篇将详细讲一下以下排序算法: 直接插入排序 希尔排序 选择排序 快速排序 归并排序 计数排序 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某写的大小,按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中,存在多个

    2024年02月08日
    浏览(62)
  • 数据结构与算法——排序(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年04月09日
    浏览(55)
  • 内部排序算法比较-数据结构C语言课设

    名称: 内部排序算法比较 内容: 在教科书中,各种内部排序算法的时间复杂的分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各种算法的比较次数和移动次数,以取得直观感受。 任务: (1)对以下7中常会用的内部排序算法进行比较

    2024年02月12日
    浏览(53)
  • 算法 数据结构 递归插入排序 java插入排序 递归求解插入排序算法 如何用递归写插入排序 插入排序动图 插入排序优化 数据结构(十)

    1. 插入排序(insertion-sort):                                           是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入     算法稳定性:                  

    2024年02月09日
    浏览(53)
  • 第11章:C语言数据结构与算法初阶之排序

    排序是一种非常重要的算法。 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,

    2024年02月12日
    浏览(44)
  • 【数据结构】用Java实现七大排序算法

    目录 🌷1. 排序的概念及引用 1.1 排序的概念 1.2 衡量指标 1.2 十个排序算法  1.3 十个排序性能对比 🌷2. 冒泡排序 2.1 算法描述 2.2 动图 ⭐️代码优化 🌷3. 选择排序 3.1 算法描述 3.2 动图  3.3 代码 🌷4. 插入排序 4.1 算法描述 4.2 动图  4.3 代码 🌷5 希尔排序 5.1 描述 5.2 动图  

    2023年04月23日
    浏览(49)
  • 【算法与数据结构】Java实现查找与排序

    也叫做折半查找,属于有序查找算法。 前提条件 :数组数据必须有序,从小到大,或者从大到小都是可以的。 如果是无序的,也可以先进行排序。 但是排序之后,会改变原有数据的顺序,查找出来元素位置跟原来的元素可能是不一样的,所以排序之后再查找只能判断当前数

    2024年01月19日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包