精华内容
下载资源
问答
  • 排序之冒泡排序

    2021-06-17 11:01:24
    冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序(前一个数大于后一个数)则交换,使值较大的元素逐渐从前移后部,就象水底下的...

    冒泡排序的介绍

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

    通过简单的demo理解冒泡排序的规律

    public class BubbleSort {
        public static void main(String[] args) {
            int[] arr = {3, 9, -1, 10, -2}; // 定义个长度为5的数组
    
            int temp = 0;
    
            // 第一次循环,将第一大数字移到最右边,进行了四次比较
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第1次循环:" + Arrays.toString(arr));
    
            // 第二次循环,将第二大数字移到最右边,共比较三次
            for (int j = 0; j < arr.length - 1 - 1; j++) { // 最右边的数已经排好序,不需要比较,所以 减1
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第2次循环:" + Arrays.toString(arr));
    
            // 第三次循环,将第三大数字移到最右边,共比较二次
            for (int j = 0; j < arr.length - 1 - 2; j++) { // 最右边两个数数已经排好序,不需要比较,所以 减2
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第3次循环:" + Arrays.toString(arr));
    
            // 第四次循环,将第四大数字移到最右边,共比较一次
            for (int j = 0; j < arr.length - 1 - 3; j++) { // 最右边三个数数已经排好序,不需要比较,所以 减3
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第4次循环:" + Arrays.toString(arr));
        }
    
    }
    
    

    运行结果如下

    image-20210617095025610

    我们发现,长度为5的无序数组通过4次排序将其变成从小到大的有序。 最多进行(arr.length - 1)轮排序

    • 第一次循环,将第一大数字移到最后一位
    • 第二次循环,将第二大数字移到倒数第二位
    • 第三次循环,将第三大数字移到倒数第三位
    • 第四次循环,将第四大数字移到倒数第四位
    • 。。。。。。。。。。

    依据规律写出冒泡排序方法

       public static int[] sort(int[] arr){
            int temp = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
            return arr;
        }
    

    冒泡排序的优化:

    优化1: 通过上面的demo我们发现每一轮排序的时候都这一轮中将最大的数排到右边了,(第一次最右边拍好了,第二次最右边两个排好了,第三次最右边三个排好了。。。)因此在第二轮循环中可以免去重复的比较

     public static int[] sort(int[] arr){
            int temp = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length - 1 - i; j++) { // 减去重复的比较
                    if (arr[j] > arr[j + 1]) {
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
              //每次循环打印下
              System.out.println("第" + (i + 1) + "次循环:" + Arrays.toString(arr));
            }
            return arr;
        }
    
    image-20210617103342069

    **注:**上面的demo中我写的数组是恰巧进行了(arr.length - 1 )轮排序,而下图中长度为5的数组只进行了1轮排序

    image-20210617102811922

    因此还能继续优化,避免不必要的比较

    **优化2:**设置标志位

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

    public static int[] sort(int[] arr) {
            int temp = 0;
            boolean isExchange = false;  // 定义标志变量表示是否在这一轮进行交换过。默认没交换false
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        isExchange = true; // 如果前一个大于后一个,代表交换了
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                if (isExchange == false){ // 如果未交换直接跳出当前轮的循环
                    break;
                }else {
                    isExchange = false;
                }
                System.out.println("第" + (i + 1) + "次循环:" + Arrays.toString(arr));
            }
            return arr;
        }
    

    其实优化二也没啥太大必要,反正每一轮都是要每一个元素进行比较的,了解即可

    总结:冒泡排序还是很简单的,如果我们想简单写出来的话不考虑别的,直接两轮for循环就行了。(注意内层不要越界)

    展开全文
  • **********************冒泡排序下沉法********************* int[] array = {18,25,7,36,13,2,89,63}; System.out.println("冒泡排序下沉法原序列:"); for ( int i : array ) { System.ou...

     

    
    **********************冒泡排序下沉法*********************
    
            int[] array = {18,25,7,36,13,2,89,63};
            System.out.println("冒泡排序下沉法原序列:");
            for ( int i : array ) {
                System.out.print(i+"\t");
            }
            for ( int i = 0; i < array.length; i++ ) {
                for ( int j = 0; j < array.length-i-1; j++ ) {
                    if ( array[j] > array[j+1] ) {
                        int t = array[j];
                        array[j] = array[j+1];
                        array[j+1] = t;
                    }
                }
            }
            System.out.println("\n从小到大排序后序列:");
            for ( int i : array ) {
                System.out.print(i+"\t");
            }
    
    **********************冒泡排序上浮法*********************
    
            int[] array = {18,25,7,36,13,2,89,63};
            System.out.println("冒泡排序上浮法原序列:");
            for ( int i : array ) {
                System.out.print(i+"\t");
            }
            for ( int i = 0; i < array.length - 1; i++ ) {
                for ( int j = array.length-2; j >= i; j-- ) {
                    if ( array[j] > array[j+1] ) {
                        int t = array[j];
                        array[j] = array[j+1];
                        array[j+1] = t;
                    }
                }
            }
            System.out.println("\n从小到大排序后序列:");
            for ( int i : array ) {
                System.out.print(i+"\t");
            }
    
    *************************选择排序*********************
    
            int[] array = {18,25,7,36,13,2,89,63};
            System.out.println("选择排序原序列:");
            for ( int i : array ) {
                System.out.print(i+"\t");
            }
            for ( int i = 0; i < array.length - 1; i++ ) {
                int k = i;
                for ( int j = i+1; j < array.length; j++ ) {
                    if ( array[k] > array[j] ) {
                        k = j;
                    }
                }
                if ( k != i ) {
                    int t = array[i];
                    array[i] = array[k];
                    array[k] = t;
                }
            }
            System.out.println("\n从小到大排序后序列:");
            for ( int i : array ) {
                System.out.print(i+"\t");
            }

     

    展开全文
  • 一, 向上冒泡排序 最轻的冒到最上边,最沉的冒dao

    一, 向上冒泡排序

    元素从底向上冒,最轻的冒到最上边,最沉的冒到最下边。

    时间复杂度为O(N^2)

    证明如下

    first element compare N-1

    second element compare N-2

    ...

    last element compare 0

    total compares: [(0+1+...+N-1)*N]/2=(N^2)/2


    实施代码

    	public static void bubbleSortUp(int[] array) {
    		for (int i = 0; i < array.length; i++) {
    			for (int j = array.length - 1; j > i; j--) {
    				if (more(array[j - 1], array[j]))
    					exchange(array, j, j - 1);
    			}
    		}
    	}


    compare and exchange

    	// compare
    	public static boolean more(int v, int w) {
    		return v > w;
    	}
    
    	// exchange
    	public static void exchange(int[] array, int i, int j) {
    		int temp = array[i];
    		array[i] = array[j];
    		array[j] = temp;
    	}


    二,向下冒泡排序

    元素从上往上沉,最沉的沉到最下边,最轻的沉到最上边。

    时间复杂度为O(N^2)

    向下排序和向上排序差不多,就是初始指针指向不太一样,代码如下

    	public static void bubbleSortBottom(int[] array) {
    		for (int i = 0; i < array.length; i++) {
    			for (int j = 0; j < (array.length - 1) - i; j++) {
    				if (more(array[j], array[j + 1])) 
    					exchange(array, j, j + 1);
    			}
    		}
    	}



    展开全文
  • 算法基础-冒泡排序

    2014-02-27 02:46:57
    冒泡排序向上冒泡和向下冒泡,这里以向下冒泡为例说明。 向下冒泡的思路,基本上就是比较相邻的两个数据,如果前一个数据比后一个数据大,那么就交换数据。依次这样进行。下面我们使用了2中方法实现。一种 是直接...

    一、冒泡排序

    冒泡排序有向上冒泡和向下冒泡,这里以向下冒泡为例说明。

    向下冒泡的思路:比较相邻的两个数据,如果前一个数据比后一个数据大,那么就交换数据。依次这样进行。下面我们使用了两种方法实现。

    一种是直接按冒泡的思路直接写的,而后一种设置了一个标记,其实相当于对冒泡排序进行了小小的优化。

    二、代码实现

    // 冒泡排序.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    void BubbleSort1(int a[],int n);
    void BubbleSort2(int a[],int n);
    void Swap(int *x1, int *x2);
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int Array[4]={1,-1,3,4};
    	for ( int i=0; i< 4; i++)
    		cout << Array[i] << " ";
    	cout << endl;
    	//BubbleSort1(Array,4);
    	BubbleSort2(Array,4);
    
    	for ( int i=0; i< 4; i++)
    		cout << Array[i] << " ";
    	cout << endl;
    
    	return 0;
    }
    
    //冒泡排序1
    void BubbleSort1(int a[],int n)
    {
    	int i, j;
    	for (i = 0; i < n-1; i++ )
    		for ( j = 1; j <n - i; j++)
    			if(a[j - 1] > a[j])
    				Swap((a+j-1),(a+j));
    }
    
    //冒泡排序2
    void BubbleSort2(int a[],int n)
    {
    	int j,k;
    	bool flag;
    
    	k = n;
    	flag = true; //设置了一个标记
    	while (flag)
    	{
    		flag = false;
    		for ( j = 1; j < k; j++)
    			if( a[j-1] > a[j])
    			{
    				Swap((a+j-1),(a+j));
    				flag = true;
    			}
    	}
    }
    
    void Swap(int *x1, int *x2)
    {
    	int tmp;
    	tmp = *x1;
    	*x1 = *x2;
    	*x2 = tmp;	
    }

    结果



    展开全文
  • 排序算法系列:冒泡排序与双向冒泡排序

    万次阅读 多人点赞 2016-01-29 15:25:32
    **排序算法**应该算是一个比较热门的话题,在各个技术博客平台上也都有一些博文进行了一定程度的讲解。...本文就先从最简单的冒泡排序开始说起,别说你已经彻底了解了冒泡排序算法(虽然一开始我也是这样以为的)。
  • 最近在复习经典排序算法,自己用python也实现了一下,... 冒泡排序冒泡排序是实现起来最简单的排序算法,时间复杂度是O(n^2),它的代码核心是两层嵌套的for循环,循环里一个判断数组相邻两个元素大小,如果不满足...
  • 冒泡排序的动态图 可以自行搜索 网上都有便于理解 #include<stdio.h> #define MaxSize 20 //顺序表最大长度 typedef int KeyType; //typedef定义关键字类型为(int) typedef int InfoType; typedef struct...
  • C双向冒泡排序算法

    2021-05-22 10:27:48
    同事考研遇到的数据结构题:题目:冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉),请给出上浮下沉过程交替的冒泡排序算法。为了减少重复代码,设置了变量step在1、-1间变化,...
  • 冒泡排序是一种比较简单的排序算法,其基本思想是:通过对待排序序列从前后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移后部,可以形象的理解为像水底的气泡...
  • 这节我们值讲解同属于交换排序的冒泡排序和快速排序 冒泡排序 冒泡顾名思义就是水中的水泡一样再向上浮出水面的时候总是越来越大的,我们冒泡也是同样的原理,再每次都找到最大的放在我们的数组末尾,这样再执行...
  • 应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。2、基本思想两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。将被排序的记录数组R[1..n]垂直排列,每个记录...
  • 冒泡排序(Bubble Sorting)的基本思想是:通过对待 排序序列从前后(从下标较小的元素开始),依次比较 相邻元素的值,若发现逆序则交换,使值较大 的元素逐渐从前移后部,就象水底下的气泡一样逐渐 向上冒 ...
  • Java之冒泡排序

    2021-05-27 21:15:39
    排序的介绍 排序是将多个数据,依指定的...冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移后部
  • python篇 冒泡排序

    2021-11-07 13:10:46
    所谓冒泡排序,就像水淘米,水倒进锅中,饱满的大米下沉,轻质的谷壳上浮,如果水灌得太急甚至能看到空气形成的气泡从锅底急速上升,然后在水面消失。我们要做的就是如此上浮或下沉分开元素。 ## 2.举例说明: **值...
  • 冒泡排序代码实现与详解

    千次阅读 2021-02-08 13:37:52
    冒泡排序(Bubble Sorting)的基本思想是:通过对待排序序列从前后,依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前后移动,就像水底的气泡一样逐渐向上冒。 在讲解代码之前首先要明确 1....
  • 冒泡排序与快速排序比较

    千次阅读 2019-12-31 18:08:22
    冒泡排序是一种简单的排序方法,它的基本思想是:通过相邻两个元素之间的比较交换,使较大的元素逐渐从前面移后面(升序),就像水底的气泡一样逐渐向上冒泡,所以被称为“冒泡”排序。 1.2逻辑图表示 1.3...
  • 已结贴√问题点数:2回复次数:2 浅议冒泡排序及其优化方法浅议冒泡排序及其优化方法冒泡排序法是一种简单的排序方法,不仅代码简短,排序思路也简单易懂,是一种容易被初学者接受的基本排序方法。但正因为冒泡排序...
  • 通过相邻两个元素之间的比较交换,使较大的元素逐渐从前面移后面(即升序),就像水底的气泡一样逐渐向上冒泡,所以被称为“冒泡”排序。 var arr = [3, 4, 5, 1, 7, 2, 8, 9, 6, 0]; function arrayRank(arr)...
  • 冒泡排序:  冒泡排序就是每次找出最大(最小)元素,放在集合最前或最后,这是最简单的排序算法 def bubble_sort(collection): #升序排列 length=len(collection) for s in range(length-1):#可以假设...
  • 排序算法之 冒泡排序和快速排序

    千次阅读 2018-09-11 10:27:10
    冒泡排序是一种简单的排序方法,它的基本思想是:通过相邻两个元素之间的比较交换,使较大的元素逐渐从前面移后面(升序),就像水底的气泡一样逐渐向上冒泡,所以被称为“冒泡”排序。冒泡排序的最坏时间...
  • /*冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉)*/ /*请给出上浮下沉过程交替的冒泡排序算法*/ #include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 ...
  • 什么是冒泡排序呢?...而冒泡排序之所以叫冒泡排序,正是因为这种排序算法的每一个元素都可以小气泡一样,根据自身大小,一点一点向着数组的一侧移动。具体如何移动呢?我们来看一下例子: 有8个...
  • 二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式,要在同一台计算机的相同状态运行,才能比较那个算法速度更快。 事前估算的方法 通过分析某个算法的时间复杂度来判断哪个算法更优. 时
  • 一:冒泡排序的基本介绍   冒泡排序(Bubble Sorting)的基本思想是:通过对待 排序序列从前后(从下标较小的元素开始),依次比较 相邻元素的值,若发现逆序则交换,使值较大 的元素逐渐从前移后部,就象水底下...
  • 冒泡排序

    万次阅读 2020-06-27 16:57:00
    冒泡排序(Bubble Sort)的基本思想是:通过对待排序数组从头到尾遍历(从索引较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从数组头部移尾部,就象水底下的气泡一样逐渐向上冒。...
  • java 排序算法 冒泡排序 选择排序 直接插入排序 希尔排序
  • 排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按...① 冒泡排序 ② 快速排序 选择排序: ③ 直接选择排序 ④ 堆排序 插入排序: ⑤ 直接插入排序 ⑥ 希尔排序 合...
  • 冒泡排序法* 思想:通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的排序码,* ,若发现逆序这交换,使得排序码较小的元素逐渐从后部移向前部(从下标较大的单元移下标)* 较小的单元,,就像水...
  • 冒泡排序和快速排序1、冒泡排序1.1 介绍1.2 代码实现1.2.1 基本实现1.2.2 优化2、快速排序2.1 介绍2.2 代码实现 1、冒泡排序 1.1 介绍 1.2 代码实现 1.2.1 基本实现 1.2.2 优化 2、快速排序 2.1 介绍 2.2 代码实现 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,534
精华内容 4,213
关键字:

向上冒泡排序和向下冒泡排序

友情链接: Lab6_FileSystem.zip