[数据结构与算法]常用的排序算法（选择，冒泡，插入）

前言

概述

最近在重新学习数据结构与算法，计划最近一年的业余时间都不干别的了，专门学算法。

今天给大家分享的是关于常见的几种排序算法：选择排序，冒泡排序和插入排序。这里的来代码源自于网传的左神算法新手班的内容，不过后面我整理了一份更加简洁的代码。

算法简介

关于这几种排序算法，我之前是写过文章分析过的，不过这种经典的算法，就算学习100遍，练习10000遍也不过分，这里我重新梳理一下：

• 选择排序：这种排序算法的思路很简单，就是从左往右遍历，每次找最小的数放到前面。这样保证前面的数始终小于或等于后面的数，到最后整个数组都是有序的。
• 冒泡排序：这种排序算法的思路也很简单，也是从左往右遍历，每次比较相邻两个数的大小，将大的往右边放。这样就保证到最后，右边的数始终比左边的数大，整个数组都是有序的。
• 插入排序：这种排序算法的思路是从左往右遍历，每次保证左边的小数组是有序的。即就是每次从右边取一个数过来，然后和左边的小数组比较，插入到一个合适的位置。这样到了最后，左边的小数组完全取代整个数组，实现数组的有序。

关于这几个算法，有几个核心需要注意：

• 选择排序：从右边选择最小的数往左边放。
• 冒泡排序：每次将最大的数冒泡到右边。
• 插入排序：把左边看成小数组，每次去右边找一个数，插入到左边小数组的合适位置。

伪代码

选择排序：

for (i=0; i<数组长度-1; i++){
	最小索引=i
	for(j=i+1;j<数组长度;j++){
		如果 arr[最小索引] > arr[j]{
			最小索引=j
		}
	}
	交换最小索引位置和i位置的元素的值
}

注意：外层循环只需要遍历到小于数组长度-1，因为内存循环是从i+1开始的，否则会索引越界，这里需要特别注意。

冒泡排序：

for (i=0; i<数组长度; i++){
	for (j=0; j<数组长度-1-i; j++){
		如果 arr[j] > arr[j+1]{
			交换 j 和 j+1 索引位置的元素
		}
	}
}

注意：外层循环是小于数组长度，但是这里小于数组长度-1也是可以的。因为最后一次比较的时候，只剩下一个最小的数了，那次比较是可以被忽略掉的。

插入排序：

for (i=1; i<数组长度; i++){
	for (j=i-1; j>=0 && arr[j]>arr[j+1]; j--){
		交换j 和 j+1 索引位置的元素
	}
}

注意：这里外层循环是从1开始的，因为内层循环要从i-1开始。内层循环j>=0表示左边有值，arr[j]>arr[j+1]表示左边的数大于右边的数。

核心代码实现

交换数组中两个元素的值

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

选择排序

public static void selectSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 选择排序，从左往右，每次选择最小的放左边，这样保证整个数组最后是从小到大的
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        // 从当前位置的后一个位置找到最后，找最小的那个数的索引
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr, i, minIndex);
    }
}

冒泡排序

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 冒泡排序，从左往右，如果发现大的值，就往右移动（交换），这样保证后面的数都比前面的数大，所以是有序的
    for (int i = 0; i < arr.length; i++) {
        // 发现后一个数比前一个数大，就交换
        for (int j = 0; j < arr.length-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr,j,j+1);
            }
        }
    }
}

插入排序

public static void insertSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 插入排序，从左往右，每次保证左边的数组是有序的，最后整个数组都是有序的
    // 因为这有点像大牌，习惯性的把小牌放左边，大牌放右边，所以形象的比喻为插入排序
    for (int i = 1; i < arr.length; i++) {
        // 保证左边是有序的，如果左边有值且左边的值比右边的大
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            swap(arr, j, j + 1);
        }
    }
}

选择排序

原始代码

package com.zhangdapeng520.z02_select_sort;

import java.util.Arrays;

/**
 * @文件 Z01Hello.java
 * @作者 张大鹏
 * @版本 v0.1.0
 * @描述
 * @创建时间 2022-10-18 07:53:00
 * @更新时间 2022-10-18 07:53:00
 */
public class Z01Hello {
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

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

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random() [0,1)
        // Math.random() * N [0,N)
        // (int)(Math.random() * N) [0, N-1]
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            // [-? , +?]
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            selectionSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        selectionSort(arr);
        printArray(arr);
    }

}

整理后代码

package com.zhangdapeng520.z02_select_sort;

import java.util.Arrays;

/**
 * @文件 Practice01.java
 * @作者 张大鹏
 * @版本 v0.1.0
 * @描述
 * @创建时间 2022-10-18 08:11:00
 * @更新时间 2022-10-18 08:11:00
 */
public class Practice01 {
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 选择排序，从左往右，每次选择最小的放左边，这样保证整个数组最后是从小到大的
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;

            // 从当前位置的后一个位置找到最后，找最小的那个数的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            swap(arr, i, minIndex);
        }
    }

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

    public static int[] getArr(int size){
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i]=(int)(Math.random()*100);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = getArr(10);
        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

冒泡排序

原始代码

package com.zhangdapeng520.z03_bubble_sort;

import java.util.Arrays;

/**
 * @文件 Z01Hello.java
 * @作者 张大鹏
 * @版本 v0.1.0
 * @描述
 * @创建时间 2022-10-18 07:54:00
 * @更新时间 2022-10-18 07:54:00
 */
public class Z01Hello {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int end = arr.length - 1; end > 0; end--) {
            for (int i = 0; i < end; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    // 交换arr的i和j位置上的值
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            bubbleSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        bubbleSort(arr);
        printArray(arr);
    }
}

整理后代码

package com.zhangdapeng520.z03_bubble_sort;

import java.util.Arrays;

/**
 * @文件 Practice01.java
 * @作者 张大鹏
 * @版本 v0.1.0
 * @描述
 * @创建时间 2022-10-18 08:11:00
 * @更新时间 2022-10-18 08:11:00
 */
public class Practice01 {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 冒泡排序，从左往右，如果发现大的值，就往右移动（交换），这样保证后面的数都比前面的数大，所以是有序的
        for (int i = 0; i < arr.length; i++) {
            // 发现后一个数比前一个数大，就交换
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }

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

    public static int[] getArr(int size){
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i]=(int)(Math.random()*100);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = getArr(10);
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

插入排序

原始代码

package com.zhangdapeng520.z04_insert_sort;

import java.util.Arrays;

/**
 * @文件 Z01Hello.java
 * @作者 张大鹏
 * @版本 v0.1.0
 * @描述
 * @创建时间 2022-10-18 07:59:00
 * @更新时间 2022-10-18 07:59:00
 */
public class Z01Hello {
    // 从左到右，每次保证一小段数组是有序的，最终整个数组都是有序的
    // 就像斗地主一样，我们习惯性的将小牌放左边，大牌放右边，形象的比做插入排序
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
            // int j = i - 1; j >= 0 && arr[j] > arr[j + 1]
            // 表示左边有数，并且左边的数比我大，就交换
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

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

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        // Math.random() ->  [0,1) 所有的小数，等概率返回一个
        // Math.random() * N -> [0,N) 所有小数，等概率返回一个
        // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; // 长度随机
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random())
                    - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100; // 随机数组的长度0～100
        int maxValue = 100;// 值：-100～100
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            insertionSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                // 打印arr1
                // 打印arr2
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        insertionSort(arr);
        printArray(arr);
    }
}

整理后代码

package com.zhangdapeng520.z04_insert_sort;

import java.util.Arrays;

/**
 * @文件 Practice01.java
 * @作者 张大鹏
 * @版本 v0.1.0
 * @描述
 * @创建时间 2022-10-18 08:11:00
 * @更新时间 2022-10-18 08:11:00
 */
public class Practice01 {
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 插入排序，从左往右，每次保证左边的数组是有序的，最后整个数组都是有序的
        // 因为这有点像大牌，习惯性的把小牌放左边，大牌放右边，所以形象的比喻为插入排序
        for (int i = 1; i < arr.length; i++) {
            // 保证左边是有序的，如果左边有值且左边的值比右边的大
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }

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

    public static int[] getArr(int size) {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = getArr(10);
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}