Java中常见的几种排序算法：
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
- 希尔排序（Shell Sort）
- 归并排序（Merge Sort）
- 快速排序（Quick Sort）
- 堆排序（Heap Sort）
- 计数排序（Counting Sort）
- 桶排序（Bucket Sort）
- 基数排序（Radix Sort）
其中冒泡、选择、插入等是最常用的几种排序算法(必须要掌握)
算法复杂度
其中，n表示输入元素的数量，k表示元素的取值范围大小。
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机 内执行时所需存储空间的度量，它也是数据规模n的函数。
1.冒泡排序（Bubble Sort）
冒泡排序的基本思想是对比相邻的元素值，如果满足条件就交换元素值，把较小的元素移动到数组前面，把较大的元素移动到数组后面(也就是交换元素的位置)，这样较小的元素就像气泡一样从底部升到顶部。
算法示例
//排序实现
public void sort(int[] arry) {
for(int i=1;i<arry.length;i++) {
for(int j=0;j<arry.length-i;j++) {
//如果数组元素第一位比第二位大 就创建temp把第一位赋值于他
//然后第二位向前移，temp存储的第一位的值到第二位上 完成一次排序
if(arry[j]>arry[j+1]) {
int temp = arry[j];
arry[j] = arry[j+1];
arry[j+1] = temp;
}
}
}
showArry(arry);//遍历
}
public void showArry(int[] arry) {
for(int i:arry) {
System.out.print(">"+i);
}
}2.选择排序（Selection Sort）
基本思想：选择排序的基本思想是每次从待排序的元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的元素排完。
public class SelectionSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}3.插入排序（Insertion Sort）
基本思想：将未排序数据插入到已排序序列的合适位置
public class InsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}4.希尔排序（Quick Sort）
基本思想：将待排序的数组按照一定的间隔进行分组，对每组使用插入排序算法进行排序，然后缩小间隔，再对分组进行排序，直到间隔为1为止。逐渐减小间隔大小的方法有助于提高排序过程的效率，可以减少比较和交换的次数。这是希尔排序算法的一个关键特点。
算法示例：
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Shell {
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始化间隔（gap）的值，它决定了每次迭代中子数组的大小
// 从数组长度的一半开始作为初始间隔值，gap就是分割的子数组数量
for (int gap = n / 2; gap > 0; gap /= 2) {
// 循环从间隔值开始，遍历数组直到数组的末尾；代表循环所有的子数组
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// 将当前元素 arr[j] 的值替换为前一个元素 arr[j - gap] 的值。
// 通过这个操作，将较大的元素向后移动，为当前元素腾出位置
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Shell.shellSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
5.归并排序（Merge Sort）
基本思想：归并排序是一种分治思想的排序算法，它的基本思想是将待排序的数组分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的数组。
算法示例：
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Merge {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Merge.mergeSort(arr, 0, arr.length - 1);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
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) {
// 子数组 L 的大小
int n1 = mid - left + 1;
// 右子数组 R 的大小
int n2 = right - mid;
// 创建两个临时数组 L 和 R ，分别用来存储左子数组和右子数组的元素
int[] L = new int[n1];
int[] R = new int[n2];
// 使用 for 循环将原始数组 arr 中的元素复制到临时数组 L 和 R 中，分别从 left 和 mid + 1 开始
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
// 初始化三个变量 i、j和k，分别指向数组 L 、R 和原始数组 arr 的起始位置
int i = 0, j = 0, k = left;
// 使用 while 循环，比较 L 和 R 的元素，并将较小的元素放回原始数组 arr 中
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 当 L 或 R 中的元素用完时，将剩余的元素依次放回原始数组 arr 中
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
// merge 方法执行完毕后，两个子数组范围内的元素已经按照从小到大的顺序合并到了原始数组 arr 中
}
}
6. 快速排序（Quick Sort）
基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
算法示例：
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Quick {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 6, 1, 3};
int[] expectedArr = {1, 2, 3, 5, 6, 8};
Quick.quickSort(arr, 0, arr.length - 1);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
// 接收一个数组 arr，一个低索引 low ，和一个高索引 high 作为参数
public static void quickSort(int[] arr, int low, int high) {
// 检查 low 是否小于 high。如果不是，则意味着数组只有一个元素或为空，因此不需要排序
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
/**
* 取最后一个元素作为枢轴元素，将较小的元素放在左边，较大的元素放在右边
* @param arr 输入数组
* @param low 低位索引
* @param high 高位索引
* @return 枢轴所在位置
*/
private static int partition(int[] arr, int low, int high) {
// 将最后一个元素作为枢轴元素（ arr[high] ）
int pivot = arr[high];
// 将 i 初始化为 low - 1，用于跟踪较小元素的索引
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
// 如果当前元素 arr[j] 小于枢轴元素，则增加 i 并交换 arr[i] 和 arr[j]
// 较小元素索引+1
i++;
// 将当前元素 arr[j] 放在较小元素索引位置
// 将较小元素放在前面
swap(arr, i, j);
}
// 其他情况，则较小元素索引没有增加，说明当前元素应该放在右边
}
// 将枢轴元素（ arr[high] ）与索引 i + 1 处的元素交换。
// 确保枢轴元素左边是较小元素，右边是较大元素
swap(arr, i + 1, high);
// 将 i + 1 作为枢轴索引返回
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
7. 堆排序（Heap Sort）
基本思想：将待排序的数组构建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，再将剩余元素重新构建成堆，重复执行交换和重构堆的操作，直到整个数组有序。
算法示例：
public class Heap {
// 堆排序方法
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建大根堆，
// 这段代码是构建大根堆的过程，它的循环次数为n/2-1次，是因为在完全二叉树中，叶子节点不需要进行堆化操作，
// 所以只需要对非叶子节点进行堆化，而非叶子节点的数量为n/2-1个。因此，只需要循环n/2-1次即可完成大根堆的构建。
// 非叶子节点在一维数组中就是前面 n/2-1
for (int i = n / 2 - 1; i >= 0; i--) {
// 从最底层的根节点开始堆化，每次执行完成后，都找出最大值，并放在根节点位置
// 逐层往上找，循环结束后，第一个元素肯定是最大值
heapify(arr, n, i);
}
// 依次取出堆顶元素，并将余下元素继续堆化，得到有序序列
for (int i = n - 1; i >= 0; i--) {
// 第一个for循环已经找出最大值，所以先做交货，把最大值换到最后一个位置
// 把最大值交换到最后一个位置，下一次循环最后一个位置就不比较了
swap(arr, 0, i);
// 继续找出最大值，放在第一个位置
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int heapSize, int i) {
int largest = i; // 初始化假设最大值为根节点
int left = 2 * i + 1; // 相对于索引i的左节点索引
int right = 2 * i + 2; // 相对于索引i的右节点索引
// 找到左右子节点中的最大值
if (left < heapSize && arr[left] > arr[largest]) {
// 如果有左节点，且左节点大于根节点，则记录左节点为最大值
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
// 如果有右节点，且右节点大于最大值，则记录右节点为最大值
largest = right;
}
// 上面两个if之后，肯定找到最大值
if (largest != i) {
// i 是根节点下标
// 如果最大值不是根节点，则交换根节点与最大值节点，
// 并递归地对最大值节点进行堆化
swap(arr, i, largest);
heapify(arr, heapSize, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
Heap.heapSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
8. 计数排序（Counting Sort）
基本思想：统计数组中每个元素出现的次数，然后根据元素出现的次数依次将元素放入有序的数组中。 
算法示例：
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Counting {
public static void countingSort(int[] arr) {
int n = arr.length;
// 取出数组中最大值
int max = getMax(arr);
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 计算每个元素在有序序列中的位置
for (int i = 1; i <= max; i++) {
// 因为count包含了每个数据出现的次数，所以从小到大，
// 逐个往前加得到就是原数组中每个元素在有序序列中应有的位置
count[i] += count[i - 1];
}
// 输出有序序列
int[] sortedArr = new int[n];
for (int i = n - 1; i >= 0; i--) {
int item = arr[i];//元素
int itemPos = count[item];// 元素在有序数组中的位置
sortedArr[itemPos - 1] = item; // 将元素填入有序数组
count[item]--;
}
// 将有序序列复制回原数组
System.arraycopy(sortedArr, 0, arr, 0, n);
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
public static void main(String[] args) {
int[] arr = {5, 2, 6, 8, 3, 1, 6, 5, 12};
int[] expectedArr = {1, 2, 3, 5, 5, 6, 6, 8, 12};
Counting.countingSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}
9. 桶排序（Bucket Sort）
基本思想：将待排序的数组分到有限数量的桶里，然后对每个桶进行排序，最后依次将所有桶中的元素取出来，组成有序的数组。
桶排序的时间复杂度为O(n)，其中n为待排序元素的个数。
算法示例：
import org.junit.jupiter.api.Assertions;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Bucket {
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
Bucket.bucketSort(arr, 20);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
/**
* 桶排序
* @param arr 待排序数组
* @param bucketSize 桶大小，数据不宜过大，桶越大，后续对桶内数据排序越耗时
*/
public static void bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
// 循环数组，先找到最小值和最大值
int minValue = arr[0];
int maxValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
// 根据桶的大小，计算桶个数，并初始化桶
int bucketCount = (maxValue - minValue) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - minValue) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
int currentIndex = 0;
for (int i = 0; i < bucketCount; i++) {
List<Integer> bucket = buckets.get(i);
// 对桶内数据进行排序
Collections.sort(bucket);
// 将数据逐个从桶内取出，并存入数组
for (int j = 0; j < bucket.size(); j++) {
arr[currentIndex++] = bucket.get(j);
}
}
}
}
10. 基数排序（Radix Sort）
基本思想：将待排序的数组按照位数（个位、十位、百位）进行划分，然后依次对每个位上的数字进行排序，最终得到有序的数组。
基数排序的时间复杂度为O(d(n+k))，其中d为最大元素的位数，n为待排序元素的个数，k为桶的个数。
算法示例：
public class Radix {
public static void radixSort(int[] arr) {
if (arr.length == 0) {
return;
}
// 循环取得数组中的最大值
int maxNum = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxNum) {
maxNum = arr[i];
}
}
// 根据最大值算出数组中的最大位数，个位、十位、百位、千位等
int maxDigit = 0;
while (maxNum != 0) {
maxNum /= 10;
maxDigit++;
}
// 初始化10个list，分别存放位数是0-9的10组数字
List<List<Integer>> buckets = new ArrayList<>(10);
for (int i = 0; i < 10; i++) {
buckets.add(new ArrayList<>());
}
int mod = 10; // 初始10，用于数据个位数取模
int div = 1; // 桶序号除数
// 按位数循环数组，个位循环1次，十位循环2次，百位循环3次，以此类推！
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
// 循环数组，将数据分别存入桶中
// 第一次循环，桶里面的个位数顺序排序完成
// 第二次循环，个位、十位都排序完成
// 第三次循环，个位、十位、百位都排序完成
for (int j = 0; j < arr.length; j++) {
// 计算当前位数的桶序号
int bucketIndex = (arr[j] % mod) / div;
buckets.get(bucketIndex).add(arr[j]);
}
// 循环桶列表，将当前位数已排序的数据放入数组中
int currentIndex = 0;
for (int j = 0; j < 10; j++) {
List<Integer> bucket = buckets.get(j);
for (int k = 0; k < bucket.size(); k++) {
arr[currentIndex++] = bucket.get(k);
}
bucket.clear();
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 12, 35, 57, 1, 6};
int[] expectedArr = {1, 2, 3, 5, 6, 8, 12, 35, 57};
Radix.radixSort(arr);
System.out.println("arr = " + Arrays.toString(arr));
Assertions.assertArrayEquals(expectedArr, arr);
}
}