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

    2020-07-24 00:16:17
    每次冒泡操作都会相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。 2.原理 1.比较相邻的元素。...

    1. 概念

    冒泡排序是一种简单的排序算法。只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。

    2.原理

    1.比较相邻的元素。如果第一个比第二个大,就交换它们两个;
    2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
    3.针对所有的元素重复以上的步骤,除了最后一个;
    4. 重复步骤1~3,直到排序完成(需要注意的每过一次外部循环,内部循环的变量需要减1,因为最大数已经到最右边了)。

    3.算法分析

    最佳情况:T(n) = O(n)   最差情况:T(n) = O(n2)   平均情况:T(n) = O(n2)

    4.插图参考链接

    1. https://visualgo.net/en/sorting?slide=1   
    2. http://www.donghuasuanfa.com/portal

    5.测试用例

     比如要排序这个数组3 2 5 4 8,带着问题去写代码,一定要手写出来!,一定要手写出来!,光看没用

    public class MaoPaoSort {
    
    
        /**
         * 普通玩法就是挨个对比,需要注意点是每次对比一次后面就不用再次对比了,需要n-1
         * @param array
         * @param n
         */
        private static void bubbleSort1(int[] array,int n){
            if(n<=1){
                return;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<n-i-1;j++){
                    if(array[j+1]<array[j]){
                        int temp= array[j+1];
                        array[j+1]=array[j];
                        array[j]=temp;
                    }
                }
            }
        }
    
    
        /**
         * 普通玩法增强版
         * @param array
         * @param n
         */
        private static void bubbleSort2(int[] array,int n){
            if(n<=1){
                return;
            }
    
            for(int i=0;i<n;i++){
                //循环一次没有可替换,可提前退出冒泡的标志位
                boolean flag=false;
                for(int j=0;j<n-i-1;j++){
                    if(array[j+1]<array[j]){
                        int temp= array[j+1];
                        array[j+1]=array[j];
                        array[j]=temp;
                        flag=true;
                    }
                }
                if(!flag){
                    //没有数据交换,提前退出
                    break;
                }
            }
        }
    
    
        /**
         * 增强版玩法
         * @param array
         */
        public static void bubbleSort3(int array[]){
            for(int i=0;i<array.length-1;i++){
                //有序标记,每一轮的初始值都是true
                boolean isSorted=true;
                //无序数列的边界,每次比较只需要比到这里为止
                int sortBorder=array.length-1;
                for(int j=0;j<sortBorder;j++){
                    int tmp=0;
                    if(array[j]>array[j+1]){
                        tmp=array[j];
                        array[j]=array[j+1];
                        array[j+1]=tmp;
                        //因为有元素互换,所以不是有序的,标记为false
                        isSorted=false;
                        //把无须数列的边界更新为最后一次交换元素的位置
                        sortBorder=j;
                    }
    
                }
                if(isSorted){
                    break;
                }
            }
    
        }
    
    
    
        public static void main(String[] args) {
            int[] array=new int[]{3,2,5,4,8};
            bubbleSort3(array);
            System.out.println(Arrays.toString(array));
        }
    }

     

    展开全文
  • 一次冒泡会让至少个元素交换到它该在的位置,重复n次就完成了排序; 优化:若某次冒泡不存在数据互换,就完成了n个数据的排序互换; 性能分析 最小时间复杂度:当数据完全有序时,只需进行一次冒泡操作,时间复杂度...

    排序原理

    1. 冒泡排序只会操作相邻的两个数;
    2. 对相邻的两个数据进行比较,看是否满足大小关系,如果不满足就互换位置;
    3. 一次冒泡会让至少一个元素交换到它该在的位置,重复n次就完成了排序;
    4. 优化:若某次冒泡不存在数据互换,就完成了n个数据的排序互换;

     

    性能分析

    1. 最小时间复杂度:当数据完全有序时,只需进行一次冒泡操作,时间复杂度为O(n);
    2. 最大时间复杂度:当数据完全逆序时,需要n次冒泡操作,时间复杂度为O(n^2);
    3. 平均时间复杂度:取个中间值近似(不严谨但很实用)为n*(n-1)/4,复杂度还是O(n^2);
    4. 空间复杂度:每次互换只需要一个临时变量,故而空间复杂度为O(1),为原地排序算法;
    5. 算法稳定性:如果两个值相等,就不会交换位置,故而是稳定排序算法;

    《数据结构与算法之美》 -- 王争

    展开全文
  • 每次冒泡操作都会相邻的俩个元素进行比较,看是否满足大小关系。如果不满足就让这俩个元素进行交换。 一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。 eg: 可以看出:经过...

    冒泡排序

    冒泡操作只会操作相邻的俩个数据。

    每次冒泡操作都会对相邻的俩个元素进行比较,看是否满足大小关系。如果不满足就让这俩个元素进行交换。

    一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。

    eg:

    在这里插入图片描述

    可以看出:经过一次冒泡操作后,6这个元素已经在最终位置上了。要想完成所有数据的排序,只需要进行6次这样的冒泡操作。

    eg:实现原始冒泡

    public static void bubbleSort(int[] array) {
        if (array.length <= 1) {
            return;
        }else {
            int n = array.length;
            for (int i = 0;i < n;i++) {
                for (int j = 0;j < n - i - 1;j++) {
                    if (array[j] > array[j+1]) {
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                }
            }
        }
    }
    

    以上的冒泡程序是可以进行优化的。
    eg:
    在这里插入图片描述

    这里的6个元素,只需要进行4次冒泡排序操作就可以了。

    eg:优化冒泡排序:

    public static void bubbleSort(int[] array) {  
        if (array.length <= 1) {      
            return;  
        }else {    
            int n = array.length;    
            for (int i = 0;i < n;i++) {   
                boolean flag = false;      
                for (int j = 0;j < n - i - 1;j++) {    
                    if (array[j] > array[j+1]) {      
                        flag = true;                  
                        int temp = array[j];         
                        array[j] = array[j+1];       
                        array[j+1] = temp;             
                    }        
                }       
                //此时没有数据交换,停止循环           
                if (!flag) {          
                    break;         
                }     
            }   
        } 
    }
    

    冒泡排序算法总结:

    • 冒泡排序是一个原地排序算法:冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为:O(1),即是一个原地排序算法。
    • 冒泡排序是稳定的排序算法:冒泡排序中,只有交换才可以改变俩个元素的先后顺序,当相邻的俩个元素的大小相等时,即不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
    • 冒泡排序时间复杂度分析
      最好情况下:要排序的数据已经是有序的,只需要进行一次冒泡操作,所以最好情况的时间复杂度是O(n)
      最坏情况下:要排序的数据刚好是倒序的,此时需要进行n次冒泡排序,所以最坏情况的时间复杂度是:O(n^2)
    展开全文
  • 每次冒泡操作都会相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。 第一,冒泡排序是...

    1.冒泡排序

    冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。

     

    第一,冒泡排序是原地排序算法吗?

    原地排序:就是指在排序过程中不申请多余的存储空间,只利用原来存储待排数据的存储空间进行比较和交换的数据排序。

    冒泡的过程只涉及相邻数据的交换操作,只需要常量级的临时空间,所以它的空间复杂度为 O(1),是一个原地排序算法。

    第二,冒泡排序是稳定的排序算法吗?

    稳定性:如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变

    在冒泡排序中,只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等的时候,我们不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。

    第三,冒泡排序的时间复杂度是多少?

    时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势,所以它表示的时候会忽略系数、常数、低阶

    最好情况下,要排序的数据已经是有序的了,我们只需要进行一次冒泡操作,就可以结束了,所以最好情况时间复杂度是 O(n)。而最坏的情况是,要排序的数据刚好是倒序排列的,我们需要进行 n 次冒泡操作,所以最坏情况时间复杂度为 O(n2)。

     

    代码实现:

        // 冒泡排序,a表示数组,n表示数组大小
        public static void bubbleSort(int[] a, int n) {
            if (n <= 1) return;
    ​
            for (int i = 0; i < n; ++i) {
                // 提前退出冒泡循环的标志位
                boolean flag = false;
                for (int j = 0; j < n - i - 1; ++j) {
                    if (a[j] > a[j + 1]) { // 交换
                        int tmp = a[j];
                        a[j] = a[j + 1];
                        a[j + 1] = tmp;
                        flag = true;  // 表示有数据交换
                    }
                }
                if (!flag) break;  // 没有数据交换,提前退出
            }
        }

    2.插入排序

    插入排序包含两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时,需要拿 a 与已排序区间的元素依次比较大小,找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 a 插入。

    对于不同的查找插入点方法(从头到尾、从尾到头),元素的比较次数是有区别的。但对于一个给定的初始序列,移动操作的次数总是固定的,就等于逆序度。

     

     

    第一,插入排序是原地排序算法吗?

    从实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法。

    第二,插入排序是稳定的排序算法吗?

    在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法。

    第三,插入排序的时间复杂度是多少?

    如果要排序的数据已经是有序的,我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置,每次只需要比较一个数据就能确定插入的位置。所以这种情况下,最好是时间复杂度为 O(n)。注意,这里是从尾到头遍历已经有序的数据。

    如果数组是倒序的,每次插入都相当于在数组的第一个位置插入新的数据,所以需要移动大量的数据,所以最坏情况时间复杂度为 O(n2)。

    还记得我们在数组中插入一个数据的平均时间复杂度是多少吗?没错,是 O(n)。所以,对于插入排序来说,每次插入操作都相当于在数组中插入一个数据,循环执行 n 次插入操作,所以平均时间复杂度为 O(n2)。

    代码实现:

        public static void insertSort(int[] a) {
            for (int i = 1; i < a.length; i++) {
                int value = a[i];
                int j = i - 1;
                for (; j >= 0; j--) {
                    if (a[j] > value) {
                        a[j + 1] = a[j];
                    } else {
                        break;
                    }
                }
                a[j + 1] = value;
            }
        }

    3.选择排序

    选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾。

     

    第一,选择排序是原地排序算法吗?

    选择排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法。

    第二,选择排序是稳定的排序算法吗?

    选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值,并和前面的元素交换位置,这样破坏了稳定性。

    我们可以从上面的动图中看到,第一次排序时,arr[0]=5,会交换到1的位置也就是arr[5]。之后的排序中,arr[2]的5最终会出现在arr[0]的前面。

    第三,选择排序的时间复杂度是多少?

    选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。

     

    代码实现:

        public static void selectSort(int[] arr) {
            for (int i = 0; i < arr.length - 1; i++) {
                int min = arr[i];
                int index = i;
                for (int j = i + 1; j < arr.length; j++) {
                    if (min > arr[j]) {
                        min = arr[j];
                        index = j;
                    }
                }
                if (index != i) {
                    int tmp = arr[i];
                    arr[i] = arr[index];
                    arr[index] = tmp;
                }
            }
        }

     

    展开全文
  • 排序算法

    2021-02-19 14:46:44
    每次冒泡操作都会相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。 一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。 冒泡排序的时间复杂度...
  • 排序算法学习笔记一

    2021-03-13 21:05:50
    每次冒泡操作都会相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。 /** * 一次冒泡会让...
  • 每次冒泡操作都会相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换,就像气泡上升一样。一次冒泡会让至少一个元素移动到应该在的位置,重复n次,就完成了n个数据的排序工作。 冒泡排序...
  • 比较常用的排序算法

    2014-07-01 18:14:50
    各种算法同一数据排序需要的关键字比较次数和关键字移动次数,至少使用5组数据进行比较。1)插入排序:每次将一排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据...
  • 但是需要注意的是,在常规归并排序的时候,如果前一个元素大于后一个元素,直接进行交换即可,只进行了一次操作,但是对于这道题来讲,对于每一次的归并段,我们选择从后向前遍历,前面的归并段的某一个数值left[i]...
  • 数据结构实验

    2012-04-13 09:55:47
    用向量Sa[0……n×(n+1)/2]压缩存储下三角矩阵,编写程序任意输入一下三角矩阵,进行转置,输出转置后的矩阵。 2.用三元组顺序表压缩存储稀疏矩阵,编写程序任意输入一稀疏矩阵,进行转置,输出转置后...
  • 数据结构题

    2012-09-10 14:48:39
    16. 对n个记录的文件进行快速排序,所需要的辅助存储空间大致为 A. O(1) B. O(n) C. O(1og2n) D. O(n2) 17. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K %9作为散列函数...
  • 性质4:具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。 3. 满二叉树与完全二叉树 满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中...
  • 大话数据结构

    2018-12-14 16:02:18
    而只是让每个元素知道它下一个元素的位置在哪里。 3.6.1顺序存储结构不足的解决 办法 55 3.6.2线性表链式存储结构定义 56 3.6.3头指针与头结点的异同 58 3.6.4线性表链式存储结构代码描述 58 3.7单链表的读取 ...
  • 2.1.7 冒泡排序算法的时间复杂度是什么? 2.1.8 写出float x 与“零值”比较的if语句 2.1.9 Internet采用哪种网络协议?该协议的主要层次结构? 2.2.0 Internet物理地址和IP地址转换采用什么协议? 2.2.1 IP地址...
  • (44) 长度为N的线性表进行顺序查找,在最坏情况下所需要的比较次数为(B) 注:要牢记 A. N+1 B. N C. (N+1)/2 D. N/2 (45) 信息隐蔽的概念与下述哪一种概念直接相关(B) 注:P74 A.软件结构定义 B. 模块独立性 C. ...
  • Collections是针对集合类的一帮助类,他提供一系列静态方法实现各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
  • f是一个数组,f有10个元素,元素都是函数的指针,指向的函数类型是没有参数且返回double的函数. (4)int *((*b)[10]); 就跟int *(*b)[10]是一样的,b是一维数组的指针. (5)Long (*fun)(int); 函数指针. (6)int (*(*F)...
  • java 面试题 总结

    2009-09-16 08:45:34
    Collections是针对集合类的一帮助类,他提供一系列静态方法实现各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...
  • (12) 在最坏情况下,冒泡排序的时间复杂度为______。 答:n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2) (13) 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一______。 答:实体 (14) 软件的...
  • C++程序员面试宝典

    热门讨论 2013-04-01 13:36:19
    本书通过380余面试题,企业招聘C/C++程序员需要掌握的知识进行了系统、全面的总结,以帮助读者进行充分的面试准备,在激烈的竞争中成功应聘。本书内容大多取材于各大IT公司的面试题,详细分析了应聘C/C++程序员...

空空如也

空空如也

1
收藏数 20
精华内容 8
关键字:

对n个元素进行冒泡排序至少需要