文章首发于：https://blog.silverbeats.cn/排序/

# 1. 插入排序

## 1.1 直接插入排序

直接插入排序，思想较为简单。

可以类比平常打扑克抓牌的过程。每次抓一张牌时，都会将这张牌与之前手里的牌（之前手里的牌是有序的）进行比较（从左向右比，或者从右向左比），得到一个最终的插入位置，然后插入。

```java
// 直接插入排序, 假定前面是有序的，从乱序的后面取一个数插入有序的前面
public void insertSort(int[] arr) {
 int len = arr.length;
 if (len == 0 || len == 1) return;
 // 进行插入排序
 for (int i = 1; i < len; i++) {
 for (int j = i; j > 0; j--) {
 if (arr[j] < arr[j - 1]) {
 swap(arr, j, j - 1);
 }
 }
 }
}
// 交换
private void swap(int[] arr, int a, int b) {
 int temp = arr[a];
 arr[a] = arr[b];
 arr[b] = temp;
}
```

上面的代码可以再简化一下：

```java
// 直接插入排序, 假定前面是有序的，从乱序的后面取一个数插入有序的前面
public void insertSort(int[] arr) {
 int len = arr.length;
 if (len == 0 || len == 1) return;
 // 进行插入排序
 for (int i = 1; i < len; i++) {
 for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
 	swap(arr, j, j - 1);
 }
}
```

## 1.2 折半插入排序

直接插入排序确定位置是通过将待排序的元素，与前面有序的序列一个个比较过去，从而得到最终的插入位置。那么，因为是顺序存储，利用数组实现排序，可以对前面的有序序列使用折半查找来确定最终插入位置。

```java
public void binaryInsertSort(int[] arr) {
 int len = arr.length;
 if (len == 0 || len == 1) return;
 // low high mid用于折半查找
 int low, high, mid;
 for (int i = 1; i < arr.length; i++) {
 low = 0;
 high = i - 1;
 while (low <= high) {
 // (high+low)/2 这样的写法可能会超出int的表示范围
 mid = low + ((high - low) >> 1);
 if (arr[mid] < arr[i])
 low = mid + 1;
 else
 high = mid - 1;
 }
 // high + 1就是插入的位置
 int temp = arr[i];
 // 找到插入位置后,对元素进行挪动
 for (int j = i - 1; j > high; j--)
 arr[j + 1] = arr[j];
 // 将待排序的元素插入找到的位置
 arr[high + 1] = temp;
 }
}
```

## 1.3 希尔排序

希尔排序又称为缩小增量排序，当增量为1时，其实就是直接插入排序。增量的选取一般两种方案：

- 希尔提出，对数组长度不断折半。比如数组长度是32，则增量dk分别是：16,8,4,2,1
- 帕佩尔诺夫和斯塔舍维奇提出，dk = 2^k^ + 1，dk < 数组长度，k ≥ 0。比如数组长度是32，此时k 只能从4开始，则k = 4，dk = 17；k = 3，dk = 9；k = 2，dk = 5；k = 1，dk = 3；此时还需要额外添加dk = 1，算是一个兜底作用。

```java
// 希尔排序
public int[] shellSort(int[] arr) {
  int len = arr.length;
  if (len == 0 || len == 1) return arr;
  int dk = len >> 1;
  while (dk != 0) {
    shell_InsertSort(arr, dk);
    // shell_BinaryInsertSort(arr, dk);
    dk = dk >> 1;
  }
  return arr;
}

/**
 * @Title: shell_InsertSort
 * @Description: 希尔排序，直接插入法进行排序
 * @param ar: 数组
 * @param dk: 间隔
 * @return: void
 */
private void shell_InsertSort(int[] arr, int dk) {
 int len = arr.length;
 int i, j;
 for (i = dk; i < len; i++) {
 int temp = arr[i];
 for (j = i - dk; j >= 0 && arr[j] > temp; j -= dk) {
 arr[j + dk] = arr[j];
 arr[j] = temp;
 }
 }
}
/**
 * @Title: shell_BinaryInsertSort
 * @Description: 希尔排序，折半插入法进行排序
 * @param arr: 数组
 * @param dk: 间隔
 * @return: void
 */
private void shell_BinaryInsertSort(int[] arr, int dk) {
 int i, j, high, low, mid, temp;
 for (i = dk; i < arr.length; i++) {
 low = i % dk;
 high = i - dk;
 while (low <= high) {
 mid = low + (high - low) / 2;
 if (arr[mid] < arr[i])
 low = mid + dk;
 else
 high = mid - dk;
 }
 temp = arr[i];
 // high + dk 即为插入的位置
 for (j = i - dk; j > high; j -= dk)
 arr[j + dk] = arr[j];
 arr[high + dk] = temp;
 }
}
```

> 后面那个通过折半插入法进行排序纯属练手，效率远远不及直接插入法希尔排序
>
> 前者，规模1W，20次，19ms
>
> 前者，规模10W，20次，187ms
>
> 后者，规模1W，20次，129ms
>
> 后者，规模10W，20次，10761ms
>
> 估计是在dk较小的时候，序列基本有序，折半插入的话是不管有没有序都得比较那么多次，而直接插入是越有序越快。

# 2. 选择排序

## 2.1 堆排序

堆又分大根堆和小根堆，倘若要升序，选择大根堆，倘若要降序，选择小根堆。

大根堆：根节点的数字不小于左右孩子的值

小根堆：根节点的值不大于左右孩子的值

堆排序是把一个数组，看做是一颗完全二叉树，排序步骤：

- 先对乱序的数组建立大根堆，可以得到数组的第一个元素（看做完全二叉树的话就是根节点）就是最大的
- 将其与数组最后面的那个值交换，然后重新调整，变为大根堆
- 依次类推

```java
// 堆排序
public void heapSort(int[] arr) {
 // 首先构建大根堆
 for(int pos = arr.length/2 - 1; pos >= 0; --pos) {
 //从第一个非叶子结点从下至上，从右至左调整结构
 adjustHeap(arr, pos, arr.length);
 }
 // 经过上一步可以得到大根堆,现在开始排序
 for(int j = arr.length - 1; j > 0; --j) {
 //将堆顶元素与末尾元素进行交换
 swap(arr,0, j);
 //重新对堆进行调整
 adjustHeap(arr,0, j);
 }
}
// 调整为大根堆
// arr是要调整的数组, i是要调整的数组下标, length是调整的范围
private void adjustHeap(int[] arr, int pos, int length) {
 // 临时存储被调整的数组数据
 int temp = arr[pos];
 // pos是被调整元素的数组下标, 2*pos+1 是其左孩子 2*pos + 2是其右孩子
 for(int i = pos*2 + 1; i < length; i = i*2 + 1) {
 /*
 前面的判断条件保证它的右孩子是无序的,
 在堆排序过程中会将最大值不断放到后面, length就是限制条件,可以通过这个条件让有序的右孩子不被波及
 这个if保证i的下标对应的值是两个孩子中最大的那一个
 */
 if(i + 1 < length && arr[i] < arr[i + 1]) {
 i++;
 }
 // 如果根节点小于它的孩子,则交换
 if(temp < arr[i]) {
 // 交换根节点和它孩子的值
 swap(arr, pos, i);
 // 因为经过了调整,当被调整的节点挪了位置,可能会导致后面的序列出问题,所以需要让pos定到i这个位置
 pos = i;
 } else {
 break;
 }
 }
}
```

## 2.2 简单选择排序

思路简单：每次选择最大排到后面，或者每次选择最小的排到最前面

```java
public void selectSort(int[] arr) {
 // 每次过滤一遍数组将最小值放到前面
 int i, j, min;
 for (i = 0; i < arr.length - 1; i++) {
 min = i; // 假定第i个位置最小
 for (j = i + 1; j < arr.length; j++) {
 if (arr[j] < arr[min])
 min = j;
 }
 if (i != min) swap(arr, i, min);
 }
}
```

下面是另外一种做法，是每次将最小的放到最前面，最大的放到最后面

```java
public void selectSort_2(int[] arr) {
 // 每次过滤一遍数组将最小值放到前面
 // 将最大的数字放到最后面
 int i, j, min, max, lastPos;
 for (i = 0; i <= arr.length >> 1; i++) {
 min = max = i;
 lastPos = arr.length - i - 1;
 for (j = i + 1; j <= lastPos; j++) {
 if (arr[j] < arr[min])
 min = j;
 if (arr[j] > arr[max])
 max = j;
 }
 if (i != min)
 swap(arr, i, min);
 if (lastPos != max)
 swap(arr, max, lastPos);
 }
}
```

> 前者，规模10W，20次，54408ms，2720ms/次
>
> 后者，规模10W，20次，53938ms，2697ms/次
>
> 呵呵……

简单选择排序有两个版本，一种是如同上面的两种写法一样，将最大值（最小值）与序列最后（第一）个进行调换位置，这个版本成为==交换版==

另一种版本是将最大值（最小值）插入到序列的最后（最前）面，成为插入版。

区别在于：

- 交换版不稳定，插入版稳定
- 倘若序列顺序存储，插入版会涉及到大批量的元素挪动，不如交换版来的划算
- 倘若序列是链式存储，插入版会划算一些

# 3. 交换排序

## 3.1 冒泡排序

冒泡排序很经典，每次排序都能讲最大的数字排到最后，或者将最小的数字排到最前面

> 听说冒泡是毒瘤，比较次数和交换次数超级多

```java
public int[] bubbleSort(int[] arr) {
 int len = arr.length;
 if (len == 0 || len == 1) return arr;
 for (int i = 0; i < len; i++) {
 // 倘若内循环没有进行交换,则整个序列有序,会直接终止整个排序,是一个优化的地方
 boolean flag = false;
 for (int j = 0; j < len - i - 1; j++) {
 if (arr[j] > arr[j + 1]) {
 swap(arr, j, j + 1);
 flag = true;
 }
 }
 if (!flag) break;
 }
 return arr;
}
```

继续发挥，双向冒泡

```java
// 双向冒泡
public void bubble2Ways(int[] arr) {
 int left = 0, right = arr.length - 1;
 boolean flag;
 while(left < right) {
 flag = false;
 // 从左往右将最大的数字挪到最右边
 for(int i = left; i < right; ++i) {
 if(arr[i] > arr[i + 1]){
 swap(arr, i, i + 1);
 flag = true;
 }
 }
 // 挪到结束后right--
 --right;
 // 从右往左将最小的数字挪到最左边
 for(int j = right; j > 0; --j) {
 if(arr[j] < arr[j - 1]){
 swap(arr, j, j - 1);
 flag = true;
 }
 }
 ++left;
 if(!flag)break;
 }
}
```

> 前者，规模1W，20次，1362ms，68ms/次
>
> 后者，规模1W，20次，1445ms，72ms/次
>
> 前者，规模10W，20次，303042ms，5min，15152ms/次
>
> 后者，规模10W，20次，202945ms，3min23s，10147ms/次
>
> ……还是有点提高的

## 3.2 快速排序

利用分而治之的思想。每一次快速排序会实现这样的结果：

- 该数字的左边都比它小
- 该数字的右边都不小于它
- 每一次排序都会确定一个数的最终位置

```java
// 快速排序
public void QSort(int[] arr, int low, int high) {
 if (low < high) {
 int piovtpos = this.QSort_Partition(arr, low, high);
 // 排左边
 QSort(arr, low, piovtpos - 1);
 // 排右边
 QSort(arr, piovtpos + 1, high);
 }
}
// 一趟快速排序
// 参数1：数组,参数2：数组的起始位置,参数3：数组的终了位置,闭区间
private int QSort_Partition(int[] arr, int left, int right) {
 // 指定基准
 int base = arr[left];
 while (left < right) {
 while (left < right && arr[right] >= base) right--;
 if (left < right) arr[left] = arr[right];
 while (left < right && arr[left] < base) left++;
 if (left < right) arr[right] = arr[left];
 }
 arr[left] = base;
 return left;
}
```

> 平均时间复杂度为nlogn的算法中，如：堆排序，快速排序，希尔排序，归并排序中，快速排序前面系数最小
>
> 规模1W，20次，15ms
>
> 规模10W，20次，359ms
>
> 快速排序有其特点：==越有序越慢，越无序越快==

# 4. 二路归并排序

```java
/**
 * @Title: mergeSort
 * @Description: 归并排序
 * @param arr: int类型数组
 * @return: void
 */
public void mergeSort(int[] arr, int leftStart, int rightBound) {
 if(leftStart == rightBound)return;
 if(leftStart > rightBound || leftStart < 0 || rightBound < 0)throw new RuntimeException("error");
 int mid = leftStart + ((rightBound - leftStart) >> 1);
 mergeSort(arr,leftStart,mid);
 mergeSort(arr,mid+1,rightBound);
 merge(arr, leftStart, mid+1, rightBound);
}

/**
 * @Title: merge
 * @Description:一次归并,将两个有序的数组合并，仍有序
 * @param arr 数组
 * @param leftStart 第一个数组的左边界开始的位置
 * @param rightStart 第二个数组的左边界开始的位置
 * @param rightBound 第二个数组的右边界结束的位置
 * @return: void
 */
private void merge(int[] arr, int leftStart, int rightStart, int rightBound) {
 // 合并思想：新建一个数组，每次将小的数字放到新建的数组中
 int i = leftStart, j = rightStart, k = 0;
 int[] tempArr = new int[rightBound - leftStart + 1];
 while(i < rightStart && j<= rightBound)
 tempArr[k++] = arr[i] <= arr[j]?arr[i++]:arr[j++];
 // 倘若还有剩余
 while(i < rightStart)
 tempArr[k++] = arr[i++];
 while(j <= rightBound)
 tempArr[k++] = arr[j++];
 // 此时tempArr就是合并好有序的数组，对原始数组进行覆盖
 for(int p = leftStart; p <= rightBound; p++)
 arr[p] = tempArr[p - leftStart];
 // 对原数组进行覆盖可以使用System.arraycopy,可以提高效率
 /*
 if (i < rightStart) {
 System.arraycopy(arr, i, tempArr, k, rightStart - i);
 k += (rightStart - i);
 }
 if (j <= rightBound) {
 System.arraycopy(arr, j, tempArr, k, rightBound - j + 1);
 }
 System.arraycopy(tempArr, 0, arr, leftStart, tempArr.length);
 */
}
```

> 规模1W，20次，32ms
>
> 规模10W，20次，241ms

# 5. 桶排序

## 5.1 基数排序

### 5.1.1 完整代码（只适用于非负数）

```java
// 基数排序
public void radixSort(int[] arr) {
 int len = arr.length;
 int arrMax = getMinMax(arr)[1];
 // 从个位开始,对数组进行排序
 // exp = 1, 按照个位
 // exp = 10, 按照十位
 // exp = 100, 按照百位
 for (int exp = 1; arrMax / exp > 0; exp *= 10) {
 int i;
 // 存储被排序数组的临时数组
 int[] output = new int[arr.length];
 // 桶,因为不管是什么数字,个数十位不管是哪一位,都是0-9，所以桶数组的长度是10
 int[] buckets = new int[10];
 // 将数据出现的次数进行统计
 for (i = 0; i < len; i++) {
 buckets[(arr[i] / exp) % 10]++;
 }
 // 转为累加数组。目的是让更改后的buckets[i]的值，是该数据在output中的位置
 for (i = 1; i < 10; i++) {
 buckets[i] += buckets[i - 1];
 }
 // 将数据存储到临时数组output中
 for (i = len - 1; i >= 0; i--) {
 output[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
 buckets[(arr[i] / exp) % 10]--;
 }
 // 将排序好的数组赋值给arr
 for (i = 0; i < len; i++)
 arr[i] = output[i];
 }
}
```

### 5.1.2 分段说明

==**分段说明举例说明的乱序数组为：{53, 3, 542, 748, 14, 214, 154, 63, 616}，为了更好的说明过程，for循环的说明将会以个位排序，演示整个过程**==

#### 5.1.2.1 外层循环

arrMax是整个数组中最大的数字，同时也是位数最多的那个数字，比如arrMax是748，那么需要进行3次循环，分别对整个数组的个位，十位，百位来进行排序，故，外层循环的次数是由arrMax的位数来决定的。

```java
for (int exp = 1; arrMax / exp > 0; exp *= 10) {
	……   
}
```

- exp  =  1，arrMax = 748/1  = 748> 0，对个位进行排序
- exp = 10，arrMax = 748/10  = 74 > 0，对十位进行排序
- exp = 100，arrMax = 748/100  = 8 > 0，对百位进行排序
- exp = 1000，arrMax = 748/1000  = 0 > 0，false，中止外层循环

#### 5.1.2.2 内部循环两个辅助数组的作用

首先，先来看一下，我们熟知的基数排序的过程：

![基数排序过程](http://resource.silverbeats.cn/static/images/算法/排序/基数排序过程.png)

很清楚能知道，其中一个辅助数组为buckets长度为10，即为上面的桶。但问题是，模拟的时候，是将每个数字放入桶中，然后取出的顺序是放入的先后顺序一致，颇有一种每个桶里面放的都是一个队列，先进先出，这样想倒是很符合，很自然，可以声明一个Object[]数组，之后每个位置存储一个队列，队列不需要自己实现，可以使用java.util包下的Queue实现类，之后操作就比较简单了，完全就和手动模拟的过程是一致的。（倘若用C语言，这样想能恶心死你= =）

但上面这种考虑虽然简单，但空间复杂度肯定是小不了的，这里给出的是另外一种比较巧妙的解决方案。可见后面更为详细的过程图。

```java
// 存储被排序数组的临时数组
int[] output = new int[arr.length];
// 桶,因为不管是什么数字,个数十位不管是哪一位,都是0-9，所以桶数组的长度是10
int[] buckets = new int[10];
```

#### 5.1.2.3 内部四for第一for: 将数据出现的次数进行统计

`(arr[i]/exp)%10`的目的是要获得目标位置的数字。

首先，将需要的那一位变为个位，比如214，想要取得十位1，此时的exp = 10，先要除exp，得到21，这样想要的十位数字1就挪到了个位，之后让21 % 10，即可得到想要的十位数字1

这里的for循环其实目的是统计每个数字的exp位（exp = 1 表示每个数字的个位，exp = 10 表示每个数字的十位……）出现的次数。

```java
for (i = 0; i < len; i++) {
 buckets[(arr[i] / exp) % 10]++;
}
```

**以个排序演示完整过程，出现次数：为待排序数组，每个数字的个位出现的次数**

#### 5.1.2.4 内部四for第二for: 转为累加数组

```java
// 转为累加数组。目的是让更改后的buckets[i]的值，是该数据在output中的位置
for (i = 1; i < 10; i++) {
 buckets[i] += buckets[i - 1];
}
```

这个累加数组中的值，就代表了每个数字最终应该存储的位置。比如53这个数字，当按照个位排完序，应该在哪里？

首先，我们应该能想到应该要遍历待排序数组，然后按照某种规则放入用来临时存储的output数组中。那么问题来了，应该正向遍历，还是逆向遍历？

假设是正向遍历，遍历到每个数字都需要考虑一些问题：

- 有多少个数字在我前面
- 和我拥有相同的个位，有多少个，还有多少个没有被安排进临时数组
- 比如，第一个数字53，首先，获取53的个位数字3，对应到buckets数组中发现buckets[3] = 4，说明最后一个个位为3的数字应该排在第四个。通过buckets[2] = 1，说明能排在个位3前面的数字只有1个，能推出，在最后的排序结果中，以3为个位的数字应该排在序列的第2,3,4位置。问题来了，如何确定到底是那个位置，同时还要保证相同个位的数字之间相对位置不变。

假设是逆序，它天然就能保证在最终结果序列中，相同个位之间相对顺序不变。比如063。

- buckets[3] = 4，让063排第4位，buckets[3] = 3
- buckets[3] = 3，让003排第3位，buckets[3] = 2
- buckets[2] = 2，让053排第2位，buckets[3] = 1

这个逻辑写起来就会很轻松。

#### 5.1.2.5 内部四for第三for: 将数据存储到临时数组output中

这里是整个排序中最不好懂的一部分。但是当你看到上面的说明，这里就会比较容易去理解。为了方便理解，将源代码中的两行代码拆分。

```java
 // 将数据存储到临时数组output中
for (i = len - 1; i >= 0; i--) {
  // 获取这个数字的exp位
  int pos = (arr[i] / exp) % 10;
  // 对应到buckets数组
  int b = buckets[pos];
  // 数组下标从0开始,需要减1,才是arr[i]应该存储的地方
  output[--b] = arr[i];
  // 让桶的数字自减
  buckets[pos]--;
  //output[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
  //buckets[(arr[i] / exp) % 10]--;
}
```

- 第1次：616，获取个位6，buckets[6] = 8，需要减1才是存放处，output[8 - 1] = 616，桶的数字减1，buckets[6] = 7

- 第2次：063，获取个位3，buckets[3] = 4，需要减1才是存放处，output[4 - 1] = 063，桶的数字减1，buckets[3] = 3

- 第3次：154，获取个位4，buckets[4] = 7，需要减1才是存放处，output[7 - 1] = 154，桶的数字减1，buckets[4] = 6

- 第4次：214，获取个位4，buckets[4] = 6，需要减1才是存放处，output[6 - 1] = 124，桶的数字减1，buckets[4] = 5

- 第5次：014，获取个位4，buckets[4] = 5，需要减1才是存放处，output[5 - 1] = 014，桶的数字减1，buckets[4] = 4

- 第6次：748，获取个位8，buckets[8] = 9，需要减1才是存放处，output[9 - 1] = 748，桶的数字减1，buckets[8] = 8

- 第7次：542，获取个位2，buckets[2] = 1，需要减1才是存放处，output[1 - 1] = 542，桶的数字减1，buckets[2] = 0

- 第8次：003，获取个位3，buckets[3] = 3，需要减1才是存放处，output[3 - 1] = 003，桶的数字减1，buckets[3] = 2

- 第9次：053，获取个位3，buckets[3] = 2，需要减1才是存放处，output[2 - 1] = 053，桶的数字减1，buckets[3] = 1

### 5.1.3 完整代码（适用于负数）

```java
public void radixSort(int[] arr) {
 int len = arr.length;
 if(len == 1 ||len == 0) return;
 int[] temp = getMinMax(arr);
 // 应该是位数最多的那一个
 int arrMax = Math.max(Math.abs(temp[0]), Math.abs(temp[1]));
 for (int exp = 1; arrMax / exp != 0; exp *= 10) {
 int i;
 // 存储被排序数组的临时数组
 int[] output = new int[len];
 // 桶,因为要考虑负数,桶编号从-9~9,，所以桶数组的长度是19
 int[] buckets = new int[19];
 // 将数据出现的次数进行统计,其中buckets数组下标0-8代表-9~-1,下标9代表0,10-18代表1-9
 for (i = 0; i < len; i++) {
 //获取这一位
 int bit = arr[i]/exp % 10;
 buckets[bit + 9]++;
 }
 // 转为累加数组。目的是让更改后的buckets[i]的值，是该数据在output中的位置
 for (i = 1; i < buckets.length; i++) {
 buckets[i] += buckets[i - 1];
 }
 // 将数据存储到临时数组output中
 for (i = len - 1; i >= 0; i--) {
 output[buckets[(arr[i] / exp) % 10 + 9] - 1] = arr[i];
 buckets[(arr[i] / exp) % 10 + 9]--;
 }
 // 将排序好的数组赋值给arr
 for (i = 0; i < len; i++)
 arr[i] = output[i];
 }
}
```

首先和上面不包含负数的基数排序相比，变动的地方如下：

- arrMax

```java
int[] temp = getMinMax(arr);
int arrMax = Math.max(Math.abs(temp[0]), Math.abs(temp[1]));
```

> 实际上，arrMax的意义其实没有变化，都指的是这一串数字当中位数最多的那个数字，至于是正的还是负的，这无所谓，只要它位数最多。
>
> 所以，倘若这串数字包含负数，在获取位数最多的那个数字，可以这样获取。
>
> 其中getMinMax是获取arr中的最小值和最大值，返回值{min，max}

- 桶数组大小变动

```java
int[] buckets = new int[19];
// 将数据出现的次数进行统计,其中buckets数组下标0-8代表-9~-1,下标9代表0,10-18代表1-9
for (i = 0; i < len; i++) {
 //获取这一位
 int bit = arr[i]/exp % 10;
 buckets[bit + 9]++;
}
……
// 将数据存储到临时数组output中
for (i = len - 1; i >= 0; i--) {
 output[buckets[(arr[i] / exp) % 10 + 9] - 1] = arr[i];
 buckets[(arr[i] / exp) % 10 + 9]--;
}
```

> 因为要考虑到负数，应该有：-9，-8，-7，-6，……，0，1，2，……，9共计19个桶
>
> 因为数组下标是从0开始的，所以在第一个计数的for循环，当在得到该数字的某一位时，需要+9
>
> 同时在第三个for循环，在获取某个桶的值的时候，也需要+9

## 5.2 计数排序

利用桶，空间换时间，在面对在一定范围内的大量重复数字的场景下，很适用。

比如一个省的高考成绩排名，可以声明一个长度为751的计数数组，其数组下标为0-750，代表每个分数。之后遍历整个省的所有人，统计每个分数的出现的次数，然后再遍历计数数组，即可实现有序。

```java
/**
 * @Title: countSort
 * @Description:计数排序,适用于数字的范围小，排序量大的数组
 * @param arr 数组
 * @param min 该数组中的最小值
 * @param max 该数组中的最大值
 * @return: int[]
 */
public void countSort(int[] arr, int min, int max) {
 // arr的最小值到最大值之间的数字，即为countArr的下标
 int[] countArr = new int[max - min + 1];
 // 统计arr中每个数字出现的次数
 for (int j = 0; j < arr.length; j++)
 countArr[arr[j] - min]++;
 int[] res = new int[arr.length];
 // 将countArr变为累加数组,这一步主要是实现算法稳定
 for (int m = 1; m < countArr.length; m++)
 countArr[m] += countArr[m - 1];
 // 这一步参见基数排序的过程示意图
 for(int k = arr.length - 1; k >= 0; k--)
 res[--countArr[arr[k] - min]] = arr[k];
 // 将排序好的数组赋值给arr
 for(int i = 0; i < arr.length; i++) {
 arr[i] = res[i];
 }
}
```

# 6. 排序比较

| 排序 | 英文 | 平均 | 最坏 | 最好 | 空间 | 稳定性 |
| -------- | --------- | ----------------- | ---- | ---- | ---- | ------ |
| 插入排序 | Insertion | n2 | n2 | n | 1 | 稳 |
| 折半插入 | | n2 | n2 | nlog2n | 1 | 稳 |
| 希尔排序 | Shell | n1.3 | n2 | n | 1 | 不稳 |
| 堆排序 | Heap | nlog2n | nlog2n | nlog2n | 1 | 不稳 |
| 选择排序 | Selection | n2 | n2 | n2 | 1 | 不稳 |
| 冒泡排序 | Bubble | n2 | n2 | n | 1 | 稳 |
| 快速排序 | Quick | nlog2n | n2 | nlog2n | log2n | 不稳 |
| 归并排序 | Merge | nlog2n | nlog2n | nlog2n | n | 稳 |
| 桶排序 | Bucket | n+k | n2 | n | n+k | 稳 |
| 计数排序 | Counting | n+k | n+k | n+k | n+k | 稳 |
| 基数排序 | Radix | n*k | n*k | n*k | n+k | 稳 |

- 经过一趟排序能够使某个关键字到达最终位置的排序：交换类排序（冒泡，快速排序）、选择类排序（简单选择，堆排序）
- 排序算法的关键字比较次数和原始序列无关：简单选择排序和折半插入排序
- 排序算法的排序趟数和原始序列有关：交换类排序（冒泡，快速排序）

十大内部排序

总共已有 0 条评论