Java排序算法总结

作者: 左大人 | 来源:发表于2019-01-16 17:47 被阅读0次

序言

排序算法是面试过程中经常会被问到的基础知识，今天，我们来总结一下比较常见的几种排序算法：直接插入排序、希尔排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、桶排序、基数排序。

准备知识

在介绍各种排序算法之前，我们先来熟悉一些概念，包括时间复杂度、空间复杂度、算法稳定性。

1. 时间复杂度

时间频度：一个算法执行所消耗的时间，从理论上是不能算出来的，必须在机器上运行才知道。但我们不可能也没必要对每个算法上机测试，只需要知道那个算法花费时间多，那个花费时间少即可。并且算法花费时间与算法语句执行次数成正比。一个算法中语句执行次数成为语句频度或时间频度，用T(n)表示。

时间复杂度：时间频度T(n)中，n是问题的规模，当n不断变化时，T(n)也会发生变化。现在我们想知道这个变化的规律，因此引入时间复杂度概念。常见的时间复杂度有：常数阶O(1)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n²)、立方阶O(n³)、k次方阶O(n^{k)，指数阶O(2}n)。随着规模n的增大，上述时间复杂度不断增大，算法执行效率越低。

2. 空间复杂度

一个算法的空间复杂度是指算法所耗费的存储空间，它也是问题规模n的函数，主要包括存储算法本身占用的空间、算法输入输出数据占用的空间、算法运算过程中临时占用的空间。

3. 算法稳定性

通俗理解，就是保证两个相等的数，排序前和排序后位置保持不变。形式化表示：Ai == Aj，排序前Ai在Aj前面，那么排序后，Ai仍然在Aj前面。

常见算法

1. 直接插入排序

/**
 * 名称：1. 插入排序
 * 解释：找到当前元素在子数组（包括自身和之前的元素）中的位置。每次把当前元素插入到正确的位置。
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定
 */
public static void insertionSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }
    int i, j, tmp;
    for (i = 1; i < array.length; i++) {
        tmp = array[i];
        for (j = i; j > 0; j--) {
            if (tmp < array[j - 1]) {
                array[j] = array[j - 1];
                continue;
            }
            break;
        }
        array[j] = tmp;
    }
    System.out.println("插入排序结果：");
    for (int p = 0; p < array.length; p++) {
        System.out.println(array[p]);
    }
}

2. 希尔排序

/**
 * 名称：2. 希尔排序
 * 解释：选择步长gap（gap按一定规则减小，最后为1），i从gap开始向后遍历，每个元素都与(i-gap)所在元素进行比较，直至所有元素排序成功
 * 插入排序是希尔排序的特殊情况（gap=1）
 * 时间复杂度：平均O(n^1.3)，与gap相关
 * 空间复杂度：O(1)
 * 不稳定
 */
public static void shellSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }
    int gap, i, j, tmp;
    for (gap = array.length / 2; gap > 0; gap = gap / 2) {
        for (i = gap; i < array.length; i++) {
            tmp = array[i];
            for (j = i; j >= gap; j = j - gap) {
                if (tmp < array[j - gap]) {
                    array[j] = array[j - gap];
                    continue;
                }
                break;
            }
            array[j] = tmp;
        }
    }
    System.out.println("希尔排序结果：");
    for (int p = 0; p < array.length; p++) {
        System.out.println(array[p]);
    }
}

3. 冒泡排序

/**
 * 名称：3. 冒泡排序，相邻两个比较，反序则交换位置，每次会把(n-1-i)位置的数排好，即每次排好最大的元素
 * 与插入排序的区别：插入排序每次把当前元素在它之前的数组找到位置，冒泡排序每次排好最后一个元素
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 稳定
 */
public static void bubbleSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }
    int i, j, tmp;
    for (i = 0; i < array.length - 1; i++) {
        for (j = 0; j < array.length - 1 - i; j++) {
            if (array[j + 1] < array[j]) {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
    System.out.println("冒泡排序结果：");
    for (int p = 0; p < array.length; p++) {
        System.out.println(array[p]);
    }
}

4. 选择排序

/**
 * 名称：4. 选择排序，从i开始，每次从子数组（i->length）中找到最小的元素，和位置i的元素进行交换，即每次排好最小的元素
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 * 不稳定
 */
public static void selectSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }
    int i, j, min, tmp;
    for (i = 0; i < array.length - 1; i++) {
        min = array[i];
        for (j = i + 1; j < array.length; j++) {
            if (array[j] < min) {
                tmp = min;
                min = array[j];
                array[j] = tmp;
            }
        }
        array[i] = min;
    }
    System.out.println("选择排序结果：");
    for (int p = 0; p < array.length; p++) {
        System.out.println(array[p]);
    }
}

5. 快速排序

/**
 * 名称：5. 快速排序，以某个元素为锚点，从右边开始找比锚点小的元素，从左边开始找比锚点大的元素，交换二者，递归进行直至排序完成
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(logn)，因为递归调用
 * 不稳定
 */
public static void quickSort(int[] array, int left, int right) {
    if (array == null && array.length == 0) {
        return;
    }
    int i, j, anchor, tmp;
    if (left > right) {
        return;
    }
    anchor = array[left];
    i = left;
    j = right;
    while (i < j) {
        //从右边开始找到小于anchor的数（必须从右边开始找，因为最后结束的那个元素需要与锚点交换位置，这个元素必须比锚点小）
        while (array[j] >= anchor && j > i) {
            j--;
        }
        //从左边开始找到大于anchor的数
        while (array[i] <= anchor && i < j) {
            i++;
        }
        //交换两者
        if (i < j) {
            tmp = array[i];
            array[i] = array[j];
            array[j] = tmp;
        }
    }
    //交换锚点和ij相交元素
    array[left] = array[j];
    array[j] = anchor;

    //递归继续排列左右两边的元素
    quickSort(array, left, j - 1);
    quickSort(array, j + 1, right);
}

private static void testQuickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
    System.out.println("快速排序结果：");
    for (int p = 0; p < array.length; p++) {
        System.out.println(array[p]);
    }
}

6. 堆排序

/**
 * 名称：6. 堆排序，把待排序数组当做一个完全二叉树（特点left=parent*2+1 right=parent*2+2），然后对二叉树进行一次遍历排序，使得堆顶元素最大，把最大元素放到最后面，然后重复上述步骤
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(1)
 * 不稳定
 */
public static void heapSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }

    int p, i, tmp, left, right, maxIndex;
    //从末尾开始逐步缩小待排序数组，直至排序完成
    for (p = array.length - 1; p > 0; p--) {
        //对每个节点进行一次排序，达到所有父节点 > 子节点
        for (i = (p + 1) / 2 - 1; i >= 0; i--) {
            left = i * 2 + 1;
            right = i * 2 + 2;
            maxIndex = i;
            if (left <= p && array[left] > array[maxIndex]) {
                maxIndex = left;
            }
            if (right <= p && array[right] > array[maxIndex]) {
                maxIndex = right;
            }
            //把虽大元素交换到父节点
            if (maxIndex != i) {
                tmp = array[i];
                array[i] = array[maxIndex];
                array[maxIndex] = tmp;
            }
        }
        //把堆顶元素放到数组末尾
        tmp = array[0];
        array[0] = array[p];
        array[p] = tmp;
    }

    System.out.println("堆排序结果：");
    for (int k = 0; k < array.length; k++) {
        System.out.println(array[k]);
    }
}

7. 归并排序

/**
 * 名称：7. 归并排序，把一个很长的数组逐步分成小数组排序，然后又合并为大的数组排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)，因为递归调用
 * 稳定
 */
public static void mergeSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }
    internalSort(array, 0, array.length - 1);
    System.out.println("归并序结果：");
    for (int k = 0; k < array.length; k++) {
        System.out.println(array[k]);
    }
}

private static void internalSort(int[] array, int left, int right) {
    if (left < right) {
        int middle = (left + right) / 2;
        internalSort(array, left, middle);
        internalSort(array, middle + 1, right);
        sort(array, left, middle, right);
    }
}

private static void sort(int[] array, int left, int middle, int right) {
    int i = left;
    int j = middle + 1;
    int[] tmp = new int[array.length];
    int index = left;
    while (i <= middle && j <= right) {
        if (array[i] < array[j]) {
            tmp[index++] = array[i++];
        } else {
            tmp[index++] = array[j++];
        }
    }
    while (i <= middle) {
        tmp[index++] = array[i++];
    }
    while (j <= right) {
        tmp[index++] = array[j++];
    }

    for (int p = left; p <= right; p++) {
        array[p] = tmp[p];
    }

}

8. 桶排序

/**
 * 名称：8. 桶排序，把最大元素和最小元素的差值划分为若干区间，然后把每个数加入到对应的区间，对每个区间排序，最后把各区间连接起来
 * 时间复杂度：O(n+k)
 * 空间复杂度：O(n+k)
 * 依赖桶内排序算法（如果用到桶内排序用到快排，则不稳定）
 */
public static void bucketSort(int[] array) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
        if (array[i] < min) {
            min = array[i];
        }
    }
    //根据数组元素区间获取桶数量
    int bucketNum = (max - min) / array.length + 1;
    ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketNum);
    for (int i=0; i<bucketNum; i++){
        buckets.add(new ArrayList<Integer>());
    }
    //把元素加入到桶中
    for (int i=0; i<array.length; i++) {
        buckets.get((array[i] - min)/array.length).add(array[i]);
    }
    //对每个桶内元素进行排序
    for (int i=0; i<bucketNum; i++){
        Collections.sort(buckets.get(i));
    }
    System.out.println(buckets.toString());
}

9. 基数排序

/**
 * 名称：9. 基数排序，从个位开始（循环到最高位），把每个元素按照取模值放入二维数组对应的位置，一个次循环完毕之后，
 *      把二维数组中的元素又放回到原数组中
 * 时间复杂度：O(kn)
 * 空间复杂度：O(kn)
 * 稳定
 */
public static void radixSort(int[] array) {
    if (array == null && array.length == 0) {
        return;
    }
    //找到数组中的最大值
    int max = array[0];
    int length = array.length;
    int k = 1;  //用来取各个位上的数字
    int index = 0;
    for (int i = 1; i < length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    int[][] buckets = new int[10][length];
    int[] counts = new int[10];
    int digit;
    while (k <= max) {
        //把元素添加到二维数组中
        for (int i=0; i<length; i++) {
            digit = (array[i]/k) % 10;
            buckets[digit][counts[digit]++] = array[i];
        }
        //把二维数组中的元素顺序放入数组中
        for (int i=0; i<10; i++) {
            if (counts[i] > 0) {
                for (int j=0; j < counts[i]; j++) {
                    array[index++] = buckets[i][j];
                }
            }
            counts[i] = 0;
        }
        k *= 10;
        index = 0;
    }
    System.out.println("基数排序结果：");
    for (int p = 0; p < array.length; p++) {
        System.out.println(array[p]);
    }
}

总结

上面给出了各种排序算法的实现，并且每个算法都给了比较详细的注释，各位同学可以参考注解理解代码，这里给出各算法的一览图：

image.png