文章目录
- 前言
- 一、选择排序
- 1. 原理讲解
- 2. 代码示例
- 3. 总结
- 二、插入排序
- 1.原理讲解
- 2.代码示例
- 3. 总结
- 三、归并排序
- 1. 原理讲解
- 2. 代码示例
- 3. 总结
- 四、快速排序
- 1. 原理讲解
- 2. 代码示例
- 五、堆排序
- 1. 原理讲解
- 2. 代码示例
- 六、希尔排序
- 1. 原理讲解
- 2. 代码示例
- 七、冒泡排序
- 1. 原理讲解
- 2. 代码示例
- 八、计数排序
- 1. 原理讲解
- 2. 代码示例
- 九、基数排序
- 1. 原理讲解
- 2. 代码示例
- 十、桶排序
- 1. 原理讲解
- 2. 代码示例
前言
排序方法： 选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序、冒泡排序、计数排序、基数排序、桶排序。
重点掌握： 插入排序、归并排序、快速排序、堆排序。
部分内容转载于：912.排序数组精选题解
一、选择排序
1. 原理讲解
重复“使用线性查找从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”。即：先选出最小的，再选出第 2 小的，放到开头，以此类推。
- 总比较次数： n 2 2 \frac{n^{2}}{2} 2n2
- 时间复杂度： O ( n 2 ) O(n^{2}) O(n2)
- 空间复杂度： O ( 1 ) O(1) O(1)
2. 代码示例
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for(int i = 0; i < len - 1; i++) {
int minIndex = i;
for(int j = i + 1; j < len; j++) {
if(nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums, i, minIndex);
}
return nums;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
3. 总结
- 算法思想 1：贪心算法：每一次决策只看当前，当前最优，则全局最优。注意：这种思想不是任何时候都适用。
- 算法思想 2：减治思想：外层循环每一次都能排定一个元素，问题的规模逐渐减少，直到全部解决，即大而化小，小而化了。运用减治思想很典型的算法就是二分查找。
- 优点：交换次数最少。
二、插入排序
1.原理讲解
插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧未排序的区域内选取出一个数据，然后将它插入到已排序区域内合适的位置上。
- 时间复杂度： O ( n 2 ) O(n^{2}) O(n2)
- 空间复杂度： O ( 1 ) O(1) O(1)
2.代码示例
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
// 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
for(int i = 0; i < len; i++) {
// 先暂存这个元素，然后之前元素逐个后移，留出空位
int temp = nums[i];
int j = i;
while(j > 0 && nums[j - 1] > temp) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = temp;
}
return nums;
}
}
3. 总结
- 由于插入排序在几乎有序的数组上表现良好，特别地，在短数组上的表现也很好。因为短数组的特点是：每个元素离它最终排定的位置都不会太远。为此，在小区间内执行排序任务的时候，可以转向使用插入排序。
三、归并排序
1. 原理讲解
归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并是指把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有的子序列都归并为一个整体为止。即：借助额外空间，合并两个有序数组，得到更长的有序数组。
- 时间复杂度： O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))
- 空间复杂度： O ( n ) O(n) O(n)
2. 代码示例
class Solution {
int[] tmp;
public int[] sortArray(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) >> 1;
// 递归调用函数 mergeSort(nums, l, mid) 对 nums 数组里 [l,mid] 部分进行排序。
mergeSort(nums, l, mid);
// 递归调用函数 mergeSort(nums, mid + 1, r) 对 nums 数组里 [mid+1,r] 部分进行排序。
mergeSort(nums, mid + 1, r);
int i = l, j = mid + 1;
int cnt = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[cnt++] = nums[i++];
} else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {
tmp[cnt++] = nums[i++];
}
while (j <= r) {
tmp[cnt++] = nums[j++];
}
for (int k = 0; k < r - l + 1; ++k) {
nums[k + l] = tmp[k];
}
}
}
3. 总结
- 归并排序比快速排序好的一点是，它借助了额外空间，可以实现稳定排序。
四、快速排序
1. 原理讲解
快速排序首先在序列中随机选择一个基准值，然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”两个类别，即：[比基准值小的数] 基准值 [比基准值大的数]，接着对两个[]中的数进行排序之后，整体的排序就完成了。
- 时间复杂度： O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))
- 空间复杂度： O ( n ) O(n) O(n)
2. 代码示例
class Solution {
public int[] sortArray(int[] nums) {
randomizedQuicksort(nums, 0, nums.length - 1);
return nums;
}
// 对 nums 数组里 [l,r] 的部分进行排序
public void randomizedQuicksort(int[] nums, int l, int r) {
if (l < r) {
int pos = randomizedPartition(nums, l, r);
randomizedQuicksort(nums, l, pos - 1);
randomizedQuicksort(nums, pos + 1, r);
}
}
// 函数对 nums 数组里 [l,r] 的部分进行划分，并返回分界值的下标 pos
public int randomizedPartition(int[] nums, int l, int r) {
int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
swap(nums, r, i);
return partition(nums, l, r);
}
public int partition(int[] nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
五、堆排序
1. 原理讲解
堆是一种图的树形结构，被用于实现优先队列。优先队列是一种数据结构，可以自由添加数据，但取出数据时要从最小值开始按照顺序取出。
- 时间复杂度： O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))
- 空间复杂度： O ( 1 ) O(1) O(1)
2. 代码示例
public class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
// 将数组整理成堆
heapify(nums);
// 循环不变量：区间 [0, i] 堆有序
for (int i = len - 1; i >= 1; ) {
// 把堆顶元素（当前最大）交换到数组末尾
swap(nums, 0, i);
// 逐步减少堆有序的部分
i--;
// 下标 0 位置下沉操作，使得区间 [0, i] 堆有序
siftDown(nums, 0, i);
}
return nums;
}
/**
* 将数组整理成堆（堆有序）
*
* @param nums
*/
private void heapify(int[] nums) {
int len = nums.length;
// 只需要从 i = (len - 1) / 2 这个位置开始逐层下移
for (int i = (len - 1) / 2; i >= 0; i--) {
siftDown(nums, i, len - 1);
}
}
/**
* @param nums
* @param k 当前下沉元素的下标
* @param end [0, end] 是 nums 的有效部分
*/
private void siftDown(int[] nums, int k, int end) {
while (2 * k + 1 <= end) {
int j = 2 * k + 1;
if (j + 1 <= end && nums[j + 1] > nums[j]) {
j++;
}
if (nums[j] > nums[k]) {
swap(nums, j, k);
} else {
break;
}
k = j;
}
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
六、希尔排序
1. 原理讲解
思想来源：插入排序的优化。在插入排序里，如果靠后的数字较小，它来到前面就得交换多次。「希尔排序」改进了这种做法。带间隔地使用插入排序，直到最后「间隔」为 1 的时候，就是标准的「插入排序」，此时数组里的元素已经「几乎有序」了；希尔排序的「间隔序列」其实是一个超参数。
2. 代码示例
public class Solution {
// 希尔排序
public int[] sortArray(int[] nums) {
int len = nums.length;
int h = 1;
// 使用 Knuth 增量序列
// 找增量的最大值
while (3 * h + 1 < len) {
h = 3 * h + 1;
}
while (h >= 1) {
// insertion sort
for (int i = h; i < len; i++) {
insertionForDelta(nums, h, i);
}
h = h / 3;
}
return nums;
}
/**
* 将 nums[i] 插入到对应分组的正确位置上，其实就是将原来 1 的部分改成 gap
*
* @param nums
* @param gap
* @param i
*/
private void insertionForDelta(int[] nums, int gap, int i) {
int temp = nums[i];
int j = i;
// 注意：这里 j >= deta 的原因
while (j >= gap && nums[j - gap] > temp) {
nums[j] = nums[j - gap];
j -= gap;
}
nums[j] = temp;
}
}
七、冒泡排序
1. 原理讲解
冒泡排序是重复“从序列右边开始比较相邻两个数字的大小，再根据结果交换两个数字的位置”。
- 时间复杂度： O ( n 2 ) O(n^{2}) O(n2)
- 空间复杂度： O ( 1 ) O(1) O(1)
2. 代码示例
public class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
for (int i = len - 1; i >= 0; i--) {
// 先默认数组是有序的，只要发生一次交换，就必须进行下一轮比较，
// 如果在内层循环中，都没有执行一次交换操作，说明此时数组已经是升序数组
boolean sorted = true;
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
sorted = false;
}
}
if (sorted) {
break;
}
}
return nums;
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
八、计数排序
1. 原理讲解
「计数排序」是把每个出现的数值都做一个计数，然后根据计数从小到大输出得到有序数组。
这种做法丢失了稳定性，如果是本题这种基本数据类型的话没有关系。如果是对象类型，就不能这么做了。
保持稳定性的做法是：先对计数数组做前缀和，在第 2 步往回赋值的时候，根据原始输入数组的数据从后向前赋值，前缀和数组保存了每个元素存放的下标信息。
2. 代码示例
public class Solution {
// 计数排序
private static final int OFFSET = 50000;
public int[] sortArray(int[] nums) {
int len = nums.length;
// 由于 -50000 <= A[i] <= 50000
// 因此"桶" 的大小为 50000 - (-50000) = 10_0000
// 并且设置偏移 OFFSET = 50000，目的是让每一个数都能够大于等于 0
// 这样就可以作为 count 数组的下标，查询这个数的计数
int size = 10_0000;
// 计数数组
int[] count = new int[size];
// 计算计数数组
for (int num : nums) {
count[num + OFFSET]++;
}
// 把 count 数组变成前缀和数组
for (int i = 1; i < size; i++) {
count[i] += count[i - 1];
}
// 先把原始数组赋值到一个临时数组里，然后回写数据
int[] temp = new int[len];
System.arraycopy(nums, 0, temp, 0, len);
// 为了保证稳定性，从后向前赋值
for (int i = len - 1; i >= 0; i--) {
int index = count[temp[i] + OFFSET] - 1;
nums[index] = temp[i];
count[temp[i] + OFFSET]--;
}
return nums;
}
}
九、基数排序
1. 原理讲解
基本思路：也称为基于关键字的排序，例如针对数值排序，个位、十位、百位就是关键字。针对日期数据的排序：年、月、日、时、分、秒就是关键字。
「基数排序」用到了「计数排序」。
2. 代码示例
public class Solution {
// 基数排序：低位优先
private static final int OFFSET = 50000;
public int[] sortArray(int[] nums) {
int len = nums.length;
// 预处理，让所有的数都大于等于 0，这样才可以使用基数排序
for (int i = 0; i < len; i++) {
nums[i] += OFFSET;
}
// 第 1 步：找出最大的数字
int max = nums[0];
for (int num : nums) {
if (num > max) {
max = num;
}
}
// 第 2 步：计算出最大的数字有几位，这个数值决定了我们要将整个数组看几遍
int maxLen = getMaxLen(max);
// 计数排序需要使用的计数数组和临时数组
int[] count = new int[10];
int[] temp = new int[len];
// 表征关键字的量：除数
// 1 表示按照个位关键字排序
// 10 表示按照十位关键字排序
// 100 表示按照百位关键字排序
// 1000 表示按照千位关键字排序
int divisor = 1;
// 有几位数，外层循环就得执行几次
for (int i = 0; i < maxLen; i++) {
// 每一步都使用计数排序，保证排序结果是稳定的
// 这一步需要额外空间保存结果集，因此把结果保存在 temp 中
countingSort(nums, temp, divisor, len, count);
// 交换 nums 和 temp 的引用，下一轮还是按照 nums 做计数排序
int[] t = nums;
nums = temp;
temp = t;
// divisor 自增，表示采用低位优先的基数排序
divisor *= 10;
}
int[] res = new int[len];
for (int i = 0; i < len; i++) {
res[i] = nums[i] - OFFSET;
}
return res;
}
private void countingSort(int[] nums, int[] res, int divisor, int len, int[] count) {
// 1、计算计数数组
for (int i = 0; i < len; i++) {
// 计算数位上的数是几，先取个位，再十位、百位
int remainder = (nums[i] / divisor) % 10;
count[remainder]++;
}
// 2、变成前缀和数组
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 3、从后向前赋值
for (int i = len - 1; i >= 0; i--) {
int remainder = (nums[i] / divisor) % 10;
int index = count[remainder] - 1;
res[index] = nums[i];
count[remainder]--;
}
// 4、count 数组需要设置为 0 ，以免干扰下一次排序使用
for (int i = 0; i < 10; i++) {
count[i] = 0;
}
}
/**
* 获取一个整数的最大位数
*
* @param num
* @return
*/
private int getMaxLen(int num) {
int maxLen = 0;
while (num > 0) {
num /= 10;
maxLen++;
}
return maxLen;
}
}
十、桶排序
1. 原理讲解
基本思路：一个坑一个萝卜，也可以一个坑多个萝卜，对每个坑排序，再拿出来，整体就有序。
2. 代码示例
public class Solution {
// 桶排序
// 1 <= A.length <= 10000
// -50000 <= A[i] <= 50000
// 10_0000
private static final int OFFSET = 50000;
public int[] sortArray(int[] nums) {
int len = nums.length;
// 第 1 步：将数据转换为 [0, 10_0000] 区间里的数
for (int i = 0; i < len; i++) {
nums[i] += OFFSET;
}
// 第 2 步：观察数据，设置桶的个数
// 步长：步长如果设置成 10 会超出内存限制
int step = 1000;
// 桶的个数
int bucketLen = 10_0000 / step;
int[][] temp = new int[bucketLen + 1][len];
int[] next = new int[bucketLen + 1];
// 第 3 步：分桶
for (int num : nums) {
int bucketIndex = num / step;
temp[bucketIndex][next[bucketIndex]] = num;
next[bucketIndex]++;
}
// 第 4 步：对于每个桶执行插入排序
for (int i = 0; i < bucketLen + 1; i++) {
insertionSort(temp[i], next[i] - 1);
}
// 第 5 步：从桶里依次取出来
int[] res = new int[len];
int index = 0;
for (int i = 0; i < bucketLen + 1; i++) {
int curLen = next[i];
for (int j = 0; j < curLen; j++) {
res[index] = temp[i][j] - OFFSET;
index++;
}
}
return res;
}
private void insertionSort(int[] arr, int endIndex) {
for (int i = 1; i <= endIndex; i++) {
int temp = arr[i];
int j = i;
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
}
![[Linux_IMX6ULL驱动开发]-总线设备驱动模型](https://img-blog.csdnimg.cn/direct/1266dc6d183747b497ba96029848f5c3.png)
