文章目录

1. 冒泡排序

1.1 算法思想

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。一次遍历下来最大(小)的数已经跑到最后，因此确定了一个数，最多遍历n次可完成排序。

1.2 算法步骤

  1. 比较相邻的元素。如果第一个比第二个大（小），就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大（小）的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤1~3，直到排序完成。

1.3 复杂度分析

如果待排序列是有序的，则只需要一次遍历就可确定，最好情况下的时间复杂度为O（n）。

最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度
O（n） O(n^2) O(n^2) O（1）

2. 代码实现

2.1 Java版

class Solution {
   
    public int[] sortArray(int[] nums) {
   
        // 冒泡排序
        // 一次确定一个最好的什么
        // 时间on2，空间o1，稳定
        int[] arr = new int[nums.length];
        System.arraycopy(nums,0,arr,0,nums.length);
        bubbleSort(arr);
        return arr;
    }
    private void bubbleSort(int[] arr){
   
        // 向上冒泡
        for(int i = 0; i < arr.length; ++i){
   
            for(int j = arr.length-1; j > i; --j){
   
                if(arr[j] < arr[j-1]){
   
                    swap(arr, j-1, j);
                }
            }
        }

        // 向下冒泡
        // for(int i = 0; i < arr.length; ++i){
   
        // for(int j = 0; j < arr.length-i-1; ++j){
   
        // if(arr[j] > arr[j+1]){
   
        // swap(arr, j+1, j);
        // }
        // }
        // }
    }

    private void swap(int[] arr, int i, int j){
   
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}