算法学习：排序算法

一、算法分类

我们可以将排序算法分为比较类排序和非比较类排序。

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
  注：比如如果是java的话，可以调用系统自带的排序方法，传入一个Comparator函数。

• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
  注：一般只能用于整型相关的数据类型，并且一般需要辅助使用额外的内存空间。

  
  
  

二、初级排序-O(n^2)

1. 选择排序（Selection Sort）

每次找最小值，然后放到待排序数组的起始位置。

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

2. 插入排序（Insertion Sort）

从前到后逐步构建有序序列；对于未排序数据，在已排序序列中从后
向前扫描，找到相应位置并插入。

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int cur = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > cur) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = cur;
    }
}

3. 冒泡排序（Bubble Sort）

嵌套循环，每次查看相邻的元素如果逆序，则交换。

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

三、高级排序-O(n*Logn)

1. 快速排序（Quick Sort）

• 核心思想是分治：数组取标杆pivot，将小元素放pivot左边，大元素放右侧，然后依次对右边和右边的子数组继续快排；以达到整个序列有序。
• 关于基数选择有很多方式，而基数选择直接关系到快排的效率。
• 代码实现：

public static void quickSort(int[] array, int begin, int end) {
    if (end <= begin) return;
    int pivot = partition(array, begin, end);
    quickSort(array, begin, pivot - 1);
    quickSort(array, pivot + 1, end);
}

// 选取最后一个数为标杆，将比它小的数放到前面去，然后排列
static int partition(int[] a, int begin, int end) {
    int pivot = end, counter = begin;
    for (int i = begin; i < end; i++) {
        // pivot: 标杆位置，counter: ⼩于pivot的元素的个数
        if (a[i] < a[pivot]) {
            int temp = a[i];
            a[i] = a[counter];
            a[counter] = temp;
            counter++;
        }
    }
    int temp = a[pivot];
    a[pivot] = a[counter];
    a[counter] = temp;
    return counter;
}

2.归并排序（Merge Sort）

• 核心思想是分治；
• 排序过程：
  a. 把长度为n的输入序列分成两个长度为n/2的子序列；
  b. 对这两个子序列分别采用归并排序；
  c. 将两个排序好的子序列合并成一个最终的排序序列。
• 代码实现：

public static void mergeSort(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) >> 1;
    mergeSort(array, left, mid);
    mergeSort(array, mid + 1, right);
    merge(array, left, mid, right);
}

public static void merge(int[] array, int left, int mid, int right) {
    int[] arr = new int[right - left + 1];
    int i = 0, m = left, n = mid + 1;
    while (m <= mid && n <= right) {
        arr[i++] = array[m] < array[n] ? array[m++] : array[n++];
    }
    while (m <= mid) {
        arr[i++] = array[m++];
    }
    while (n <= right) {
        arr[i++] = array[n++];
    }
    System.arraycopy(arr, 0, array, left, right - left + 1);
}

3.堆排序（Heap Sort）

堆和堆排序比较复杂，会拎出来单独写一篇学习笔记；在算法题中遇到要使用堆排序时，如果是java，可以直接使用PriorityQueue优先队列。

四、特殊排序

1. 计数排序（Counting Sort）

计数排序要求输入的数据必须是有确定范围的整数。将输入的数据值转化为键存储在额外开辟的数组空间中；然后依次把计数大于 1 的填充回原数组。

基本思想

• 计数：
  遍历待排序的数组，统计每个元素出现的次数，并将统计结果存储在一个计数数组中。计数数组的索引对应着元素的值，而计数数组中的值表示该元素出现的次数。
  (这里可以统计最小值，用最小值+index来对应元素的值)
• 累积计数：
  对计数数组进行累积计数，即将每个元素的计数值加上前一个元素的计数值，得到每个元素在排序后数组中的位置。这一步确保相同元素的相对顺序不变。
• 排序：
  创建一个与待排序数组大小相同的结果数组，然后遍历待排序数组，根据元素的值在累积计数数组中找到其在结果数组中的位置，将元素放置在结果数组中的正确位置。

代码实现

public static void countingSort(int[] arr) {
    // 找出最大值、最小值
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    // 创建计数数组
    int[] countArray = new int[max - min + 1];
    // 统计数字出现的次数
    for (int i = 0; i < arr.length; i++) {
        countArray[arr[i] - min]++;
    }
    // 创建累计计数数组（用于表示该数存放到数组中的位置）
    int[] posArray = new int[max - min + 1];
    for (int i = 0; i < max - min + 1; i++) {
        if (i == 0) {
            posArray[i] = countArray[i];
        } else {
            posArray[i] = posArray[i - 1] + countArray[i];
        }
    }
    // 填充arr,完成排序
    for (int i = 0; i < max - min + 1; i++) {
        if (countArray[i] == 0) {
            continue;
        }
        int target = min + i;
        int start = i == 0 ? 0 : posArray[i - 1];
        int end = posArray[i];
        Arrays.fill(arr, start, end, target);
    }
}

2. 桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

image.png

3.基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。

五、算法实战

1122. 数组的相对排序

问题描述

给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

示例

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]

解题思路

思路1. 可以正常写一个简单的排序算法，然后将比较大小的地方换成一个compare方法；按照arr2写出compare方法即可。
思路2. 使用计数排序算法，按照题目中的排序规则即可。

代码示例

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int max = Arrays.stream(arr1).max().getAsInt();
        // 统计数量
        int[] countArr = new int[max + 1];
        for (int item : arr1) {
            countArr[item]++;
        }
        
        int[] rules = new int[max + 1];
        int pre = 0;
        // 先排arr2中的元素
        for (int item : arr2) {
            Arrays.fill(arr1, pre, pre + countArr[item], item);
            pre += countArr[item];
            rules[item] = 1;
        }
        // 再排arr2以外的元素
        for (int i = 0; i <= max; i++) {
            if (rules[i] == 1) {
                continue;
            }
            Arrays.fill(arr1, pre, pre + countArr[i], i);
            pre += countArr[i];
        }
        return arr1;
    }
}

---

242. 有效的字母异位词

问题描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
提示:

• 1 <= s.length, t.length <= 5 * 10^4
• s 和 t 仅包含小写字母

示例

输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

解题思路

类似计数排序，这里可以用点小技巧，只用一个数组解决问题：创建一个长度为26的数组，遍历第一个字符串的时候++，遍历第二个字符串的时候--；遍历完字符串之后，只需要检查有没有不为0的数即可。

代码示例

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] arr = new int[26];
        for (char item : s.toCharArray()) {
            arr[item - 'a']++;
        }
        for (char item : t.toCharArray()) {
            arr[item - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (arr[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

---

56. 合并区间

问题描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解题思路

先对区间数组进行排序，按照区间的左边界进行排序；然后依次合并即可。

代码示例

class Solution {
    public int[][] merge(int[][] intervals) {
        // 对区间的左边进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            // 没有重叠，直接添加
            if (res.size() == 0 || res.get(res.size() - 1)[1] < left) {
                res.add(new int[]{left, right});
            } else {
                // 有重叠部分，合并
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], right);
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}

---

493. 翻转对

问题描述

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例

输入: [1,3,2,3,1]
输出: 2

输入: [2,4,3,5,1]
输出: 3

解题思路

归并排序，nums[l..r] 中的翻转对数目，就等于两个子数组的翻转对数目之和，加上左半边的数在右半边的数组中达成条件的数量；每次合并结果的时候，还要合并这两个个有序数组，方便计算左半边的数在右半边的数组中达成条件的数量。

代码示例

class Solution {
    public static int reversePairs(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        return recursion(nums, 0, nums.length - 1);
    }

    public static int recursion(int[] nums, int left, int right) {
        if (left == right) {
            return 0;
        }

        int mid = (left + right) / 2;
        int leftCount = recursion(nums, left, mid);
        int rightCount = recursion(nums, mid + 1, right);
        // 左半边的数在右半边的数组中达成条件的数量(左右都是有序数组)
        int x = left, y = mid + 1, count = 0;
        while (x <= mid) {
            while (y <= right && (long) nums[x] > (long) 2 * nums[y]) {
                y++;
            }
            count += y - mid - 1;
            x++;
        }
        // 合并两个有序两个数组
        int[] temp = new int[right - left + 1];
        int index = 0, leftIndex = left, rightIndex = mid + 1;
        while (leftIndex <= mid || rightIndex <= right) {
            if (leftIndex > mid) {
                temp[index++] = nums[rightIndex++];
            } else if (rightIndex > right) {
                temp[index++] = nums[leftIndex++];
            } else {
                if (nums[leftIndex] < nums[rightIndex]) {
                    temp[index++] = nums[leftIndex++];
                } else {
                    temp[index++] = nums[rightIndex++];
                }
            }
        }
        System.arraycopy(temp, 0, nums, left, right - left + 1);

        return leftCount + rightCount + count;
    }
}