排序笔记
2020-06-28 本文已影响0人
ShihChieh_Ma
/**
* @author: shihchieh.ma
* @create: 2020/6/15 6:13 下午
* @email: shihchieh.ma@gail.com
* @description:
*/
public class Sort {
public static final int[] INTS = {
// 24, 352, 23, 4, 1, 421, 5, 6, 436, 7, 86, 97, 9, 74, 34, 234, 1, 3, 6, 7
10, 8, 6, 4, 2
};
/**
* @param n 生成n个元素的随机数组
* @param rangeL 随机范围[rangeL
* @param rangeR rangeR]
* @return 返回一个随机 int 型数组
*/
public static int[] gennerateArray(int n, int rangeL, int rangeR) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * (rangeR - rangeL + 1)) + rangeL;
}
return arr;
}
public static void main(String[] args) {
// int[] INTS = gennerateArray(1000, 10);
long startTime, endTime;
// 冒泡排序
int[] bubbleArr = INTS.clone();
startTime = System.currentTimeMillis();
bubbleSort(bubbleArr);
endTime = System.currentTimeMillis();
printArray("冒泡排序:", bubbleArr, endTime - startTime);
// 选择排序
int[] selectionArr = INTS.clone();
startTime = System.currentTimeMillis();
selectionSort(selectionArr);
endTime = System.currentTimeMillis();
printArray("选择排序:", selectionArr, endTime - startTime);
// 插入排序
int[] insertArr = INTS.clone();
startTime = System.currentTimeMillis();
insertSort(insertArr);
endTime = System.currentTimeMillis();
printArray("插入排序:", insertArr, endTime - startTime);
// 快速排序
int[] quickArr = INTS.clone();
startTime = System.currentTimeMillis();
quickSort(quickArr, 0, quickArr.length - 1);
endTime = System.currentTimeMillis();
printArray("快速排序:", quickArr, endTime - startTime);
// 计数排序
int[] countArr = INTS.clone();
startTime = System.currentTimeMillis();
int[] countSort = countSort(countArr);
endTime = System.currentTimeMillis();
printArray("计数排序:", countSort, endTime - startTime);
// 基数排序
int[] radixArr = INTS.clone();
startTime = System.currentTimeMillis();
radixSort(radixArr);
endTime = System.currentTimeMillis();
printArray("基数排序:", radixArr, endTime - startTime);
// 桶排序
int[] bucketArr = INTS.clone();
startTime = System.currentTimeMillis();
int[] bucketSort = bucketSort(bucketArr);
endTime = System.currentTimeMillis();
printArray("桶排序:", bucketSort, endTime - startTime);
// 归并排序
int[] mergeArr = INTS.clone();
startTime = System.currentTimeMillis();
mergeSort(mergeArr, 0, mergeArr.length - 1, new int[mergeArr.length]);
endTime = System.currentTimeMillis();
printArray("归并排序:", mergeArr, endTime - startTime);
// 希尔排序
int[] shellArr = INTS.clone();
startTime = System.currentTimeMillis();
shellSort(shellArr);
endTime = System.currentTimeMillis();
printArray("希尔排序:", shellArr, endTime - startTime);
// 堆排序
int[] heapArr = INTS.clone();
startTime = System.currentTimeMillis();
heapSort(heapArr);
endTime = System.currentTimeMillis();
printArray("堆排序:", heapArr, endTime - startTime);
}
private static void printArray(String name, int[] ints, long time) {
for (int anInt : ints) {
System.out.print("_" + anInt + "_");
}
System.out.println("\t");
System.out.println(name + "耗时:" + time);
System.out.println();
}
}
冒泡排序
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
/** 冒泡排序 */
private static void bubbleSort(int[] clone) {
for (int i = 0, j = clone.length; i < j; i++) {
for (int k = 0, l = j - 1 - i; k < l; k++) {
if (clone[k] > clone[k + 1]) {
clone[k] = clone[k] ^ clone[k + 1];
clone[k + 1] = clone[k] ^ clone[k + 1];
clone[k] = clone[k] ^ clone[k + 1];
}
}
}
}
选择排序
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
- 以此类推，直到所有元素均排序完毕
/** 选择排序 */
private static void selectionSort(int[] clone) {
for (int i = 0, j = clone.length; i < j; i++) {
int minIndex = i;
for (int k = i; k < j; k++) {
if (clone[k] < clone[minIndex]) {
minIndex = k;
}
}
if (minIndex != i) {
clone[i] = clone[i] + clone[minIndex];
clone[minIndex] = clone[i] - clone[minIndex];
clone[i] = clone[i] - clone[minIndex];
}
}
}
插入排序
- 第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤 2->5
/** 插入排序 */
private static void insertSort(int[] clone) {
for (int i = 1, j = clone.length; i < j; i++) {
int k = i;
int temp = clone[k];
while (k > 0 && clone[k - 1] > temp) {
clone[k] = clone[k - 1];
k--;
}
clone[k] = temp;
}
}
快速排序
- 选取第一个数为基准
- 将比基准小的数交换到前面，比基准大的数交换到后面
- 对左右区间重复第二步，直到各区间只有一个数
/**
* 快速排序
*
* @param clone 数组
* @param leftIndex 左边角标 初始0
* @param rightIndex 右边角标 初始length-1
*/
private static void quickSort(int[] clone, int leftIndex, int rightIndex) {
// temp-基准位
int i, j, temp;
if (leftIndex > rightIndex) {
return;
}
i = leftIndex;
j = rightIndex;
temp = clone[leftIndex];
while (i < j) {
// 先右边，往左递减,找一个小于基准位的数
// 当右边的角标位置所在的数>基准位的数时，继续从右往左找（同时 j 索引-1)
// 找到就跳出 while循环
while (temp <= clone[j] && i < j) {
j--;
}
// 再左边，往右递增
// 如上
while (temp >= clone[i] && i < j) {
i++;
}
// 满足条件则交换
if (i < j) {
clone[i] = clone[i] + clone[j];
clone[j] = clone[i] - clone[j];
clone[i] = clone[i] - clone[j];
}
}
// i=j 左右在同一位置
// 最后将基准为与i和j相等位置的数字交换
clone[leftIndex] = clone[i];
clone[i] = temp;
// 左半数组<(i或j所在索引的数)<右半数组
// 也就是说(i或j所在索引的数)已经确定排序位置，就不用再排序了，
// 相同的方法分别处理左右数组
// 递归调用左半数组
quickSort(clone, leftIndex, j - 1);
// 递归调用右半数组
quickSort(clone, j + 1, rightIndex);
}
计数排序
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
- 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
- 向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；
当数组最大和最小差值过大时，不适合计数排序
当数组元素不是整数时，不适合用计数排序
/** 计数排序 */
private static int[] countSort(int[] clone) {
int max = clone[0];
int min = clone[0];
for (int i = 1, j = clone.length; i < j; i++) {
if (clone[i] > max) {
max = clone[i];
}
if (clone[i] < min) {
min = clone[i];
}
}
int dValue = max - min;
int[] countArray = new int[dValue + 1];
for (int value : clone) {
countArray[value - min]++;
}
// 统计数组做变形，后边的元素等于前面的元素之和
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
// 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
int[] sortedArray = new int[clone.length];
for (int i = clone.length - 1; i >= 0; i--) {
// 给sortedArray的当前位置赋值
sortedArray[countArray[clone[i] - min] - 1] = clone[i];
// 给countArray的位置的值--
countArray[clone[i] - min]--;
}
return sortedArray;
}
基数排序
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序
/** 基数排序 */
private static void radixSort(int[] clone) {
int maxLength = 0;
// 最大位数
for (int i : clone) {
int length = String.valueOf(i).length();
maxLength = Math.max(length, maxLength);
}
List<List<Integer>> list =
new ArrayList<List<Integer>>() {
{
// 0-9
for (int i = 0; i < 10; i++) {
add(new ArrayList<>());
}
}
};
for (int i = 0, temp = 1; i < maxLength; temp *= 10, i++) {
for (int value : clone) {
list.get((value / temp) % 10).add(value);
}
for (int j = 0, k = 0, l = list.size(); j < l; j++) {
while (!list.get(j).isEmpty()) {
clone[k] = list.get(j).get(0);
list.get(j).remove(0);
k++;
}
}
}
}
桶排序
- 设置一个定量的数组当作空桶子。
- 寻访序列，并且把项目一个一个放到对应的桶子去。
- 对每个不是空的桶子进行排序。
- 从不是空的桶子里把项目再放回原来的序列中。
/** 桶排序 */
private static int[] bucketSort(int[] clone) {
int maxLength = 0, minLength = 0;
// 最大位数and最小位数
for (int i = 0, j = clone.length; i < j; i++) {
int length = String.valueOf(clone[i]).length();
maxLength = Math.max(length, maxLength);
if (i == 0) {
minLength = length;
} else {
minLength = Math.min(length, minLength);
}
}
// 新建一个桶的集合
List<LinkedList<Integer>> buckets = new ArrayList<>();
for (int i = 0, j = maxLength - minLength + 1; i < j; i++) {
// 新建一个桶，并将其添加到桶的集合中去。
buckets.add(new LinkedList<>());
}
for (int i : clone) {
int index = String.valueOf(i).length() - 1;
LinkedList<Integer> integers = buckets.get(index);
integers.add(i);
}
int[] finalArr = new int[clone.length];
int tempIndex = 0;
// 计数排序
for (LinkedList<Integer> integers : buckets) {
if (integers.size() > 0) {
int max = integers.get(0);
int min = integers.get(0);
for (Integer i : integers) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int dValue = max - min;
int[] countArray = new int[dValue + 1];
for (int value : integers) {
countArray[value - min]++;
}
// 统计数组做变形，后边的元素等于前面的元素之和
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
// 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
Integer[] sortedArray = new Integer[integers.size()];
for (int i = integers.size() - 1; i >= 0; i--) {
// 给sortedArray的当前位置赋值
sortedArray[countArray[integers.get(i) - min] - 1] = integers.get(i);
// 给countArray的位置的值--
countArray[integers.get(i) - min]--;
}
for (Integer integer : sortedArray) {
finalArr[tempIndex++] = integer;
}
}
}
return finalArr;
}
归并排序
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
/**
* 归并排序
*
* @param ints 数组
* @param start 左角标
* @param end 右角标
* @param tempArr 辅助数组
*/
private static void mergeSort(int[] ints, int start, int end, int[] tempArr) {
// 当子序列中只有一个元素时结束递归
if (start < end) {
// 划分子序列
int mid = (start + end) / 2;
// 对左侧子序列进行递归排序
mergeSort(ints, start, mid, tempArr);
// 对右侧子序列进行递归排序
mergeSort(ints, mid + 1, end, tempArr);
// 合并
merge(ints, start, mid, end, tempArr);
}
}
/** 两路归并算法，两个排好序的子序列合并为一个子序列 */
private static void merge(int[] ints, int left, int mid, int right, int[] tempArr) {
int p1 = left, p2 = mid + 1, k = left;
while (p1 <= mid && p2 <= right) {
if (ints[p1] <= ints[p2]) {
tempArr[k++] = ints[p1++];
} else {
tempArr[k++] = ints[p2++];
}
}
while (p1 <= mid) {
// 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
tempArr[k++] = ints[p1++];
}
while (p2 <= right) {
tempArr[k++] = ints[p2++];
}
// 复制回原素组
if (right + 1 - left >= 0) {
System.arraycopy(tempArr, left, ints, left, right + 1 - left);
}
}
希尔排序
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
/** 希尔排序 */
public static void shellSort(int[] clone) {
// 步长逐渐减小
for (int gap = clone.length / 2; gap > 0; gap /= 2) {
// 在同一步长内
for (int i = gap; i < clone.length; i++) {
// 同一步长内排序方式是插入排序
int temp = clone[i], j;
// j-gap代表有序数组中最大数的下标，j-pag表示有序数组的前一个元素，减pag是减去偏移量就是步长
for (j = i; j >= gap && temp < clone[j - gap]; j -= gap) {
// 原有序数组最大的后移一位
clone[j] = clone[j - gap];
}
// 找到了合适的位置插入
clone[j] = temp;
}
}
}
堆排序
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
/** 堆排序 */
private static void heapSort(int[] clone) {
// 创建堆
for (int i = (clone.length - 1) / 2; i >= 0; i--) {
// 从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(clone, i, clone.length);
}
// 调整堆结构,交换堆顶元素与末尾元素
for (int i = clone.length - 1; i > 0; i--) {
// 将堆顶元素与末尾元素进行交换
clone[i] = clone[i]+clone[0];
clone[0] = clone[i]-clone[0];
clone[i] = clone[i]-clone[0];
// 重新对堆进行调整
adjustHeap(clone, 0, i);
}
}
/**
* 调整堆
*
* @param arr 待排序列
* @param parent 父节点
* @param length 待排序列尾元素索引
*/
private static void adjustHeap(int[] arr, int parent, int length) {
// 将temp作为父节点
int temp = arr[parent];
// 左孩子
int lChild = 2 * parent + 1;
while (lChild < length) {
// 右孩子
int rChild = lChild + 1;
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (rChild < length && arr[lChild] < arr[rChild]) {
lChild++;
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if (temp >= arr[lChild]) {
break;
}
// 把孩子结点的值赋给父结点
arr[parent] = arr[lChild];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = lChild;
lChild = 2 * lChild + 1;
}
arr[parent] = temp;
}
练习代码
import java.util.*;
/**
* @author: shihchieh.ma
* @create: 2020/6/15 6:13 下午
* @email: shihchieh.ma@gail.com
* @description:
*/
public class Sort {
public static final int[] INTS = {
24, 352, 23, 4, 1, 421, 5, 6, 436, 7, 86, 97, 9, 74, 34, 234, 1, 3, 6, 7
// 10, 8, 6, 4, 2
};
/**
* @param n 生成n个元素的随机数组
* @param rangeL 随机范围[rangeL
* @param rangeR rangeR]
* @return 返回一个随机 int 型数组
*/
public static int[] gennerateArray(int n, int rangeL, int rangeR) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = (int) (Math.random() * (rangeR - rangeL + 1)) + rangeL;
}
return arr;
}
public static void main(String[] args) {
// int[] INTS = gennerateArray(10000, 1,10001);
long startTime, endTime;
// 冒泡排序
int[] bubbleArr = INTS.clone();
startTime = System.currentTimeMillis();
bubbleSort(bubbleArr);
endTime = System.currentTimeMillis();
printArray("冒泡排序:", bubbleArr, endTime - startTime);
// 选择排序
int[] selectionArr = INTS.clone();
startTime = System.currentTimeMillis();
selectionSort(selectionArr);
endTime = System.currentTimeMillis();
printArray("选择排序:", selectionArr, endTime - startTime);
// 插入排序
int[] insertArr = INTS.clone();
startTime = System.currentTimeMillis();
insertSort(insertArr);
endTime = System.currentTimeMillis();
printArray("插入排序:", insertArr, endTime - startTime);
// 快速排序
int[] quickArr = INTS.clone();
startTime = System.currentTimeMillis();
quickSort(quickArr, 0, quickArr.length - 1);
endTime = System.currentTimeMillis();
printArray("快速排序:", quickArr, endTime - startTime);
// 计数排序
int[] countArr = INTS.clone();
startTime = System.currentTimeMillis();
int[] countSort = countSort(countArr);
endTime = System.currentTimeMillis();
printArray("计数排序:", countSort, endTime - startTime);
// 基数排序
int[] radixArr = INTS.clone();
startTime = System.currentTimeMillis();
radixSort(radixArr);
endTime = System.currentTimeMillis();
printArray("基数排序:", radixArr, endTime - startTime);
// 桶排序
int[] bucketArr = INTS.clone();
startTime = System.currentTimeMillis();
int[] bucketSort = bucketSort(bucketArr);
endTime = System.currentTimeMillis();
printArray("桶排序:", bucketSort, endTime - startTime);
// 归并排序
int[] mergeArr = INTS.clone();
startTime = System.currentTimeMillis();
mergeSort(mergeArr, 0, mergeArr.length - 1, new int[mergeArr.length]);
endTime = System.currentTimeMillis();
printArray("归并排序:", mergeArr, endTime - startTime);
// 希尔排序
int[] shellArr = INTS.clone();
startTime = System.currentTimeMillis();
mergeSort(shellArr, 0, shellArr.length - 1, new int[shellArr.length]);
endTime = System.currentTimeMillis();
printArray("希尔排序:", shellArr, endTime - startTime);
// 堆排序
int[] heapArr = INTS.clone();
startTime = System.currentTimeMillis();
heapSort(heapArr);
endTime = System.currentTimeMillis();
printArray("堆排序:", heapArr, endTime - startTime);
}
/** 冒泡排序 */
private static void bubbleSort(int[] clone) {
for (int i = 0, j = clone.length; i < j; i++) {
for (int k = 0, l = j - 1 - i; k < l; k++) {
if (clone[k] > clone[k + 1]) {
clone[k] = clone[k] ^ clone[k + 1];
clone[k + 1] = clone[k] ^ clone[k + 1];
clone[k] = clone[k] ^ clone[k + 1];
}
}
}
}
/** 选择排序 */
private static void selectionSort(int[] clone) {
for (int i = 0, j = clone.length; i < j; i++) {
int minIndex = i;
for (int k = i; k < j; k++) {
if (clone[k] < clone[minIndex]) {
minIndex = k;
}
}
if (minIndex != i) {
clone[i] = clone[i] + clone[minIndex];
clone[minIndex] = clone[i] - clone[minIndex];
clone[i] = clone[i] - clone[minIndex];
}
}
}
/** 插入排序 */
private static void insertSort(int[] clone) {
for (int i = 1, j = clone.length; i < j; i++) {
int k = i;
int temp = clone[k];
while (k > 0 && clone[k - 1] > temp) {
clone[k] = clone[k - 1];
k--;
}
clone[k] = temp;
}
}
/**
* 快速排序
*
* @param clone 数组
* @param leftIndex 左边角标 初始0
* @param rightIndex 右边角标 初始length-1
*/
private static void quickSort(int[] clone, int leftIndex, int rightIndex) {
// temp-基准位
int i, j, temp;
if (leftIndex > rightIndex) {
return;
}
i = leftIndex;
j = rightIndex;
temp = clone[leftIndex];
while (i < j) {
// 先右边，往左递减,找一个小于基准位的数
// 当右边的角标位置所在的数>基准位的数时，继续从右往左找（同时 j 索引-1)
// 找到就跳出 while循环
while (temp <= clone[j] && i < j) {
j--;
}
// 再左边，往右递增
// 如上
while (temp >= clone[i] && i < j) {
i++;
}
// 满足条件则交换
if (i < j) {
clone[i] = clone[i] + clone[j];
clone[j] = clone[i] - clone[j];
clone[i] = clone[i] - clone[j];
}
}
// i=j 左右在同一位置
// 最后将基准为与i和j相等位置的数字交换
clone[leftIndex] = clone[i];
clone[i] = temp;
// 左半数组<(i或j所在索引的数)<右半数组
// 也就是说(i或j所在索引的数)已经确定排序位置，就不用再排序了，
// 相同的方法分别处理左右数组
// 递归调用左半数组
quickSort(clone, leftIndex, j - 1);
// 递归调用右半数组
quickSort(clone, j + 1, rightIndex);
}
/** 计数排序 */
private static int[] countSort(int[] clone) {
int max = clone[0];
int min = clone[0];
for (int i = 1, j = clone.length; i < j; i++) {
if (clone[i] > max) {
max = clone[i];
}
if (clone[i] < min) {
min = clone[i];
}
}
int dValue = max - min;
int[] countArray = new int[dValue + 1];
for (int value : clone) {
countArray[value - min]++;
}
// 统计数组做变形，后边的元素等于前面的元素之和
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
// 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
int[] sortedArray = new int[clone.length];
for (int i = clone.length - 1; i >= 0; i--) {
// 给sortedArray的当前位置赋值
sortedArray[countArray[clone[i] - min] - 1] = clone[i];
// 给countArray的位置的值--
countArray[clone[i] - min]--;
}
return sortedArray;
}
/** 基数排序 */
private static void radixSort(int[] clone) {
int maxLength = 0;
// 最大位数
for (int i : clone) {
int length = String.valueOf(i).length();
maxLength = Math.max(length, maxLength);
}
List<List<Integer>> list =
new ArrayList<List<Integer>>() {
{
// 0-9
for (int i = 0; i < 10; i++) {
add(new ArrayList<>());
}
}
};
for (int i = 0, temp = 1; i < maxLength; temp *= 10, i++) {
for (int value : clone) {
list.get((value / temp) % 10).add(value);
}
for (int j = 0, k = 0, l = list.size(); j < l; j++) {
while (!list.get(j).isEmpty()) {
clone[k] = list.get(j).get(0);
list.get(j).remove(0);
k++;
}
}
}
}
/** 桶排序 */
private static int[] bucketSort(int[] clone) {
int maxLength = 0, minLength = 0;
// 最大位数and最小位数
for (int i = 0, j = clone.length; i < j; i++) {
int length = String.valueOf(clone[i]).length();
maxLength = Math.max(length, maxLength);
if (i == 0) {
minLength = length;
} else {
minLength = Math.min(length, minLength);
}
}
// 新建一个桶的集合
List<LinkedList<Integer>> buckets = new ArrayList<>();
for (int i = 0, j = maxLength - minLength + 1; i < j; i++) {
// 新建一个桶，并将其添加到桶的集合中去。
buckets.add(new LinkedList<>());
}
for (int i : clone) {
int index = String.valueOf(i).length() - 1;
LinkedList<Integer> integers = buckets.get(index);
integers.add(i);
}
int[] finalArr = new int[clone.length];
int tempIndex = 0;
// 计数排序
for (LinkedList<Integer> integers : buckets) {
if (integers.size() > 0) {
int max = integers.get(0);
int min = integers.get(0);
for (Integer i : integers) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int dValue = max - min;
int[] countArray = new int[dValue + 1];
for (int value : integers) {
countArray[value - min]++;
}
// 统计数组做变形，后边的元素等于前面的元素之和
for (int i = 1; i < countArray.length; i++) {
countArray[i] += countArray[i - 1];
}
// 倒序遍历原始数组，从统计数组中找到正确的位置，输出到结果数组
Integer[] sortedArray = new Integer[integers.size()];
for (int i = integers.size() - 1; i >= 0; i--) {
// 给sortedArray的当前位置赋值
sortedArray[countArray[integers.get(i) - min] - 1] = integers.get(i);
// 给countArray的位置的值--
countArray[integers.get(i) - min]--;
}
for (Integer integer : sortedArray) {
finalArr[tempIndex++] = integer;
}
}
}
return finalArr;
}
/**
* 归并排序
*
* @param ints 数组
* @param start 左角标
* @param end 右角标
* @param tempArr 辅助数组
*/
private static void mergeSort(int[] ints, int start, int end, int[] tempArr) {
// 当子序列中只有一个元素时结束递归
if (start < end) {
// 划分子序列
int mid = (start + end) / 2;
// 对左侧子序列进行递归排序
mergeSort(ints, start, mid, tempArr);
// 对右侧子序列进行递归排序
mergeSort(ints, mid + 1, end, tempArr);
// 合并
merge(ints, start, mid, end, tempArr);
}
}
/** 两路归并算法，两个排好序的子序列合并为一个子序列 */
private static void merge(int[] ints, int left, int mid, int right, int[] tempArr) {
int p1 = left, p2 = mid + 1, k = left;
while (p1 <= mid && p2 <= right) {
if (ints[p1] <= ints[p2]) {
tempArr[k++] = ints[p1++];
} else {
tempArr[k++] = ints[p2++];
}
}
while (p1 <= mid) {
// 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
tempArr[k++] = ints[p1++];
}
while (p2 <= right) {
tempArr[k++] = ints[p2++];
}
// 复制回原素组
if (right + 1 - left >= 0) {
System.arraycopy(tempArr, left, ints, left, right + 1 - left);
}
}
/** 希尔排序 */
private static void shellSort(int[] clone) {
// 步长逐渐减小
for (int gap = clone.length / 2; gap > 0; gap /= 2) {
// 在同一步长内
for (int i = gap; i < clone.length; i++) {
// 同一步长内排序方式是插入排序
int temp = clone[i], j;
// j-gap代表有序数组中最大数的下标，j-pag表示有序数组的前一个元素，减pag是减去偏移量就是步长
for (j = i; j >= gap && temp < clone[j - gap]; j -= gap) {
// 原有序数组最大的后移一位
clone[j] = clone[j - gap];
}
// 找到了合适的位置插入
clone[j] = temp;
}
}
}
/** 堆排序 */
private static void heapSort(int[] clone) {
// 创建堆
for (int i = (clone.length - 1) / 2; i >= 0; i--) {
// 从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(clone, i, clone.length);
}
// 调整堆结构,交换堆顶元素与末尾元素
for (int i = clone.length - 1; i > 0; i--) {
// 将堆顶元素与末尾元素进行交换
clone[i] = clone[i]+clone[0];
clone[0] = clone[i]-clone[0];
clone[i] = clone[i]-clone[0];
// 重新对堆进行调整
adjustHeap(clone, 0, i);
}
}
/**
* 调整堆
*
* @param arr 待排序列
* @param parent 父节点
* @param length 待排序列尾元素索引
*/
private static void adjustHeap(int[] arr, int parent, int length) {
// 将temp作为父节点
int temp = arr[parent];
// 左孩子
int lChild = 2 * parent + 1;
while (lChild < length) {
// 右孩子
int rChild = lChild + 1;
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (rChild < length && arr[lChild] < arr[rChild]) {
lChild++;
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if (temp >= arr[lChild]) {
break;
}
// 把孩子结点的值赋给父结点
arr[parent] = arr[lChild];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = lChild;
lChild = 2 * lChild + 1;
}
arr[parent] = temp;
}
private static void printArray(String name, int[] ints, long time) {
for (int anInt : ints) {
System.out.print("_" + anInt + "_");
}
System.out.println("\t");
System.out.println(name + "耗时:" + time);
System.out.println();
}
}
