排序算法

排序算法有 2 个指标：时间复杂度和稳定性

选择排序
时间复杂度：O(N^2)
不稳定

    public void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;

            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

冒泡排序
时间复杂度：O(N^2)
稳定

    public void sort(int[] arr) {
        for (int i = 0; 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);
                }
            }
        }
    }

插入排序
时间复杂度：O(N^2)
稳定

    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

希尔排序
时间复杂度：O(N^2)
不稳定

    public void sort(int[] arr) {
        for (int d = arr.length / 2; d > 0; d = d / 2) {
            for (int i = d; i < arr.length; i++) {
                int j = i;
                while (j - d >= 0 && arr[j] < arr[j - d]) {
                    swap(arr, j, j - d);
                    j -= d;
                }
            }
        }
    }

快速排序
时间复杂度：O(N*logN)
不稳定

    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int h) {
        if (l >= h) {
            return;
        }

        int mid = l;
        int midValue = arr[l];
        int i = l;
        int j = h;

        while (i < j) {
            while (i < j && arr[j] >= midValue) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] < midValue) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = midValue;
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, h);
    }
    

归并排序
时间复杂度：O(N*logN)
稳定

    public void sort(int[] arr) {
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private void mergeSort(int[] arr, int l, int h, int[] temp) {
        if (l >= h) {
            return;
        }
        int mid = (l + h) / 2;
        mergeSort(arr, l, mid, temp);
        mergeSort(arr, mid + 1, h, temp);
        merge(arr, l, mid, h, temp);
    }

    private void merge(int[] arr, int l, int mid, int h, int[] temp) {
        //i=[l,mid]
        int i = l;
        //j=[mid,h]
        int j = mid + 1;

        int t = 0;
        while (i <= mid && j <= h) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[t++] = arr[i++];
        }
        while (j <= h) {
            temp[t++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, l, h - l + 1);
    }
    

基数排序
时间复杂度：O(DN) D 为最大位数
时间复杂度完全公式：O(N*log(r)Max) Max 为最大数 r 为进制数
稳定

    public void sort(int[] arr) {
        int max = max(arr);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            radixSort(arr, exp);
        }
    }

    private int max(int[] a) {
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        return max;
    }

    private void radixSort(int[] arr, int exp) {
        int[] temp = new int[arr.length];
        int[] bucketIndexs = new int[10];

        // 将数据出现的次数存储在buckets[]中
        for (int aInt : arr) {
            bucketIndexs[(aInt / exp) % 10]++;
        }
        // 更改buckets[i]。目的是让更改后的buckets[i]的值，是该数据在output[]中的位置。
        for (int i = 1; i < 10; i++) {
            bucketIndexs[i] += bucketIndexs[i - 1];
        }

        // 将数据存储到临时数组output[]中
        for (int i = arr.length - 1; i >= 0; i--) {
            int bucketIndex = bucketIndexs[(arr[i] / exp) % 10];
            temp[bucketIndex - 1] = arr[i];
            bucketIndexs[(arr[i] / exp) % 10] = bucketIndex - 1;
        }
        System.arraycopy(temp, 0, arr, 0, arr.length);
    }