Java 冒泡排序

一、冒泡排序简要说明：

冒泡排序是八大排序之一，是一种简单的排序。实现过程就是数组元素两两比较，较小的数排到前面。再从第二元开始比较，不停的循环，直到最后一次循环是只比较最后两个数。

Java数组详解08 - 冒泡排序

以上图片引自博客：

二、 基本思想：

  1. 比较相邻的元素。小的放前面，大的放后面。
  2. 两两相邻的数比较过后，最大的数一定是放到最后面。
  3. 重复以上步骤，每次循环比较都能比上一次少一个数并且每次都将前面最大值放最后 。
  4. 一直循环比较，直到最后一对比较完毕。

示例：

package com.zctou.array;

import java.util.Arrays;

public class ArrayDemo08 {
    public static void main(String[] args) {
        //冒泡排序演示
        //1. 比较数组中，相邻的两个元素，第二个数比第一个数大时，交换位置
        //2. 每次循环都会得出一个最大（或最小的数）
        //3. 每一轮比较都比上一轮要少一个元素
        //4. 循环到最后一对数后结束
        int[] nums = {9,23,4,7,8,5,1,20};
        int[] nums1 = Arrays.copyOf(nums,nums.length);
        System.out.println(Arrays.toString(nums1));
        System.out.println(Arrays.toString(nums));
        int[] res1 = bubbleSort(nums);
        int[] res2 = bubbleSort(nums1);

        System.out.println(Arrays.toString(res1));
        System.out.println(Arrays.toString(res2));
    }

    //冒泡排序方法
    public static int[] bubbleSort(int[] nums) {
        int temp = 0 ;
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = nums.length-1; j >i ; j--) { //从后往前比较，每次要比上一轮少一个数
                if(nums[j]<nums[j-1]) { //最小值往前移
                    //换位置
                    temp = nums[j];
                    nums[j] = nums[j-1];
                    nums[j-1] = temp ;
                }
            }
        }
        return nums;
    }

    public static int[] bubbleSort2(int[] nums) {
        int temp = 0;
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = 0; j < nums.length-1-i; j++) { //从前往后比较，每次要比上一轮少一个数
                if(nums[j]>nums[j+1]) { //最小值往前移
                    //换位置
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp ;
                }
            }
        }
        return nums;
    }
}

三、写在最后：

冒泡的代码相对简单，只要两层循环，外层是冒泡的轮数，里层是两两比较的次数。

这个冒泡的嵌循环算法，时间复杂度为O(n2)。

文章目录