// 选择排序
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
int k = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[k]) {
k = j;
}
}
if (k != i) {
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
// 冒泡排序
public static void bubbleSort(int[] arr) {
// 设置每次冒泡的终止点
for (int i = arr.length-1; i > 0; i--) {
boolean change = false;
// 从起点开始冒泡
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
if (change == false) {
change = true;
}
}
}
// 如果本次无交换，则表示已有序，排序完成
if (!change) {
return;
}
}
}
// 插入排序
public static void insertionSort(int[] arr) {
// 从第二个元素开始为它们找位置
for (int i = 1; i < arr.length; i++) {
// 记住当前元素
int temp = arr[i];
int j;
// 从当前元素左边第一个元素开始，向左找位置
for (j = i-1; j >= 0 && arr[j] > temp; j--) {
arr[j+1] = arr[j];
}
// 找到合适位置后，将当前元素插入
arr[j+1] = temp;
}
}
// 希尔排序
public static void shellSort(int[] arr) {
// 增量控制，每次减半
for (int gap = arr.length/2; gap > 0; gap /= 2) {
// 步长控制，从gap开始向后移动
for (int i = gap; i < arr.length; i++) {
int temp = arr[i];
int j;
// 起始指针控制，向左插入排序（找位置）
for (j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
}
// 归并排序
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
// 分
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
// 治
merge(arr, left, mid, right);
}
}
public static void merge(int[] arr, int left, int mid, int right) {
// 临时数组
int[] temp = new int[right-left+1];
// 左、右指针
int i = left;
int j = mid+1;
int k = 0;
// 将两段数据按序写入临时数组
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}else {
temp[k++] = arr[j++];
}
}
// 剩余数据写入
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
// 更新arr数组
k = 0;
while (left <= right) {
arr[left++] = temp[k++];
}
}
// 快速排序
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int index = getIndex(arr, left, right);
quickSort(arr, left, index-1);
quickSort(arr, index+1, right);
}
}
public static int getIndex(int[] arr, int left, int right) {
// 得到基准元素
int item = arr[left];
// 向中间移动，调整位置，找到基准元素的位置
while (left < right) {
while (left < right && arr[right] >= item) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= item) {
left++;
}
arr[right] = arr[left];
}
// 放置基准元素
arr[left] = item;
return left;
}
// 堆排序
public static void heapSort(int[] arr) {
// 1.构建大顶堆
for (int i = arr.length/2-1; i >= 0; i--) {
adjust(arr, i, arr.length);
}
// 2.调整堆结构，交换顶元素与末尾元素
for (int j = arr.length-1 ; j > 0; j--) {
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjust(arr, 0, j);
}
}
public static void adjust(int[] arr, int i, int length) {
int temp = arr[i];
for (int k = 2i+1; k < length; k = 2k+1) {
if (k+1 < length && arr[k+1] > arr[k]) {
k++;
}
if (arr[k] > temp) {
arr[i] = arr[k];
i = k;
}else {
break;
}
}
arr[i] = temp;
}
// 计数排序
public static int[] countSort(int[] src) {
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < src.length; i++){
max = Math.max(max, src[i]);
min = Math.min(min, src[i]);
}
// 数组中的数据范围
int range = max - min + 1;
// count[i]表示数组src中数据min + i的个数
int[] count = new int[range];
for (int value : src) {
count[value - min]++;
}
// 累计变形，使得count[i]保存src中小于等于min + i的数据的个数
for (int i = 1; i < range; i++) {
count[i] += count[i - 1];
}
// 结果数组
int[] res = new int[src.length];
// 倒序遍历原数组，保持排序的稳定性
for (int i = src.length - 1; i >= 0; i--) {
// 获取数据在count数组中的索引
int index = src[i] - min;
// 个数减1
count[index]--;
// 数据src[i]排序后的索引是count[index]
res[count[index]] = src[i];
}
return res;
}
// 桶排序
public static void bucketSort(int[] arr){
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 计算桶的数量,并创建桶
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
arr[index++] = bucketArr.get(i).get(j);
}
}
}
public static void radixSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
// 计算最大位数
public static int maxbits(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
// 基数排序
public static void radixSort(int[] arr, int begin, int end, int digit) {
final int radix = 10;
int i = 0, j = 0;
int[] count = new int[radix];
int[] bucket = new int[end - begin + 1];
// 依次遍历每个位数
for (int d = 1; d <= digit; d++) {
for (i = 0; i < radix; i++) {
count[i] = 0;
}
// 统计数量
for (i = begin; i <= end; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
// 计算位置
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// 记录到对应位置
for (i = end; i >= begin; i--) {
j = getDigit(arr[i], d);
count[j]--;
bucket[count[j]] = arr[i];
}
for (i = begin, j = 0; i <= end; i++, j++) {
arr[i] = bucket[j];
}
}
}
// 获取位数数值
public static int getDigit(int x, int d) {
return ((x / ((int) Math.pow(10, d - 1))) % 10);
}