## 基数排序
`基数排序`（Radix Sort）属于`“分配式排序”`（distribution sort），又称“桶子法”（bucket sort），顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于`稳定`的排序，其时间复杂度为`O (nlog(r)m)`，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
### 基本思想
1. 先根据`个位数`的数值，在访问数值时将它们分配至编号0到9的桶子中
2. 将这些桶子中的数值按顺序重新串接起来，得到新的数列
3. 接着再根据`十位数`来分配，重新串接，获得新的数列，直到数列中`最高位数`完成上诉动作为止
### 算法实现
```java
package com.zys.sort;
/**
* @program: dataStructure
* @description: 基数排序
* @author: Leo
* @create: 2019-08-01 22:40
**/
public class RadixSort {
public static void radixSort(int[] arr) {
//所有桶
int[][] buckets = new int[10][arr.length];
//每个桶中有效元素的个数
int[] bucketCounts = new int[10];
//获取最大位数，先获取最大值
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
//最大值的长度即为最大位数
int maxLength = (max + "").length();
//共进行最大位数次 分配桶，回收数据
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//获取对应位数 ，第一次为个位，第二次为十位 ...
int value = arr[j] / n % 10;
//value的值就是这次分配桶的过程中当前元素应该放入的桶的索引（编号）
buckets[value][bucketCounts[value]++] = arr[j];
}
//遍历所有桶，按照顺序取出元素，放入原数组
int index = 0;
for (int k = 0; k < buckets.length; k++) {
//如果桶中有数据
if (bucketCounts[k] != 0) {
//遍历这个桶，取出所有数据放入原数组
for (int l = 0; l < bucketCounts[k]; l++) {
arr[index++] = buckets[k][l];
}
}
//每个桶处理过后，清空桶中有效数据个数
bucketCounts[k] = 0;
}
}
}
}
```
## 堆排序
`堆排序`（Heap Sort）是指利用`堆`这种数据结构所设计的一种排序算法。堆是一个`近似完全二叉树`的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
### 基本思想
1. 将无序序列调整成一个大顶推
2. 将堆顶元素与末尾元素交换，最大的元素就放在了数组末尾
3. 将剩余元素重新调整成大顶堆，继续与当前末尾元素交换，直到整个序列有序
### 算法实现
```java
package com.zys.sort;
/**
* @program: dataStructure
* @description: 堆排序
* @author: Leo
* @create: 2019-08-13 09:18
**/
public class HeapSort {
/**
* 堆排序思路：
* 1. 将无序序列调整成一个大顶推
* 2. 将堆顶元素与末尾元素交换，最大的元素就放在了数组末尾
* 3. 将剩余元素重新调整成大顶堆，继续与当前末尾元素交换，直到整个序列有序
*/
/**
* 堆排序（升序）
*
* @param arr 待排序数组
*/
public static void heapSort(int[] arr) {
//最后一个非叶子结点索引 = arr.length / 2 - 1
//1.将无序序列调整成一个大顶堆，从最后一个非叶子结点开始
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
for (int j = arr.length - 1; j >= 0; j--) {
//2. 将堆顶元素与末尾元素交换
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
//3. 将剩余元素重新调整成大顶堆，继续与当前末尾元素交换，直到整个序列有序
adjustHeap(arr, 0, j);
}
}
/**
* 将以i为根的子树调整成一个大顶堆
*
* @param arr 待排序数组
* @param i 非叶子结点索引
* @param length 调整中需要考虑的元素个数（每次调整并将堆顶元素交换至数组最后，length--）
*/
private static void adjustHeap(int[] arr, int i, int length) {
//先保存当前根结点的值
int currRoot = arr[i];
//j指向当前子树的根结点（i）的左子结点
for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {
//找出左右子节点中较大的数
if (j + 1 < length && arr[j + 1] > arr[j]) {
//指向当前根结点的右节点
j++;
}
//再将左右子节点中较大的数与当前根结点比较
//如果比当前根结点的值大
if (arr[j] > currRoot) {
//将较大的数赋给当前根结点坐在的位置
arr[i] = arr[j];
//将当前根结点指向与之交换的结点
i = j;
} else {
//退出循环
break;
}
}
//将当前根结点的值赋给之前与之交换的结点（i记录了索引）
arr[i] = currRoot;
}
}
```
## 简单测试（JUnit）
```java
package com.zys.test;
import com.zys.sort.*;
import org.junit.Before;
import org.junit.Test;
import java.util.Arrays;
/**
* @program: dataStructure
* @description: 排序测试类
* @author: Leo
* @create: 2019-05-23 20:42
**/
public class SortTest {
int[] arr;
@Before
public void generateUnSortedArray() {
arr = new int[]{5, 3, 7, 8, 1, 9, 4, 2, 6};
}
@Test
public void testRadixSort() {
// printArray(arr);
// RadixSort.radixSort(arr);
// printArray(arr);
//生成数组
generateRandomArray(8000000);
long startTime = System.currentTimeMillis();
RadixSort.radixSort(arr);
long endTime = System.currentTimeMillis();
System.out.println("基数排序花费时间：" + (endTime - startTime) + " ms");
}
@Test
public void testHeapSort() {
// System.out.println(Arrays.toString(arr));
// HeapSort.heapSort(arr);
// System.out.println(Arrays.toString(arr));
//生成数组
generateRandomArray(8000000);
long startTime = System.currentTimeMillis();
HeapSort.heapSort(arr);
long endTime = System.currentTimeMillis();
System.out.println("堆排序花费时间：" + (endTime - startTime) + " ms");
}
@Test
public void testCompare() {
//生成数组
generateRandomArray(8000000);
//复制一份
int[] arr2 = new int[arr.length];
System.arraycopy(arr, 0, arr2, 0, arr.length);
long startTime = System.currentTimeMillis();
RadixSort.radixSort(arr);
long endTime = System.currentTimeMillis();
System.out.println("基数排序花费时间：" + (endTime - startTime) + " ms");
startTime = System.currentTimeMillis();
HeapSort.heapSort(arr2);
endTime = System.currentTimeMillis();
System.out.println("堆排序花费时间：" + (endTime - startTime) + " ms");
}
/**
* 生成有n个元素的随机数组
*
* @param n 数组元素个数
*/
public void generateRandomArray(int n) {
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * n * 10);
}
}
private void printArray(int[] a) {
for (int x : a) {
System.out.print(x + " ");
}
System.out.println();
}
}
```
## 源码
[源码](https://github.com/leo1604270786/dataStructure)
