基础排序（冒泡、选择、插入）

前言

基本每个人入门数据结构和算法都是先经历过排序，今天就来讲解一下最基础的三个入门排序算法。分别是冒泡排序、选择排序和插入排序。

冒泡排序

思路：两两交换，小的往左边，大的往右边。

就是每趟过程把最大的数往右边靠，然后从剩下的数继续刚才的过程。

代码（冒泡排序）

package sort;

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/2/27  14:02
 */
public class BubbleSort {
    //冒泡排序，两两比较，小的往左边，大的往右边
    //时间复杂度O(n^2)  稳定排序  空间复杂度O(1)
    private static void sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //避免已经排好序了还要继续循环下次
            boolean isSorded = true;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorded = false;
                }
            }
            if (isSorded) {
                break;
            }
        }
    }

    //交换两数
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 2, 8, 1, 3, 4, 9, 7, 6};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

结果（冒泡排序）

选择排序

思路：每一次从待排序的数据元素种选出最小的元素，存放在数组的起始位置，知道全部排序完成

每次都选出最小的，然后跟待排序的第一个数交换位置，直到全部排序完成。

代码（选择排序）

package sort;

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/2/27  14:18
 */
public class SelectionSort {
    //选择排序
    //思路：从数组第一个数开始跟后面的数比较，最小和第一个交换，循环进行
    //时间复杂度：O(n^2)  空间复杂度O(1)  不稳定排序
    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                minIndex = array[minIndex] > array[j] ? j : minIndex;
            }
            swap(array, i, minIndex);
        }
    }

    //交换两数
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 5, 6, 1, 4, 9, 7, 8, 3};
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }
}

结果（选择排序）

插入排序

思路：跟打扑克牌一样。维持一个有序区，然后后面进来的数跟有序区比较，然后插入

代码（插入排序）

package sort;

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/2/27  14:32
 */
public class ChaRuSort {
    //插入排序，跟打扑克牌一样
    //时间复杂度O(n^2) 空间复杂度O(1)  稳定排序
    public static void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0 && array[j] > array[j + 1]; j--) {
                swap(array, 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 void main(String[] args) {
        int[] array = new int[]{2, 5, 6, 1, 4, 9, 7, 8, 3};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}