几种简单排序（冒泡排序，插入排序，选择排序）算法介绍

作者：Grey

原文地址：

博客园：几种简单排序（冒泡排序，插入排序，选择排序）算法介绍

CSDN：几种简单排序（冒泡排序，插入排序，选择排序）算法介绍

说明

主要介绍了几种简单排序算法：『冒泡排序』，『插入排序』，『选择排序』。

冒泡排序

冒泡排序流程

在 arr[0...N-1] 范围上：

arr[0] 和 arr[1]，谁大谁来到 1 号位置；

arr[1] 和 arr[2]，谁大谁来到 2 号位置；

依此类推……

arr[N-2] 和 arr[N-1]，谁大谁来到第 N-1 号位置上；

在 arr[0...N-2] 范围上，重复上面的过程，但最后一步是 arr[N-3] 和 arr[N-2] ，谁大谁来到第 N-2 号位置上；

在 arr[0...N-3] 范围上，重复上面的过程，但最后一步是 arr[N-4] 和 arr[N-3]，谁大谁来到第 N-3 号位置上；

依此类推……

最后在 arr[0...1] 范围上，重复上面的过程，但最后一步是 arr[0] 和 arr[1]，谁大谁来到第 1 号位置上；

示例图如下

冒泡排序完整代码

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        if (arr == null || arr.length < 2 || i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

插入排序

流程如下

想让 arr[0...0] 上有序，这个范围只有一个数，当然是有序的。

想让 arr[0...1] 上有序，所以从 arr[1] 开始往前看，如果 arr[1] < arr[0]，就交换。否则什么也不做。

依此类推……

想让 arr[0...i] 上有序，所以从 arr[i] 开始往前看，arr[i] 这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

最后一步，

想让 arr[0...N-1] 上有序，arr[N-1] 这个数不停向左移动，一直移动到左边的数字不再比自己大，停止移动。

估算时发现这个算法流程的复杂程度，会因为数据状况的不同而不同。如果数组本身是有序的，那么插入排序的过程不需要移动任何数字，但是时间复杂度是以最坏情况估计，所以插入排序的时间复杂度仍然是 O(N^2)。

示例图

插入排序完整代码

    public static void insertionSort(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) {
        if (arr == null || arr.length < 2 || i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

选择排序

主要流程

arr[0...N-1] 范围上，找到最小值所在的位置，然后把最小值交换到 0 号位置；

arr[1...N-1] 范围上，找到最小值所在的位置，然后把最小值交换到 1 号位置；

arr[2...N-1] 范围上，找到最小值所在的位置，然后把最小值交换到 2 号位置；

依此类推……

arr[N-1...N-1] 范围上，找到最小值位置，然后把最小值交换到 N-1 号位置；

所以选择排序的时间复杂度为 O(N^2)。

示例图

选择排序完整代码

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                min = arr[j] < arr[min] ? j : min;
            }
            swap(arr, i, min);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        if (arr == null || arr.length < 2 || i == j) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

本文所有示例图见：processon:简单排序（冒泡，插入，选择）

更多

算法和数据结构笔记

参考资料

算法和数据结构基础班-左程云