十大排序算法——冒泡排序

April 发布于2021-11-17 09:33 / 3091人阅读

摘要：即数组为的逆序元素的比较次数为元素的交换次数为总执行次数为根据大推导法则，保留最高阶项，即冒泡排序的时间复杂度为

冒泡排序原理

冒泡排序API设计

冒泡排序的代码实现

冒泡排序的时间复杂度分析

冒泡排序原理

①比较相邻的元素，如果前一个元素比后一个元素大，则交换这两个元素的位置

②对每一对相邻的元素循环上面的步骤，最终最后面的元素就是最大值

冒泡排序API设计

类名

Bubble

构造方法

Bubble:创建Bubble对象

成员方法

1.public static void sort(Comparable[] a):对数组内元素进行排序

2.private static void greater(Comparable v,Comparable w)；判断v是否大于w

3.private static void exchange(Comparable[] a,int x,int y):交换a数组中，索引x和索引y处的值

冒泡排序的代码实现

public class Bubble {    //对数组a进行排序    public static void sort(Comparable[] a){        for(int i=a.length-1;i>0;i--){            for(int j=0;j0;    }    //数组元素x和y交换位置    private static void exchange(Comparable[] a,int x,int y){        Comparable t=a[x];        a[x]=a[y];        a[y]=t;    }}//测试代码 class Test{    public static void main(String[] args) {        Integer[] a={4,5,6,3,2,1};        Bubble.sort(a);        System.out.println(Arrays.toString(a));    }}

测试结果：

冒泡排序的时间复杂度分析

冒泡排序虽然采用了双层for循环遍历，但是真正完成排序的代码在内循环中，所以主要分析内层循环体的执行次数即可

在最坏的情况下。即数组为{6,5,4,3,2,1}的逆序

元素的比较次数为：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

元素的交换次数为：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

总执行次数为：2*(N^2/2-N/2)=N^2-N;

根据大O推导法则，保留最高阶项，即冒泡排序的时间复杂度为O(N^2)

云服务器 idc机房托管冒泡排序前端冒泡排序冒泡排序代码 js冒泡排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123576.html

十大排序算法总结

摘要：排序算法的稳定性例如排序一个数组，数组中有两个，排序之后是，如果排序之后的两个的前后顺序没有发生变化，那么称这个排序是稳定的，反之则是不稳定的。冒泡排序冒泡排序是很经典的排序算法了，相邻的两个数据依次进行比较并交换位置。 0. 前言排序算法中涉及到了两个概念：原地排序：根据算法对内存的消耗情况，可以将算法分为原地排序和非原地排序，原地排序特指空间复杂度为 O(1) 的排序。排序算...

王晗 2019-08-16 18:30 评论0 收藏0
十大经典排序算法的 JavaScript 实现

摘要：计算机领域的都多少掌握一点算法知识，其中排序算法是数据结构与算法中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。计算机领域的都多少掌握一点算法知识，其中排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内...

philadelphia 2019-08-20 16:23 评论0 收藏0
JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

摘要：笔者写的数据结构与算法之美系列用的语言是，旨在入门数据结构与算法和方便以后复习。这应该是目前较为简单的十大经典排序算法的文章讲解了吧。比如原本在的前面，而，排序之后，在的后面十大经典排序算法冒泡排序思想冒泡排序只会操作相邻的两个数据。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法为王。想学好前端，先练好内功，内功不行，就...

zsy888 2019-08-26 10:27 评论0 收藏0
前端面试必备——十大经典排序算法

摘要：冒泡排序冒泡排序也是一种简单直观的排序算法。但希尔排序是非稳定排序算法。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。冒泡排序冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就...

RebeccaZhong 2019-08-20 18:24 评论0 收藏0
前端面试必备——十大经典排序算法

摘要：冒泡排序冒泡排序也是一种简单直观的排序算法。但希尔排序是非稳定排序算法。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。冒泡排序冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就...

hover_lew 2019-07-30 14:24 评论0 收藏0