排序算法

基本介绍

内部排序
- 将需要处理的所有数据都加载到内部存储器中进行排序。
- 分类
  - 插入排序
    - 直接插入排序（稳定，不占用额外空间，O(n^2)）
    - 希尔排序（不稳定，不占用额外空间，O(nlogn)）
  - 选择排序
    - 简单选择排序（不稳定，不占用额外空间，O(n^2)）
    - 堆排序（不稳定，不占用额外空间，O(nlogn)）
  - 交换排序
    - 冒泡排序（稳定，不占用额外空间，O(n^2)）
    - 快速排序（不稳定，不占用额外空间，O(nlogn)）
  - 归并排序（稳定，占用额外空间，O(nlogn)）
  - 基数排序（桶排序）:（稳定，占用额外空间，O(n*桶的个数)）
外部排序

时间复杂度

方法
- 事后统计法
- 事前估算法
时间频度 T(n) ：一个算法中语句的执行次数
- 算法话费的时间与算法中语句执行次数成正比
时间复杂度 O(n)
- T(n)不同，O(n)可能相同
- 常见的时间复杂度
  - 1、log2n、n、nlog2n、n^2^、n^3^、n^k^、2^n^、n！
平均时间复杂度
最坏时间复杂度

空间复杂度

该算法所消耗的存储空间

冒泡排序

从前到后依次比较相邻元素的值，发现逆序这交换，使值比较大的逐渐从前移向后。

规则
- 一共进行数组的大小-1次的循环
- 每一趟排序的次数在逐渐的减少
- 如果我们发现在某趟排序中，没有发生一次交换，可以提前结束排序（优化）

选择排序

按指定规则选出某个元素，再依规定交换位置后达到排序的目的。

规则
- 一共有n-1轮排序
- 假定当前的数是最小数，从后面的每个数一次比较
- 如果找到更小数，重新确定最小数，获得下标
- 遍历完本轮数组后，进行交换
- 之后缩减范围，继续重复过程

插入排序

对欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的

存在问题：当需要插入的数是比较小的数时，后移的次数明显增多，对效率有影响

希尔排序

缩小增量排序

快速排序

冒泡排序的改进，基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分数据比另一部分数据都要小，然后再按子方法分别进行快速排序。过程可递归运行

归并排序

采用分治思想

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2; //中间索引
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            //分解完合并
            merge(arr, left, mid, right, temp);
        }
    }

    //合并方法
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 初始化i，左边有序序列的初始索引
        int j = mid + 1; // 初始化j，右边有序序列的初始索引
        int t = 0; // 指定temp数组的当前索引

        //先把左右两边（有序）按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        //将有剩余数据的一边的数据，依次全部填充到temp
        while (i <= mid) {
            temp[t++] = arr[i++];
        }

        while (j <= right) {
            temp[t++] = arr[j++];
        }
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }
}

基数排序

稳定性，效率最高的稳定性排序法

问题：耗费空间

有负数的数组，不使用基数排序来进行排序

//基数排序法
public static void radixSort(int[] arr) {

    //计算数组中最大数的位数
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    //得到最大数是几位数
    int maxLength = (max + "").length();
    int[][] bucket = new int[10][arr.length];

    //为了记录每个桶，存储每个桶的数量
    int[] bucketElementCounts = new int[10];

    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {

        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的对应位的值
            int digitOfElement = arr[j] / n % 10;
            //放进对应的桶，然后对应 数量++
            bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = arr[j];
        }

        int index = 0;
        for (int k = 0; k < bucketElementCounts.length; k++) {
            if (bucketElementCounts[k] > 0) {
                //如果桶中有数据，才放入原数组
                for (int t = 0; t < bucketElementCounts[k]; t++) {
                    //取元素放入arr
                    arr[index++] = bucket[k][t];
                }
            }
            //第i+1轮处理完之后，需要清0
            bucketElementCounts[k] = 0;
        }
    }
}

排序算法 #

基本介绍 #

时间复杂度 #

空间复杂度 #

相关概念 #

冒泡排序 #

选择排序 #

插入排序 #

希尔排序 #

快速排序 #

归并排序 #

基数排序 #