冒泡排序算法详解

基本思想代码示例二、复杂度分析总结

给定一个长度为N的数组arr，在每一趟遍历时，比较两个相邻的元素，若元素顺序不正确，则交换两个元素的位置，继续向下遍历，因此，每一趟都会有一个最大或最小的值，像冒泡一样，被赶到序列起点或终点，执行N-1次遍历后，即可得到一个排好序的序列arr。

import java.util.Arrays;
import java.util.Random;


public class BubbleSort {
    public static void bubbleSort(int[] arr){
        //若数组为空或小于两个值，则默认有序退出
        if (arr == null || arr.length < 2){
            return;
        }
        for(int i = 0;i arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

    
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    
    public static int[] generateRandomArray(int maxSize,int maxValue){
        Random random = new Random();
        int[] arr = new int[(int) random.nextInt(maxSize+1)];
        for(int i = 0;i 
细节
 外循环：对于一个长度为N的数组，每一趟确定一个值，因此还是需要N-1趟
 内循环：
             内循环（从小到大）：每次都是从0开始，终点为N-i-1，   减i是因为每趟都会确定一个值，减1是因为数组从0开始。
             内循环（从大到小）：每次都是从N-1开始，减1是因为数组从0开始，arr[N]会越界。终点为i>0.
 
二、复杂度分析 
时间复杂度：
           第一趟执行N-1次比较
           第二趟执行N-2次比较
           …
           第N-1趟执行1次比较
 等差数列求和，总的比较次数为（N-1）+（N-2）+…+2+1，因此时间复杂度为O(
    
     
      
       
        
         N
        
        
         2
        
       
      
      
       N^{2}
      
     
    N2)
 
空间复杂度：
           只用到了有限个常熟级空间，因此空间复杂度为O(1)
 
总结 
留下笔记，只为方便回忆，如有侵权，还请联系，如有错误，还请纠正。陆续更新，还请关注。