经典排序算法与Java实现

冒泡排序

基本思路

1、 比较相邻两个元素，如果第一个比第二个大，就交换它们两个；
2、 对每一组相邻元素做同样的工作，从开始第一对到结尾最后一对，每次都把相对较大的元素放到后面，看上去就像当前最大的元素“冒”到了后面；
3、 重复上述步骤，每次排序都确定一个数的顺序，直到 N 次遍历后完成排序。

代码实现

public void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length; i++) {
        // 每一轮都把前 arr.length-1-i 中最大的数放到当前最后一个位置上
        for(int j = 0; j < arr.length-1-i; j++) {
            // 如果前一个数大于后一个数，则交换它们两个
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
            }
        }
    }
}

复杂度分析

• 时间复杂度 ：T(n) = O(n^2)
• 空间复杂度 ：S(n) = O(1)

补充

使用改进冒泡排序的话，时间复杂度可能达到 O(n)；示例代码如下 ：

public void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length; i++) {
        // 是否交换过顺序
        boolean didSwap = false;
        for(int j = 0; j < arr.length-1-i; j++) {
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1);
                didSwap = true;
            }
        }
        // 若这轮执行下来发现没做过交换，说明此时已经是排好序的了
        if(!didSwap) {
            return;
        }
    }
}

选择排序

基本思路

1、 将整个数组分为“已排序”和“未排序”两个部分；
2、 每次遍历找到最小的元素，然后将它放入“已排序”部分的末尾；
3、 这样经过 N 遍历，所有的元素就都在“已排序”的部分啦。

代码实现

public void selectionSort(int[] arr){
    for(int i = 0; i < arr.length; i++) {
        // i 指向有序区末尾，index 是当前最小值的下标
        int index = i;
        for(int j = i; j < arr.length; j++) {
            if(arr[j] < arr[index]) {
                index = j;
            }
        }
        // 将无序区的最小值放入有序区末尾
        swap(arr, i, index);
    }
}

复杂度分析

• 时间复杂度 ：T(n) = O(n^2)
• 空间复杂度 ：S(n) = O(1)

插入排序

基本思路

1、 将整个数组分为“已排序”和“未排序”两个部分；
2、 每次从“未排列”部分取一个数，按顺序插入“已排序”部分；
3、 这样经过 N 遍历，所有的元素就都在“已排序”的部分啦。

代码实现

public void insertSort(int[] arr) {
    for(int i = 0; i < arr.length-1; i++) {
        // 取无序部分的第一个元素
        int cur = arr[i+1];
        // index 指向有序部分的最后一个元素
        int index = i;
        // 依次移动有序部分的元素，直到找到 cur 应在的位置
        while(index >= 0 && cur < arr[index]) {
            arr[index+1] = arr[index--];
        }
        arr[index+1] = cur;
    }
}

复杂度分析

• 时间复杂度 ：
  • 最佳情况 ：T(n) = O(n)
  • 最坏情况 ：T(n) = O(n^2)
  • 平均情况 ：T(n) = O(n^2)
• 空间复杂度 ：S(n) = O(1)

希尔排序

基本思路

希尔排序是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。与简单插入排序不同，希尔排序会优先比较距离较远的元素。

动图演示如下 ：

代码实现

public void shellSort(int[] arr) {
    int gap = arr.length / 2;
    while(gap > 0) {
        // 这其实就是一个希尔排序，这只是将间隔由 “1” 变成了 “gap”
        for(int i = 0; i < arr.length-gap; i++) {
            int cur = arr[i + gap];
            int index = i;
            while(index >= 0 && cur < arr[index]) {
                arr[index + gap] = arr[index];
                index -= gap;   
            }
            arr[index + gap] = cur;
        }
        gap /= 2;
    }
}

复杂度分析

• 时间复杂度 ：
  • 最佳情况 ：T(n) = O(n)
  • 最坏情况 ：T(n) = O(n^2)
  • 平均情况 ：T(n) = O(n^1.3)
• 空间复杂度 ：S(n) = O(1)

归并排序

基本思路

1、 将长度为 n 的输入序列分成两个长度为 n/2 的子序列；
2、 对这两个子序列分别采用归并排序；
3、 将两个排好序的子序列合并成一个最终的排序序列。

代码实现

public class MergeSort {
    /**
     * 采用归并的方法对无序数组进行排序
     */
    public int[] MergeSort(int[] arr){
        if(arr.length < 2){
            return arr;
        }
        int mid = arr.length / 2;
        // 将数组分为左右两部分
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);
        // 对左右分别进行排序，然后合并
        return merge(MergeSort(left), MergeSort(right));
    }

    /**
     * 合并两个有序数组
     */
    public int[] merge(int[] left, int[] right){
        int[] res = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < res.length; index++) {
            // 前两个分支考虑的是是其中一个数组遍历完了的情况
            if (i >= left.length) {
                res[index] = right[j++];
            } else if (j >= right.length) {
                res[index] = left[i++];
            // 后两个分支直接合并，谁小谁在前
            } else if (left[i] < right[j]) {
                res[index] = right[i++];
            } else {
                res[index] = left[j++];
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：T(n) = O(nlog n)
• 空间复杂度：S(n) = O(n)

快速排序

基本思路

1、 从数列中挑出一个元素作为“基准数”，一般挑选左边第一个；
2、 从后半部分向前扫描，直到找到第一个比 mark 小的数，记为 A，从前半部分向后扫描，直到找到第一个比 mark 大的数，记为 B，交换 A、B；
3、 重复步骤 2，直到 left 与 right 相遇，交换基准数与相遇点，则本次“分区”结束；
4、 在分区结束后，该基准就处于数列的中间位置；将其左右分别视为两个新数列，递归地进行再分区，直到每个区域只有一个元素，排序就完成了。

代码实现

public class QuickSort {
    public void QuickSort(int[] arr, int left, int right){
        if (left < right) {
            // 对数列进行分区，并获取上一个基准数的下标，也就是这一次操作的分区线
            int partition = partition(arr, left, right);
            // 对左边递归排序
            QuickSort(arr, left, partition-1);
            // 对右边递归排序
            QuickSort(arr, partition+1, right);
        }
    }

    public int partition(int[] arr, int left, int right){
        // 选择范围内的第一个为基准数
        int mark = arr[left];
        while (left < right) {
            // 从后半部分向前扫描，直到找到第一个比 mark 小的数，记为 A
            while (left < right && arr[right] >= mark) right--;
            arr[left] = arr[right];
            // 从前半部分向后扫描，直到找到第一个比 mark 大的数，记为 B
            while (left < right && arr[left] <= mark) left++;
            // 这句联系上句，其实起到的是一个交换 A、B 的作用
            arr[right] = arr[left];
        }
        arr[left] = mark;
        return left;
    }
}

复杂度分析

• 时间复杂度：
  • 最佳情况：T(n) = O(nlog n)
  • 最差情况：T(n) = O(n^2)
  • 平均情况：T(n) = O(nlog n)
• 空间复杂度：
  • 平均：S(n) = O(log n)
  • 最差：S(n) = O(n)

堆排序

基本思路

1、 将待排序的数列构造成一个大顶堆（或小顶堆），整个序列的最大值（或最小值）就是堆顶的根节点；
2、 将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值（或最小值）；
3、 将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中的次大值（或次小值），如此反复执行，最终就能得到一个有序序列。

代码实现

public class HeapSort {
    /**
     * 构造/调整最大堆
     */
    public void heapAdjust(int[] arr, int index, int length){
        // 保存当前结点的下标
        int max = index;
        // 当前节点左子节点的下标
        int lchild = 2*index;
        // 当前节点右子节点的下标
        int rchild = 2*index + 1;
        if(length > lchild && arr[max] < arr[lchild]){
            max = lchild;
        }
        if(length > rchild && arr[max] < arr[rchild]){
            max = rchild;
        }
        // 若此节点比其左右孩子的值小，就将其和最大值交换，并调整堆
        if(max != index){
            swap(arr, index, max);
            heapAdjust(arr, max, length);
        }
    }

    /**
     * 堆排序
     */
    public int[] heapSort(int[] arr) {
        int len = arr.length;
        // 初始化堆，构造一个最大堆
        for (int i = (len / 2 - 1); i >= 0; i--) {
            heapAdjust(arr, i, len);
        }

        for (int i = len-1; i > 0; i--) {
            // 将堆顶的元素和最后一个元素交换，并重新调整堆
            swap(arr, 0, i);
            heapAdjust(arr, 0, i);
        }
        return arr;
    }
}

复杂度分析

• 时间复杂度：T(n) = O(nlog n)
• 空间复杂度：S(n) = O(1)

计数排序

基本思路

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，它要求输入的数据必须是有确定范围的整数。

代码实现

public class CountingSort {
    /**
     * 计数排序
     * @param arr 该数组中存放的数据都在已知范围内
     * @param max 范围的最大值
     * @param min 范围的最小值
     */
    public static void countingSort(int[] arr, int max, int min){
        // 偏差
        int bias = 0 - min;
        // 新开辟一个数组，并将数据按下标依次存入新数组
        int[] bucket = new int[max - min +1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i] + bias]++;
        }

        // 将新数组中的数据依次取出，再放回原数组
        int index = 0;
        for (int i = 0; i < bucket.length; i++){
            int len = bucket[i];
            while (len-- > 0) {
                arr[index++] = i - bias;
            }
        }
    }
}

复杂度分析

当输入的元素是 n 个 0 到 k 之间的整数时，

• 时间复杂度：T(n) = O(n+k)
• 空间复杂度：S(n) = O(k)

桶排序

基本思路

桶排序是计数排序的升级版，其原理在于 ：

假设输入数据服从均匀分布，将数据分配到有限数量的桶里，每个桶再分别排序（可以是使用别的排序算法，或是以递归方式继续使用桶排序）。

代码实现

public class BucketSort {
    public static ArrayList<Integer> bucketSort(ArrayList<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max)
                max = array.get(i);
            if (array.get(i) < min)
                min = array.get(i);
        }
        // 桶数量
        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        // 构造桶
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<>());
        }
        // 将元素装入桶中
        for (int i = 0; i < array.size(); i++) {
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        // 依次对桶中元素进行排序
        for (int i = 0; i < bucketCount; i++) {
            if (bucketSize == 1) {
                resultArr.addAll(bucketArr.get(i));
            } else {
                if (bucketCount == 1) {
                    bucketSize--;
                }
                // 这里是采用的递归的方法进行排序
                ArrayList<Integer> temp = bucketSort(bucketArr.get(i), bucketSize);
                resultArr.addAll(temp);
            }
        }
        return resultArr;
    }
}

复杂度分析

桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少，但相应的空间消耗就会增大。

当输入的元素是 n 个 0 到 k 之间的整数，一共划分 m 个桶时，

• 时间复杂度：
  • 最佳情况：T(n) = O(n+k)
  • 最差情况：T(n) = O(n^2)
  • 平均情况：T(n) = O(n+k)
• 空间复杂度：S(n) = O(n+m)

基数排序

基本思路

1、 取得数组中的最大数，并取得该数的位数；
2、 arr 为原始数组，从最低位开始取每个位组成 radix 数组；
3、 利用计数排序适用于小范围数的特点，分别在每个位上对 radix 进行计数排序。

代码实现

public class RadixSort {
    public void RadixSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }

        // 首先计算出最大数的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;

        // 然后对每一位进行计数排序
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for(int i = 0; i < 10; i++) {
            bucketList.add(new ArrayList<>());
        }
        for(int i = 0; i < maxDigit; i++, mod *= 10 , div *= 10){
            for (int value : arr) {
                int num = (value % mod) / div;
                bucketList.get(num).add(value);
            }
            int index = 0;
            for (ArrayList<Integer> integers : bucketList) {
                for (Integer integer : integers) {
                    arr[index++] = integer;
                }
                integers.clear();
            }
        }
    }
}

复杂度分析

当输入的元素是 n 个 0 到 k 之间的整数时，

• 时间复杂度：T(n) = O(n * k)
• 空间复杂度：S(n) = O(n + k)

总结

总而言之先放一张图 ：

术语说明 ：

• 稳定 ：如果原本 a 在 b 之前，而 a = b，则排序后 a 仍在 b 前面；
• 不稳定 ：如果 a 原本在 b 前面，而 ａ = b，排序之后 a 有可能会出现在 b 的后面；
• 内排序 ：所有排序操作都在内存中完成；
• 外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• 时间复杂度 ：描述算法运行时间的函数，用大 O 符号表示；
• 空间复杂度 ：描述算法所需要的内存空间大小。

参考文章 ：blog.csdn.net/meibenxiang…

文章永久链接：https://tech.souyunku.com/43626