排序算法

最基础的十大排序算法

冒泡排序
选择排序
插入排序
希尔排序
堆排序
归并排序
快速排序
计数排序
桶排序
基数排序

基于比较的排序算法，常见有：

冒泡排序

重复遍历数组（每次遍历不断减少），每轮遍历不断比较并往后交换较大值，用一个变量记录最近的一次交换，可以减少交换次数，
在部分有序的情况下，可以减少交换次数。

public static void bubbleSort(int[] nums) {
        int j = nums.length - 1;
        while (true) {
            int x = 0;
            for (int i = 0;i < j;i++) {
                if (nums[i] > nums[i + 1]) {
                    int tmp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = tmp;
                    x = i;
                }
            }
            if (j == 0)
                break;
            j = x;
        }
    }

选择排序

将数组分为两部分，从后往前每轮遍历获取最大值并进行交换，减少了交换次数。

public static void selectionSort(int[] nums) {
        int maxIdx;
        int r = nums.length - 1;
        do {
            maxIdx = r;
            for (int i = 0; i < r; i++) {
                maxIdx = nums[i] > nums[maxIdx] ? i : maxIdx;
            }

            if (nums[r] != nums[maxIdx] && maxIdx != r){
                int tmp = nums[r - 1];
                nums[r - 1] = nums[maxIdx];
                nums[maxIdx] = tmp;
            }

            r--;
        } while (r != 0);
    }

堆排序

插入排序

将数组分为两部分，左边为有序部分，右边为无序部分，每次从无序部分挑选最左值往有序部分插入（方向为从large到small）

伪代码

public static void insertionSort(int[] nums) {
        int left = 1;
        int i;
        while (left != nums.length) {
            int tmp = nums[left];

            i = left - 1;
            for (;i >= 0;i--) {
                if (tmp < nums[i]) {
                    nums[i + 1] = nums[i];
                } else {
                    nums[i + 1] = tmp;
                    break;
                }
            }

            if (i < 0)
                nums[0] = tmp;
            left++;
        }
    }

希尔排序

基于插入排序，用gap进行分组排序，可以减少移动次数。

public static void shellSort(int[] nums) {
        for (int g = nums.length >> 1;g >= 1;g = g >> 1) {
            for (int x = 0;x + g < nums.length;x++) {
                int left = x + g;
                int i;
                while (left < nums.length) {
                    int tmp = nums[left];

                    i = left - g;
                    for (;i >= 0;i-=g) {
                        if (tmp < nums[i]) {
                            nums[i + g] = nums[i];
                        } else {
                            nums[i + g] = tmp;
                            break;
                        }
                    }

                    if (i < 0)
                        nums[x] = tmp;
                    left+=g;
                }
            }
        }
    }

归并排序

可以分解为子问题，不断划分数组，当数组大小为1时返回（有序），返回的过程中合并两个有序部分。

public static void mergeSort(int[] nums) {
        helpMS(nums, 0, nums.length - 1);
    }

    private static void helpMS(int[] nums, int l, int r) {
        if (l == r)
            return;

        int m = (l + r) >> 1;
        helpMS(nums, l, m);
        helpMS(nums, m + 1, r);

        int[] temp = new int[r - l + 1];
        int x = l;
        int y = m + 1;
        int idx = 0;
        while (x <= m && y <= r) {
            if (nums[x] < nums[y]){
                temp[idx++] = nums[x];
                x++;
            } else {
                temp[idx++] = nums[y];
                y++;
            }
        }

        if (x <= m) {
            for (int i = x;i <= m;i++){
                temp[idx++] = nums[i];
            }
        } else {
            for (int i = y;i <= r;i++){
                temp[idx++] = nums[i];
            }
        }

        System.arraycopy(temp, 0, nums, l, temp.length);
    }

归并排序（迭代法实现）

    // 迭代归并排序
    public static void mergeSortIterative(int[] arr) {
        int n = arr.length;

        // 当前大小的子数组
        for (int currSize = 1; currSize < n; currSize *= 2) {
            // 当前子数组的左起始点
            for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
                // 找到子数组的中点和右结束点
                int mid = Math.min(leftStart + currSize - 1, n - 1);
                int rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);

                // 合并子数组
                merge(arr, leftStart, mid, rightEnd);
            }
        }
    }
    
    // 合并两个子数组 arr[l..m] 和 arr[m+1..r]
    public static void merge(int[] arr, int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        // 创建临时数组
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 拷贝数据到临时数组
        System.arraycopy(arr, l, L, 0, n1);
        System.arraycopy(arr, m + 1, R, 0, n2);

        // 合并临时数组

        // 初始索引
        int i = 0, j = 0;

        // 初始合并子数组的索引
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 拷贝L[]的剩余元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // 拷贝R[]的剩余元素
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

快速排序

找一个基准值，若基准值左右都有序则有序，可拆分为子问题。

    public static void quickSort(int[] nums) {
        helpQS(nums, 0, nums.length - 1);
    }

    private static void helpQS(int[] nums, int l, int r) {
        if (l >= r)
            return;

        int x = partition2(nums, l, r);
        helpQS(nums, l, x - 1);
        helpQS(nums, x + 1, r);
    }

    private static int partition2(int[] nums, int l, int r) {
        int idx = new Random().nextInt(r - l + 1) + l;

        if (idx != l) {
            int t = nums[idx];
            nums[idx] = nums[l];
            nums[l] = t;
        }

        int i = l + 1;
        int j = r;
        int t = nums[l];

        while (i < j) {
            while (i < j && nums[j] > t) {
                j--;
            }

            while (i < j && nums[i] < t) {
                i++;
            }

            if (i != j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
                j--;
            }
        }

        nums[l] = nums[j];
        nums[j] = t;
        return j;
    }

不基于比较的排序算法

计数排序

遍历数组，找出min和max值，通过min设置偏移量，能够对负数进行计数

public static void countingSort(int[] nums) {
        int max = 0;
        int min = 0;
        for (int num : nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }

        int offset = 0;
        if (min < 0) offset = Math.abs(min);

        int[] temp = new int[max + 1 + offset];
        for (int idx : nums) {
            temp[idx + offset]++;
        }

        int idx = 0;
        for (int i = 0;i < temp.length;i++) {
            int count = temp[i];
            if (count == 0) continue;

            while (count > 0) {
                nums[idx++] = i - offset;
                count--;
            }
        }
    }

桶排序

将元素分割为大小想等的桶（桶之间也是有序的），对各桶内元素排序

public static void bucketSort(int[] nums, int size) {
        // find min max
        int max = 0;
        int min = 0;
        for (int num : nums) {
            max = Math.max(num, max);
            min = Math.min(num, min);
        }

        // init offset
        int offset = 0;
        if (min < 0) offset = Math.abs(min);

        // init buckets
        int len = (max + offset) / size + 1;
        List<List<Integer>> buckets = new ArrayList<>(len);
        for (int i = 0;i < len;i++) {
            buckets.add(new ArrayList<>());
        }

        // put num into buckets
        for (int num : nums) {
            buckets.get((num + offset) / size).add(num);
        }

        // sort
        int idx = 0;
        for (List<Integer> bucket : buckets) {
            bucket.sort(Integer::compareTo);
            for (Integer x : bucket) {
                nums[idx++] = x;
            }
        }
    }

基数排序

基于桶，由低位到高位进行排序，得到由高位到低位有序的数组

public static void radixSort(String[] nums) {
        List<List<String>> buckets = new ArrayList<>(128);
        for (int i = 0;i < 128;i++) {
            buckets.add(new ArrayList<>());
        }

        int len = nums[0].length() - 1;
        for (int i = len;i >= 0;i--) {
            for (String num : nums) {
                int idx = num.charAt(i) - '0';
                buckets.get(idx).add(num);
            }

            int idx = 0;
            for (List<String> bucket : buckets) {
                for (String num : bucket) {
                    nums[idx++] = num;
                }
                bucket.clear();
            }
        }
    }