首页 > 编程语言 > 详细

【排序算法】1.冒泡排序--BubbleSort

时间:2021-07-14 11:57:53      阅读:26      评论:0      收藏:0      [点我收藏+]

【排序算法】1.冒泡排序--BubbleSort

算法可视化

技术分享图片

  1. 每次比较相邻值,将较小值移位。
  2. 每次将数组中最大值/最小值选出,放在数组的最末端/最前端。
  3. 每次排序排除已排序元素。

代码实现(以Java为例)

public class BubbleSort {
    //随机数个数
    static int size=10;

    public static void main(String[] args) {
        //定义随机数数组
        int[] arr = new int[size];
        //赋值
        for (int m=0;m<size;m++){
            arr[m]= (int) (Math.random()*100);
        }
        //排序前
        System.out.print("排序前数组:");
        for (int a:arr
             ) {
            System.out.print(a+" ");
        }
        System.out.println();
     //排序过程
for (int i = 0; i < arr.length - 1; i++) { for (int j=0;j<arr.length-1-i;j++){ if (arr[j]>arr[j+1]){
            //交换元素位置
int c=arr[j]; arr[j]=arr[j+1]; arr[j+1]=c; } } }
     //排序后数组
for (int a:arr ) { System.out.print(a+" "); } } }

算法分析:

  1. 由此可见:N个数字要排序完成,总共进行N-1趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数
  2. 冒泡排序的优点:每进行一趟排序,就会少比较一次,因为每进行一趟排序都会找出一个较大值。如上例:第一趟比较之后,排在最后的一个数一定是最大的一个数,第二趟排序的时候,只需要比较除了最后一个数以外的其他的数,同样也能找出一个最大的数排在参与第二趟比较的数后面,第三趟比较的时候,只需要比较除了最后两个数以外的其他的数,以此类推……也就是说,没进行一趟比较,每一趟少比较一次,一定程度上减少了算法的量。
  3. 时间复杂度
    • 如果我们的数据正序,只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值,即:Cmin=n-1;Mmin=0;所以,冒泡排序最好的时间复杂度为O(n)。
    • 如果很不幸我们的数据是反序的,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

技术分享图片

    • 综上所述:冒泡排序总的平均时间复杂度为:O(n2) ,时间复杂度和数据状况无关。

 

【排序算法】1.冒泡排序--BubbleSort

原文:https://www.cnblogs.com/xintu524/p/15009411.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!