冒泡排序、简单选择排序和插入排序

1. 冒泡排序

1.1 算法步骤

（一）比较相邻的元素。如果第一个比第二个大，就交换他们两个

（二）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

（三）针对所有的元素重复以上的步骤，除了最后一个。

（四）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.2 算法分析

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度:T(n) = O(n²)：当输入的数据是反序时，（此种情况下，可以for循环反序输出）
最好时间复杂度:T(n) = O(n)：当输入的数据已经有序时，只需遍历一遍用于确认数据已有序。
空间复杂度:O(1)

1.3 代码实现

public class BubbleSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		// boolean flag = true不放在这里，因为放在这里优化的是初始数组就有序，放在下面则可以表示某次循环有序
        for (int i = 1; i < arr.length; i++) {
            // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
            boolean flag = true;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return arr;
    }
}

此种优化只对有序数组起到作用，而如果是无序数组，这种优化还会增加负担，具体由代码第10行、18行、21行引起。

import java.util.Arrays;

/**
 * @author by 慕容琴羽
 * @Date 2022/4/29 13:56
 */
public class suanfa {
    public Integer[] bubbleSort(Integer[] array) {
        for (int end = array.length-1; end >0 ; end--) {
            // sortIndex在数组完全有序的时候，完全有序时会将1赋值给end，end--后程序为0会退出
            int sortIndex=1;
            for (int begin = 0; begin <end; begin++) {
                if (array[begin]>array[begin+1]){
                    Integer temp=array[begin+1];
                    array[begin+1]=array[begin];
                    array[begin]=temp;
                    sortIndex=begin;//记录每次交换的顺序，如果后面的数组有序，则这是最后一次交换的位置
                }
            }
            end=sortIndex;//将最后一次的交换位置赋值给end，则再扫描的时候不需要再对后面有序数组扫描
        }
        return array;
    }

    public static void main(String[] args) {
        Integer[] array = {1,2,3};
        System.out.println(Arrays.toString(new suanfa().bubbleSort(array)));
    }
}

2. 简单选择排序

2.1 算法步骤

（一）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

（二）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

（三）重复第二步，直到所有元素均排序完毕。

1.2 复杂度分析

选择排序是时间复杂度表现最稳定的排序算法之一，无论什么数据进去都是O(n²) 的时间复杂度…..所以用到它的时候，数据规模越小越好。

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)
最好时间复杂度: T(n) = O(n²)
空间复杂度: O(1)

1.3 代码实现

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较,剩最后一个的时候不用再比啦
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    // 记录目前能找到的最小值元素的下标
                    minIndex = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != minIndex) {
                int tmp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = tmp;
            }

        }
        return arr;
    }
}

3. 插入排序

插入排序的原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法步骤

（一）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

（二）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

3.2 算法复杂度

平均时间复杂度: T(n) = O(n²)
**最坏时间复杂度: T(n) = O(n²)**：输入数组按降序排列（完全逆序）
**最好时间复杂度: T(n) = O(n)**：输入数组按升序排列（基本有序）
空间复杂度: O(1)

3.3 代码实现

public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }
        }
        return arr;
    }
}