精华内容
下载资源
问答
  • 冒泡排序理解与算法优化 冒泡排序为基本内部排序算法(即不借助外部空间,内部自我排序), 如上图,冒泡排序经过不断比较相邻的元素的值,进行交换,第一次从第一个元素到最后一个元素的交换,会将该数组的最大值交换到...

    冒泡排序理解与算法优化

    冒泡排序为基本内部排序算法(即不借助外部空间,内部自我排序),
    在这里插入图片描述
    如上图,冒泡排序经过不断比较相邻的元素的值,进行交换,第一次从第一个元素到最后一个元素的交换,会将该数组的最大值交换到最后一项,以此循环,我们不断地找出剩余元素中的最大值,并将该最大值移动到剩余元素中的最大值.最终排序成功,本文采取从小到大排序.
    (本文中语言使用c语言,算法利用函数实现,编译器参考DEV C++)
    在这里插入图片描述

    void Bubble_sort(int *a,int len)//函数传递数组名字以及数组长度
    {   int i,j,k;
       int temp;// 采用中间变量法
        for(i=0;i<len;i++){
    	  for(j=0;j<len-i-1;j++){//剩余元素的最大值是不断向前移动
    		  if(a[j]<a[j+1]){
    			temp=a[j];
    			a[j]=a[j+1];
    			a[j+1]=temp;
    		}
    }
    }}
    

    如上图:最基本的冒泡排序.
    思考一:如果中间一次排序成功,那么后面就没有必要进行比较,我们可以定义一个变量,如果没有进行交换,那么排序结束,即排序成功.
    代码如下

    void Bubble_sort(int *a,int len)//函数传递数组名字以及数组长度
    {  int i,j,k;
       int temp;// 采用中间变量法
       int change=1;
        for(i=0;i<len&&change;i++){//进行交换后才进行下一次循环
          change=0;//change被赋值为0
    	  for(j=0;j<len-i-1;j++){
    		  if(a[j]<a[j+1]){
    			temp=a[j];
    			a[j]=a[j+1];
    			a[j+1]=temp;
    			change=1;
    		}
    }
    }}
    

    思考二:上述排序可不可以再优化一下呢?
    如果中间的某一次排序恰好使得后面的数字有序,那么我们就不需要再对这些有序的数字进行排序,那么如何才能实现这个功能呢?
    可以通过记录上一次最后一次交换的位置,下一次排序从第一个比较到上次记录的位置,即设置结界边界.
    代码如下:

    void Bubble_sort(int *a,int len)//函数传递数组名字以及数组长度
    {  int i,j,k;
       int temp;// 采用中间变量法
       int change=1,k=size-1,pos;//pos记录当前边界.
        for(i=0;i<len&&change;i++){//进行交换后才进行下一次循环
          change=0;//change被赋值为0
    	  for(j=0;j<k;j++){
    		  if(a[j]<a[j+1]){
    			temp=a[j];
    			a[j]=a[j+1];
    			a[j+1]=temp;
    			change=1;
    			pos=j;
    		}
    }
    k=pos;//改变当前结界
    }}
    

    思考三:上述冒泡排序还能再优化吗?
    当然可以,考虑双向冒泡排序(又称鸡尾酒排序),即每一次外层循环,内层循环进行从左向右和从右向左的排序.并且该双向排序都采用思考一与思考二的优化方式.
    冒泡最终优化代码如下:

    void Bubble_sort(int *a,int len){
    	int i,j,k,maxindex,minindex,index1=len-1,index2,judgement=1,temp;
    	// i,j,k用来控制循环次数,maxindex,minindex为双向排序的正向结界边界与逆向结界边界,
    	for(i=0;i<len-1&&judgement;i++){
    		judgement=0;
    		for(j=0;j<index1;j++){
    			if(a[j]>a[j+1]){
    				temp=a[j];
    				a[j]=a[j+1];
    				a[j+1]=temp;
    				judgement=1;
    				maxindex=j;
    			}
    		}
    		index1=maxindex;//正向排序结界
    		for(j=index1;j>minindex;j--){
    			if(a[j]<a[j-1]){
    				temp=a[j];
    				a[j]=a[j-1];
    				a[j-1]=temp;
    				judgement=1;
    				index2=j;
    			}
    		}
    		minindex=index2;
    	}
    minindex++;//剩余元素的最小值是不断地向后移动,所以minindex++.			
    }
    

    上述即为冒泡排序的个人理解与优化.
    思考:可以看到冒泡排序的基本思想就是不断地比较和交换,各类优化也只是在减少不必要的交换次数或者是比较次数.双向排序也可以大大减少排序所需时间,但在处理一些较大数据时,冒泡排序的性能远达不到要求.
    这里引用一句话:
    在这里插入图片描述

    展开全文
  • 对于冒泡排序及冒泡排序优化的一点理解冒泡排序的一点心得优化冒泡排序外循环优化:内循环优化: function bubbleSort(arr) { // 外层循环控制比较的轮数 for(let i=0; i<arr.length-1; i++){ // 内层循环...

    对于冒泡排序及冒泡排序的优化的一点理解

    function bubbleSort(arr) {
                // 外层循环控制比较的轮数
                for(let i=0; i<arr.length-1; i++){
                    // 内层循环控制比较的次数
                    for(let j=0; j<arr.length-1-i; j++){
                        if(arr[j] > arr[j+1]){
                            // 当前一项比后一项大,进行交换
                            [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
                        }
                    }
                }
                return arr
            }
    

    冒泡排序的一点心得

    1. 发现一个规律,既然每次都是当前一项比后一项大的时候才交换,这就说明
      如果当前项是未到最终位置的数据中最大的,那么这个元素势必会在一轮排序中
      一直进行交换直到交换到最终的位置上。所以在冒泡排序中一轮排序势必会确定好
      一个元素的最终位置,那么下一轮排序的次数就会减少一次
    2. 外层循环arr.length-1的来历:
      内循环一次就可以确定一个元素的位置,但不是数据有多少个就得内循环多少次,
      在第arr.length-1次循环结束的时候,因为交换的动作是相互的,在第arr.length-1次的排序中
      ,一轮就确定了两个元素的最终位置。所以外循环只用走arr.length-1次就完成了。
    3. 内循环arr.length-1-i的来历:
      外层的i值,是控制冒泡排序的整个轮数,而只要有元素的最终位置被确定那么这个轮数自然会减小。
      当i=0时:意味着当前是第一轮排序,也意味着还没有元素被排到最终位置上,所以这个0就是没有元素
      在最终位置上,那么arr.length-1-i的这些个元素还需要在内循环被排序,也就是内循环还需要
      arr.length-1-i次。

    优化冒泡排序

    外循环优化:

    当某一轮(非最后一轮)内循环里没有发生交换动作时,就说明该组数据已经有序。
    后序的外层循环可以不用再走了,这是对外层循环的优化。

    内循环优化:

    既然每一次内循环都可以确定一个元素的最终位置,其实这个元素不是任意元素
    而是,未排序元素里的最大值的元素,所以该元素确定的最终位置以及其之后的元素
    位置必然都是有序的。
    那么下一轮内循环的时候j的值就应该取到已有序的元素之前,这样进一步来缩小内
    循环的次数。

    function bubbleSort1(arr) {
                let lastChangeIndex = 0 //最后一次交换的位置
                let flag = false // 标记是否交换
                for(let i=0; i<arr.length-1; i++) {   
                    let sortBorder = arr.length-1-i //交换边界的初始值
                    for(let j=0; j<sortBorder; j++) {
                        if(arr[j] > arr[j+1]) {
                            [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
                            lastChangeIndex = j // 最后一次交换的位置
                            flag = true //如果进行交换就改变flag的值
                        } 
                    }
                    sortBorder = lastChangeIndex // 把最后一次交换的位置赋值给交换边界
                    if(!flag) {
                        break
                    }
                }
                return arr
            }
    
    展开全文
  • 数据结构学习笔记之冒泡排序 ...这就是一轮排序代码很容易理解 import java.util.Arrays; public class BubbleSort { public static void main (String[] args) { int arr[] = {3, 15, 151, 181, 81, 2,...

    数据结构学习笔记之冒泡排序

    欢迎各位大佬指出我的错误以及可以改进的地方

    • 冒泡排序是一种稳定排序,因为比较和交换发生在两个相邻元素之间,通过相邻元素的比较,如果不是顺序排列则交换位置,是则从下一个元素开始。
      这就是一轮排序代码很容易理解
    import java.util.Arrays;
    
    public class BubbleSort {
    	public static void main (String[] args) {
    		int arr[] = {3, 15, 151, 181, 81, 2, 8, 1};
    
    		boolean flag = false;
    		for (int j = 0; j < arr.length - 1; j++) {
    			for (int i = 0; i < arr.length - 1 - j; i++) {
    				if (arr[i] > arr[i + 1]) {
    					int temp = arr[i + 1];
    					arr[i + 1] = arr[i];
    					arr[i] = temp;
    					flag = true;
    				}
    			}
    			if (flag==false)
    				break;
    			else
    				flag=false;
    		}
    		System.out.println (Arrays.toString (arr));
    	}
    }
    

    如果经过比较未进入交换则flag为false,即顺序排列跳出循环。
    这就能基本上完成冒泡排序但是会遇到这种情况:
    例如有一串数组{2,3,4,5,6,7,1}
    前面都是排好的顺序但唯独最后一个是最小的,这样还是会一步一步的替换比较。
    对此我们进行优化,将单向冒泡改为双向冒泡。
    代码如下:

    		long start=System.currentTimeMillis ();
    		boolean flag = false;
    		for (int j = 0; j < arr.length - 1; j++) {
    			for (int i = j; i < arr.length - 1 - j; i++) {
    				if (arr[i] > arr[i + 1]) {
    					int temp = arr[i + 1];
    					arr[i + 1] = arr[i];
    					arr[i] = temp;
    					flag = true;
    				}
    			}
    			if (flag==false)
    				break;
    			else
    				flag=true;
    
    			for (int i= arr.length-1-j; i>0;i--){
    				if (arr[i-1] > arr[i]) {
    					int temp = arr[i];
    					arr[i] = arr[i-1];
    					arr[i-1] = temp;
    					flag = true;
    				}
    			}
    				if (flag==false)
    					break;
    				else
    					flag=true;
    		}
    

    最后这只是一个小思考,希望有大佬能给我更多的指点。

    展开全文
  • 冒泡排序理解 今天学习到冒泡排序,整个人很懵,相信很多初学者和我一样,都相当懵,今天我就来分享一下我的思路。 首先先上代码,我是在哔哩哔哩,狂神说java学的 package scanner; import java.util.Arrays; ...

    冒泡排序理解

    今天学习到冒泡排序,整个人很懵,相信很多初学者和我一样,都相当懵,今天我就来分享一下我的思路。

    首先先上代码,我是在哔哩哔哩,狂神说java学的

    package scanner;
    import java.util.Arrays;
    public class Arrays02 {
        public static void main(String[] args){
            int[] a = {3,5,2,1,4};
            int[] sort = sort(a);
            System.out.println(Arrays.toString(sort));
    
        }
        //冒泡排序
        //1.比较数组中,两个相邻的元素,如果第一个数比第二个数大,我们就交换他们的位置
        //2.每一次比较,都会产生出一个数,或者最小的数字;
        //3.下一轮可以少一次排序
        //4.依次循环,直到结束!
        public static int[] sort(int[] array){
            //临时变量
            int temp = 0;
            //外层循环,判断我们这个要走多少次;
            for (int i = 0; i < array.length - 1; i++) {
                boolean flag = false;//减少没有意义的比较
                //内层循环,比较两个数,如果第一个数,比第二个数大,则交换位置
                for (int j = 0; j < array.length-1-i; j++) {
                    if(array[j]>array[j+1]){
                        temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                        flag = true;
                    }
                }
                    if(flag==false){
                    break;
                }
            }
            return array;
        }
    }
    

    先说第一个让我懵逼的点,就是

     for (int j = 0; j < array.length-1-i; j++) 
    

    前面i<array.length-1能理解是什么意思,就是为了防止溢出,因为数组的下标是从0开始的,比方说int [] i = {5,2,1,3}

    这个数组有4个数如果直接i<4的话,因为后面自增是i++,程序就会运行0,1,2,3,4就会直接溢出数据,所以需要-1。(我也不知道为什么for后面不能是++i 这样岂不是更好用?)

    而j < array.length-1-i,为什么要-i呢?其实就是为了不再去重复比较已经排好的值。

    举个例子

    第一次运行,-i此时i=0,int [] i = {5,2,1,3}第一遍运行排序完毕了,顺序就是:2,1,3,5,那么5其实是不用再去排序了,第二次遍运行的时候,-i,i=1,就是为了减掉已经排序的5。

    第二遍排序完了,顺序是:1,2,3,5,第三次运行的时候-i,i=2,就是为了减掉已经排好的3,5这两个数,以此类推。

    其实排序到这里就会发现,已经不会再交换数字了,继续排序是无效的,浪费时间的。

    所以就用到了优化的代码:

    boolean flag = false;

    flag = true;

    if(flag==false){
    break;}

    首先boolean flag = false;是默认数组不需要再进行比较交换

    用上面的例子int [] i = {5,2,1,3},当i=1的时候,数组就已经排序完成了,当i=2的时候,就没有能满足for (int j = 0; j < array.length-1-i; j++)条件的数值了,所以就会直接返回 flag = false,此时就会判断最后的语句,if(flag==false){
    break;}直接中断循环

    展开全文
  • 本文将从0开始编写快速排序的代码。希望阅读者最好要自己作图,思考执行过程,自己动手实现代码,如果默写代码,甚至背诵代码,就是本末倒置了。 2. 文章结构 主要讲解一路快排,二路快排和三路快排的实现过程,作...
  • 冒泡排序 冒泡排序,作为最基础的算法之一,属于选择...本篇主要通过Javascript来实现冒泡排序以及其优化过程。 1、冒泡排序 function popoSort(arr=[]){ if(arr.length <= 0) { return arr; } const...
  • 目录一、Bubble Sort的核心思想二、代码实现三、优化处理 一、Bubble Sort的核心思想 二、代码实现 三、优化处理
  • 一、排序算法 a. 一次扫描性能高,减少了io随机请求的次数 b. 排序操作是在内存(sort_buffer)里面进行的, 先select结果再进行排序,如果结果值大于max_length_...二、优化思路 a. 尽量减少io的读取 max_lengt...
  • 冒泡排序法的基本思想就是:数组内容从前往后相邻的两个数依次进行比较,把较大的数往后移动,从而一轮最终把最大的数放最后面。 int a[]={7,5,8,3}; //1轮1次比较:7和5交换,结果为{5,7,8,3} //1轮2次比较:7和8...
  • 冒泡排序优化

    2019-09-25 14:40:31
    最常用的是冒泡排序,代码容易理解,容易编写。用了多年才发现还有个地方可以优化一下,或许能减少运算次数,也就提高了效率。发文章来巩固一下。个人水平有限,如有错误,还请指正mr.li.ming@qq.com。 原理:按...
  • 冒泡排序优化

    2018-04-20 13:20:50
    冒泡排序是非常好理解的,以从小到大排序为例,每一轮排序就找出未排序序列中最大值放在最后。
  • 写在前面,排序算法属于面试中绝对不会错过的一道题,不管是原理,手撕,变形,优化,全都是考点。接下来更的几篇文章争取全面考虑,从面试官的角度解析排序算法以及对应回答~如果喜欢的话可以点赞收藏关注!及时...
  • 以下是本人学习极客时间的专栏《数据结构与算法之美》后,自己动手敲...可以简单地这样理解,插入排序就是就是往一个有序的数列中添中新的数据,插入之后保证数据列仍然有序,因此叫插入排序。 那么具体是如何实现的...
  • 虽然效率差一点,但好在具有结构简单,容易理解,易于操作等优点。冒泡排序就是把小的元素往前调或者把大的元素往后调。在相邻的两个元素间比较,交换也发生在这两个元素之间。 冒泡排序是一种稳定排序算法,在排序...
  • 冒泡排序及其优化

    2019-09-13 03:42:34
    根据自己的理解进行了优化。 如果对数组进行正序排序,第一轮冒泡排序后,最大值被交换到最后一位。所以下一轮只对前n-1个数进行交换排序。如果,前n-1个数已经是正序排列,就不需要进行交换了,也就是排序可以结束...
  • 冒泡排序优化

    千次阅读 2021-03-21 19:45:45
    import java.util.Arrays; /** * @创建人 wdl * @创建时间 2021/3/21 * @描述 ...public class BubbleSort { public static void main... //为了容易理解,我们吧冒泡排序的演变过程给大家展示 //第一趟排序,就
  • C 冒泡排序 冒泡排序优化

    千次阅读 2016-01-07 14:33:24
    本文包含冒泡排序的三种实现方式 分别为冒泡排序初级版,升级版,终级版(自己起的名字) 使用时只要使用终极版就本以了,终级版为升级版的优化版本 至于初极版和升级版只是为了帮助理解 冒泡排序的时间复杂度为O(n²)
  • 交换类排序 基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来...冒泡排序是一种非常容易理解排序 时间复杂度:O(N^2) 空间复杂度:O(1) 稳定性:稳定 代码实现 void BublleSort(int*array, int size...
  • 在前几篇博客中讲了计数排序的一般方法,理解起来比较简单。但是上一次提到的计数排序只是简单的按照数组下标统计输出了元素的值,并没有真正将原来的数据进行排序。在日常的使用当中,往往会出现相同的数据进行排序...
  • 冒泡排序是最常见也是非常容易理解的一个排序方法; 我们直接上代码 function bubbleSort(arr){ for(let i=0;i<arr.length-1;i++){ for(let j=0;j<arr.length-i-1;j++){ if(arr[j]>arr[j+1]){ //...
  • 排序是在日常编写程序的过程中,经常遇到的问题,排序的方法分为很多种,本文介绍排序算法中最容易理解的冒泡排序以及冒泡排序的的优化过程,直接上代码: #include"stdafx.h" #include"stdlib.h" #include"math.h...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,347
精华内容 538
热门标签
关键字:

优化排序理解