SortAlgorithm
Sort Algorithm： CountSort、BucketSort、RadixSort、HeapSort
SortAlgorithm
七、CountSort
给定20个随机数，其范围为0~10，得到最大数max，则创建数组大小为11的一维数组，初始时数组中的元素均为0，遍历原数组，若第一个数为9，则数组下标为9的元素加1：依次遍历并修改数组。最后输出数组元素的下标值，元素的值是几，就输出几次
public static int[] countSort(int[] arr) {
//1.得到数列的最大值
int max = arr[0];
for(int i = 1; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
}
//2.根据数列最大值确定统计数组的长度
int[] countArray = new int[max + 1];
//3.遍历数列，填充统计数组
for(int i = 0; i < arr.length; i++) {
countArray[arr[i]]++;
}
//4.遍历统计数组，输出结果
int index = 0;
int[] sortedArray = new int[arr.length];
for(int i = 0; i < countArray.length; i++) {
for(int j = 0; j < countArray[i]; j++) {
sortedArray[index++] = i;
}
}
return sortedArray;
}
以上是以数列的最大值决定统计数组的长度，此方式可能会浪费大量的内存。（输入数列的最大值+1）
改进： 以数列最大值和最小值的差+1 作为统计数组的长度；同时数列的最小值作为一个偏移量，用于统计数组的对号入座。
例如： 95 94 91 98 99 90 93 91 92 99
统计数组长度： 99 -90 +1 = 10， 偏移量为90，对于95，对应的统计数组下标是95-90 = 5
稳定排序
public static int[] countSort(int[] arr) {
//1.得到数列的最大值和最小值，并算出差值d
int max = arr[0];
int min = arr[0];
for(int i = 1; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
if(arr[i] < min) {
min = arr[i];
}
}
int d = max - min;
//2.创建统计数组并统计对应元素的个数
int[] countArray = new int[d + 1];
for(int i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
//3.统计数组做变形，后面的元素等于前面的元素之和
/*
* 为了保证排序的稳定性，将统计数组从第二个元素开始，每一个元素都加上
* 前面所有元素之和。 这样相加，是让统计数组存储的元素值等于相应整数的最终排序位置。
*/
int sum = 0;
for(int i = 0; i < countArrya.length; i++) {
sum += countArray[i];
countArraay[i] = sum;
}
//4.倒序遍历统计数组，从统计数组找到正确位置
int[] sortedArray = new int[arr.length];
for(int i = arr.length - 1; i >= 0; i--) {
sortedArray[countArray[array[i] - min] - 1] = arr[i];
countArray[arr[i] - min]--;
}
return sortedArray;
}
八、BucketSort
每一个桶代表一个区间范围，里面可以承载一个或多个元素。
九、Radixsort
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或（binsort）
它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
基数排序是属于稳定性的排序，效率高
基数排序是桶排序的扩展，速度很快
基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成 OutOfMemoryError
基数排序是1887年赫尔曼·何乐礼发明的。
实现：将整数按位数切割成不同的数字，然后按每个位数分别比较（按位数比较的排序方法）
思路：
将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
时间复杂度：O(k(n+m))
空间复杂度：O(n+m)
// 基数排序（该代码不能对负数进行排序）
public static void radixSort(int[] arr) {
// 得到数组中最大的数的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 得到最大的数是几位数
int maxLength = (max + "").length();
// 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
// 每个桶中存放对应的数据，大小为 arr.length
int[][] bucket = new int[10][arr.length];
// 记录每个桶中实际存放数据的个数，用一维数组来记录
int[] bucketElementCounts = new int[10];
// 需要进行maxLength 次的排序,每次排序根据对应的位数决定如何存放数据
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
//得到每个元素的个位(十位、百位)的值
// int digitOfElement = arr[j] / n % 10;
int digitOfElement = arr[j] / n % 10;
//放入到对应的桶中,bucketElementCounts[digitOfElement]表示第几个桶
bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
bucketElementCounts[digitOfElement]++;
}
// 按照桶的顺序，依次将数据放入原数组
int index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
//判断通知是否有数据
if (bucketElementCounts[k] != 0) {
for (int l = 0; l < bucketElementCounts[k]; l++) {
arr[index++] = bucket[k][l];
}
}
// 在一轮排序结束后，需将bucketElementCounts[k] = 0
bucketElementCounts[k] = 0;
}
System.out.println(Arrays.toString(arr));
}
}
十、HeapSort
1）堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最好、最坏、平均
时间复杂度均为O(nlogn)，是不稳定排序
2）堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；
（对节点的左孩子的值和右孩子的值的大小关系没有要求）
每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆
3）大顶堆：
大顶堆特点： arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2] //i对应第几个节点，i从0开始编号
4）小顶堆：
小顶堆特点：arr[i] <= arr[2i + 1] &&arr[i] <= arr[2i + 2] //i对应第几个节点，i从0开始编号
5）一般升序采用大顶堆，降序采用小顶堆
堆排序的基本思想：
1）将待排序序列构造成一个大顶堆
2）此时，整个序列的最大值就是堆顶的根节点
3）将其与末尾元素进行交换，此时末尾即为最大值
4）将剩余的n-1个数再构造成大顶堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列。
i索引
1.父结点索引：(i-1)/2（这里计算机中的除以2，省略掉小数）
2.左孩子索引：2*i+1
3.右孩子索引：2*i+2
最后一个非叶子节点的索引 i= arr.length/2-1
分析： 实现堆排序，主要完成两个步骤：1）将arr数组（二叉树）先进行调整成大顶堆 2）取出堆顶与最后一个节点交换，将arr.length-1个数据继续调整为大顶堆 因为初始数组是普通的二叉树，将其调整为大顶堆只能是从下往上最后一个非子结点开始，逐步调整为子大顶堆。 最后一个非叶子节点的索引为arr.length / 2 - 1（即非叶子节点的个数），从下往上进行调整，直到索引为0 public static void adjustHeap(int[] arr, int i, int length)方法将一个二叉树调整为大顶堆，其中的i表示的是将以i索引 位置为堆顶进行的大顶堆转换，因此从最后一个非叶子节点开始，每调用一次该方法就得到一个大顶堆，直到索引为0整个 二叉树调整为了大顶堆。【此时进行堆顶元素的交换时，排好的二叉树只调用一次该方法即可达到大顶堆的调整】 然后将堆顶元素与arr数组最后一个位置进行交换，剩余arr.length继续进行大顶堆调整，反复进行，直到全部序列排好。
package tree;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
// 升序排列
int[] arr = {4, 6, 8, 5, 9};
heapSort(arr);
}
//堆排序
public static void heapSort(int[] arr) {
int temp = 0;
//将无序序列构建成一个堆，根据升序降序选择大顶堆或小顶堆
for (int i = arr.length / 2 -1; i >= 0 ; i--) {
adjustHeap(arr, i, arr.length);
}
// 将堆顶元素与末尾元素交换，将最大元素沉到数组末端
// 重新调整结构，使其满足堆定义，然后继续交换堆顶元素和当前末端元素，直到整个序列有序
for (int j = arr.length - 1; j > 0; j--) {
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0 ,j);
}
System.out.println(Arrays.toString(arr));
}
//将一个数组（二叉树）调整成一个大顶堆
/**
*
* @param arr 待调整的数组
* @param i 表示非叶子节点在数组中的索引
* @param length 对多少个元素继续调整 ， length在逐渐减少
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i]; //将当前元素保存在临时遍历
// k = i * 2 + 1 k表示i节点的左子节点
//以i为索引位置向下进行大顶堆的调整
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) { // 若左子节点的值小于右子节点的值
k++; // k 指向右子节点
}
if (arr[k] > temp) { //如果子节点大于父节点
arr[i] = arr[k]; // 把较大的值赋给当前节点
i = k; // i指向k 继续循环比较
} else {
break;
}
}
arr[i] = temp;
}
}