冒泡排序

冒泡排序算法运行起来非常慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。
冒泡排序原理即：从数组下标为0的位置开始，比较下标位置为0和1的数据，如果0号位置的大，则交换位置，如果1号位置大，则什么也不做，然后右移一个位置，比较1号和2号的数据，和刚才的一样，如果1号的大，则交换位置，以此类推直至最后一个位置结束，到此数组中最大的元素就被排到了最后，之后再根据之前的步骤开始排前面的数据，直至全部数据都排序完成。

冒泡排序代码

package com.java.demo;

import java.util.Random;


/*
 * 数组排序冒泡排序：
 */
public class ArrayTest1 {

    public static void main(String[] args) {
        //创建一个数组
        int[] arr = new int[5];
        //创建随机数对象
        Random rd = new Random();
        
        for (int i = 0; i < arr.length; i++) {
            //获取1-10的随机数
            int num = rd.nextInt(10)+1;
            //对数组进行赋值
            arr[i] = num;
        }
        System.out.println("数组排序前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        //对数组进行排序，冒泡排序
        
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                //进行判断，如果前面的大于后面是不是进行互换，这里要用到中间变量
                if (arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        System.out.println();
        System.out.println("数组排序后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

冒泡排序原理图

选择排序

选择排序原理即：在选择排序中，不再只比较两个相邻的数据。因此需要记录下某一个数据的下标，进行选择排序就是把所有的数据扫描一遍，从中挑出（按从小到大排序）最小的一个数据，这个最小的数据和最左端下标为0的数据交换位置。之后再次扫描数据，从下标为1开始，还是挑出最小的然后和1号位置进行交换，这个过程一直持续到所有的数据都排定。而程序中需要有一个标识变量来标识每次挑出最小数据的下标。

选择排序代码

package com.java.demo;

import java.util.Random;

/*
 * 数组排序选择排序：
 */
public class ArrayTest2 {

    public static void main(String[] args) {

        // 定义一个数，动态初始化
        int[] arr = new int[5];
        // 创建生成随机数的对象
        Random rd = new Random();

        // 对数组进行赋值
        for (int i = 0; i < arr.length; i++) {
            // 获取1-100的随机数
            int num = rd.nextInt(100) + 1;
            arr[i] = num;
        }

        // 打印
        System.out.println("数组未排序前：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

        // 对数组进行排序，选择排序
        for (int i = 0; i < arr.length; i++) {

            for (int j = i + 1; j < arr.length; j++) {
                // 判断
                if (arr[i] > arr[j]) {
                    // 进行互换
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println();

        // 打印
        System.out.println("数组排序后：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }
}

选择排序原理图

冒泡排序和选择排序效率

一般来说选择排序效率比较高，因为只要交换一次，但是冒泡也可以只记录坐标然后做一次性变换，只是牺牲空间复杂度。但是冒泡有个很大的优点就是它可以检测整个数组是否已经有序，当某次遍历没有发生任何交换的时候你就可以提前终止了。也算是个小优化吧。

Java基础(冒泡排序与选择排序)