Java 9种排序算法详解和示例汇总

冒泡排序、选择排序、直接插入排序、二分法排序、希尔排序、快速排序、堆排序、归并排序、基数排序，共9中排序算法详解和代码示例。

示例中全部采用从小到大排序，编码方式为本人理解的思路，算法思想也是自己理解的口语表达方式，若想查看更准确的算法思想和代码示例可直接搜索各算法的百科

示例源码地址

一、冒泡排序

1、算法思想

1. 两两比较，如果后者比前者大则交换位置
2. 每遍历一圈最大的数就会冒到最后，则确定了本轮比较中的最大值放到最后不动
3. 循环1、2直至遍历完所有

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 冒泡排序：两两比较，大者交换位置，则每一圈比较最大的数就会冒到最后，循环直至遍历完所有
 */
private void bubbleSort() {

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

• 时间复杂度O（n²）

二、选择排序

1、算法思想

1. 找到所有数中最大值下标
2. 找到最大值的下标与最后一个位置的数值交换位置，这样每次找到的最大值则固定到最后
3. 循环1、2操作直至遍历找到所有

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 选择排序：找到当前数中最大的数字，找到后与最后一个位置的数字交换位置，直至循环遍历完所有的数为止
 */
private void selectSort() {

    for (int i = 0; i < array.length; i++) {

        // 定义最大数字的下标，默认为0
        int max = 0;
        for (int j = 0; j < array.length - i; j++) {

            // 找到比自己大的数就更新下标
            if (array[max] < array[j]) {
                max = j;
            }
        }

        // 将找到最大的数与最后一个数字交换位置
        int temp = array[array.length - i - 1];
        array[array.length - i - 1] = array[max];
        array[max] = temp;
    }

}

• 时间复杂度O（n²），但是由于选择排序每轮比较只交换一次，所以实际性能要优于冒泡

三、直接插入排序

1、算法思想

1. 从位置1的数值n开始，将前面已经遍历过的数值集合看成数组m，则将n往m中插入
2. n插入到集合m中时从后往前比较，如果比n大则往后移一位，如果比较到比n小，则当前位置就是插入n的位置
3. 通过1、2的操作则可以保证每次插入n后m的集合都是排好的序列
4. 循环1、2、3操作将集合中所有数值均插入一遍即排序完成

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 直接插入排序：从1开始遍历数组，每个数字都在前面已经遍历的数字中插入
 * 从小到大排序的话碰到比它大的则往后移，直到比它小为止
 */
private void insertSort() {
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];
        int j;
        // 在前面已经遍历过的数字中比较若小于则往后移
        for (j = i - 1; j >= 0; j--) {
            if (temp < array[j]) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = temp;
    }
}

• 时间复杂度O（n²）

四、二分法排序

• 二分法排序是直接插入排序的改进版本，直接插入排序插入到前方集合中时采用的方式是逐个比较，二分法则是采用二分比较

1、算法思想

1. 从位置1的数值为n，将前面已经遍历过的数值集合看成数组m，则将n往m中插入
2. n插入到集合m中时采用二分法，先比较m中中间的数值，如果比n大则继续比较后面一半集合的中间的数值，直至比较到拆分的集合中左边一半或者右边一半没有值为止，则当前中间值的位置即为n插入到m中的位置
3. 通过1、2的操作则可以保证每次插入n后m的集合都是排好的序列
4. 循环1、2、3操作将集合中所有数值均插入一遍即排序完成

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 二分插入排序：从1开始遍历，已经遍历的数组中头是left，尾是right，遍历到的数字与中间的数字对比
 * 若小于中间的数字则right变更成中间数字前面的一个数字，反之则变更left
 * 直至最后left>right则插入
 */
private void binaryInsertSort() {
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];
        int left = 0, right = i - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (temp < array[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 将遍历到比他大的数字全部往后移一位
        for (int j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = temp;
    }
}

• 时间复杂度O(nlogn)

五、希尔排序

1、算法思想

1. 定义一个增量m，集合的长度为n，则将集合拆分成n/m组，每组内部进行比较排序
2. 每组内比较的方法无要求，可以用插入或者二分法都行
3. 假如要排序一段集合为{4，1，2，3}，定义m为2，则拆分成两组两两比较，即为4和2比，1和3比
4. 因此按照1、2的思路每比较一次都可以将m组内的数值排序
5. 不断变化m的值，多次分组遍历之后即可排序

2、代码示例

• m的变化方式有多种，不同的变化方式可能排序结果和效率不同。此处示例采用的方式是m=m/2

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 希尔排序：定义一个增量m，比较的数字集合总数为n，则将集合分成n/m组，每组进行插入排序
 * 随后m递减，多次比较之后就可得出排序后的集合
 */
private void shellSort() {
    int m = array.length;
    while (true) {
        // 本次增量的变化方式为 m/2
        m = m / 2;
        // 分组后的数组下标为n/m的摩
        for (int i = 0; i < m; i++) {
            // 分组后数组的数据为原数组下标摩为i的数
            for (int j = i + m; j < array.length; j += m) {
                // 每组内部进行插入排序（此处使用直接插入排序方式，也可使用二分法插入）
                int temp = array[j];
                int k;
                // 在前面已经遍历过的数字中比较若小于则往后移
                for (k = j - m; k >= i; k -=m) {
                    if (temp < array[k]) {
                        array[k + m] = array[k];
                    } else {
                        break;
                    }
                }
                array[k + m] = temp;
            }
        }

        if (m == 1) {
            break;
        }
    }
}

• 时间复杂度O(nlogn)

六、快速排序

1、算法思想

1. 快速排序的思想主要是先设置一个基准点m，这里我们假设每次设置的基准点都是每一组的第一个数值
2. 拿着基准点m在集合中进行比较，找到它应该放置的位置
3. 比较方式主要是定义集合中最左边的下标left，最右边的下标right，从左边开始比较，比m小则left++，找到比m大的则停住，将left下标的值赋值成right下标的值，然后同理比较right，比m大的则right–，找到比m小的就赋值成left下标的值。当left==right之后则比较完成
4. 经过步骤3的比较之后则可以找到m点排序所在的位置，然后集合被分成前后两半，各自按照1、2、3的方式排序，递归至全部拆分比较完成后即排序完成

• 由于步骤3思想较复杂一点，特此引用《啊哈！算法》一书中的插图演示一下，图中以第一个点6为基准点，找到6排序后应该所在的位置

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/** * 快速排序：找到某个点排序之后它应该所在的位置 */
private void quickSort() {
    quickSort(0, array.length - 1);
}

/** * 找到开始和结束位置之间以第一个数为基数，这个基数应该所在的位置 * 找到之后以基数为中心点拆分成前后两段，依次递归进行本操作，直至最后遍历完所有基数为止 * * @param low 开始的点下标 * @param high 结束的点下标 */
private void quickSort(int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = getMiddle(low, high);
    quickSort(low, mid - 1);
    quickSort(mid + 1, high);
}

/** * 通过比较获取最开始基数最后所在的位置 * * @param low 最开始的位置 * @param high 结束的位置 * @return 最后基数所在的位置 */
private int getMiddle(int low, int high) {
    int temp = array[low];
    while (low < high) {
        while (low < high && array[high] >= temp) {
            high--;
        }
        array[low] = array[high];

        while (low < high && array[low] <= temp) {
            low++;
        }
        array[high] = array[low];
    }
    array[low] = temp;
    return low;
}

• 时间复杂度O(nlogn)

七、堆排序

1、算法思想

1. 将数组构建成大堆二叉树，即所有节点的父节点的值都大于叶子节点的完全二叉树
2. 若叶子节点比父节点大，则交换位置
3. 根节点即为最大值，则将根节点与最后的的一个叶子节点交换位置
4. 重复1，2操作，每次都找最大值则放置最后即可排序完成

• 由于堆排序运用到了完全二叉树的数据结构，较难理解，特地在网上找了个算法演示的图片参考

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 堆排序，将数组构建成大堆二叉树，即父节点比叶子节点大的二叉树
 * 从小到大排序的话则每次直接将根节点放置到最后一位，循环往复直至遍历完所有为止
 */
private void heapSort() {

    // 先构建一次大堆二叉树，做一个基本的排序
    buildMaxHeap();

    for (int i = array.length - 1; i > 0; i--) {
        // 将最大值与最后一个位置的数交换
        exchangeValue(0, i);

        // 重新构建大堆二叉树，从0开始往下检测是否需要重新构建大堆
        maxHeap(i, 0);
    }

}


/**
 * 构建大堆二叉树，从最底层开始往上构建，最底层的父节点则是总长度的一半
 */
private void buildMaxHeap() {
    int length = array.length;
    for (int i = length / 2 - 1; i >= 0; i--) {
        maxHeap(length, i);
    }
}


/**
 * 构建大堆二叉树的节点，若修改了顺序，则递归重新构建下一层
 *
 * @param length 构建数据数组长度
 * @param node 构建堆排序的父节点
 */
private void maxHeap(int length, int node) {
    int left = 2 * node + 1;
    int right = 2 * node + 2;
    // 找到一个节点和他的孩子节点中的最大值下标
    int maxIndex = node;
    if (left < length && array[left] > array[maxIndex]) {
        maxIndex = left;
    }
    if (right < length && array[right] > array[maxIndex]) {
        maxIndex = right;
    }

    // 如果不是父节点最大，则跟最大的孩子节点交换
    if (maxIndex != node) {
        exchangeValue(node, maxIndex);
        maxHeap(length, maxIndex);
    }
}



/**
 * 交换两个下标的数值
 *
 * @param first  第一个下标
 * @param second 第二个下标
 */
private void exchangeValue(int first, int second) {
    int temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}

• 时间复杂度O(nlogn)

八、归并排序

1、算法思想

1. 将数据集合两分拆开
2. 循环拆分至每组只剩一个为止
3. 将拆分的数组进行排序组合
4. 两两合并，直至合并成一个数组即排序完成

• 算法思想参考下图
  

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 归并排序：将数据集合两分拆开，直至最小之后两两排序合并
 */
private void mergeSort() {
    int[] temp = new int[array.length];
    mergeSort(temp, 0, array.length - 1);
}


/**
 * 查分数组，如果数组不能拆分了，则直接返回，拆分之后合并
 */
private void mergeSort(int[] temp, int start, int end) {

    if (start >= end) {
        return;
    }

    int mid = (start + end) / 2;
    mergeSort(temp, start, mid);
    mergeSort(temp, mid + 1, end);
    mergeArray(temp, start, mid + 1, end);
}


/**
 * 将数组array，以mid为中心，前后两个数组进行合并
 */
private void mergeArray(int[] temp, int start, int mid, int end) {

    // 定义指针下标，记录前后段是够可以继续移动
    int minA = start, minB = mid;
    for (int i = start; i <= end; i++) {
        if (minA >= mid || minB > end) {
            // 如果a或者b用完了，则直接用对方的
            if (minA >= mid) {
                temp[i] = array[minB];
                minB++;
            } else {
                temp[i] = array[minA];
                minA++;
            }
        } else {
            // 都没用完则比较大小
            if (array[minA] < array[minB]) {
                temp[i] = array[minA];
                minA++;
            } else {
                temp[i] = array[minB];
                minB++;
            }
        }
    }

    System.arraycopy(temp, start, array, start, end - start + 1);
}

• 时间复杂度O(nlogn)

九、基数排序

1、算法思想

1. 基数排序又称桶排序，具体思想就是将数值当成数组的下标保存
2. 将所有数值拿出个位来比较，例如值为m的就存入下标为m的数组中
3. 将比较后的数组拿出即为按个位排序好的数组，再将这个排序好的数组按十位排序
4. 比较完个十百千所有位数以后即排序完成

• 步骤一思想参考图
  

2、代码示例

private int[] array = {23, 11, 7, 29, 33, 59, 8, 20, 9, 3, 2, 6, 10, 44, 83, 28, 5, 1, 0, 36};

/**
 * 基数排序，先按个位将所有数字按照个位的值放入0-9的二维数组中，依次取出之后再按十位
 * 如此循环直至个十百千等等所有位数遍历完为止
 */
private void radixSort() {

    // 定义二位数组用来存储每个基数以及基数下的数值
    int[][] temp;

    // 定义一维数组记录基数下保存了几位
    int[] position;

    int radix = 1;

    while (true) {
        position = new int[10];
        temp = new int[10][array.length];

        for (int i = 0; i < array.length; i++) {
            int value = (array[i] / radix) % 10;
            temp[value][position[value]] = array[i];
            position[value]++;
        }

        // 判断是否所有的数值都在0位上，都在0位上则表示排序完成
        if (position[0] == array.length) {
            break;
        }

        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < position[i]; j++) {
                array[index] = temp[i][j];
                index++;
            }
        }

        radix = radix * 10;
    }
}

• 基数排序的时间复杂度为O(d(n+r))，r为基数，d为位数