八大基础排序
1. 冒泡排序（Bubble Sort）
基本思想：依次比较相邻的两个元素，若它们的顺序错误则进行交换。
特点：稳定排序，但效率较低，时间复杂度为O(n^2)，空间复杂度为O(1)。
代码实例
public class BubbleSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用冒泡排序对数组进行排序
bubbleSort(arr);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 冒泡排序方法
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 标记位，表示这一趟是否有交换
for (int j = 0; j < n - i - 1; j++) {
// 交换如果元素找到比下一个元素大
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
// 如果有交换，则标记为true
swapped = true;
}
}
// 如果没有交换发生，说明数组已经有序
if (!swapped) {
break;
}
}
}
}
2. 选择排序（Selection Sort）
基本思想：在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。
特点：不稳定排序，时间复杂度为O(n^2)，空间复杂度为O(1)。
实例代码
public class SelectionSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用选择排序对数组进行排序
selectionSort(arr);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 选择排序方法
public static void selectionSort(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;
}
}
// 将找到的最小元素与第一个未排序的元素交换
if (minIndex != i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
}
3. 插入排序（Insertion Sort）
基本思想：将待排序的数据分成已排序和未排序两部分，每次将一个元素插入到已排序部分的正确位置。
特点：稳定排序，时间复杂度为O(n^2)，空间复杂度为O(1)。
实例代码
public class InsertionSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用插入排序对数组进行排序
insertionSort(arr);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 插入排序方法
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i]; // 要插入的元素
int j = i - 1;
// 将比key大的元素向后移动
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // 将key插入到正确的位置
}
}
}
4. 快速排序（Quick Sort）
基本思想：通过一趟排序将待排记录分割为独立的两个部分，其中一部分记录的关键字均比另一部分的关键字小，然后对这两部分记录继续进行排序，以达到整个序列有序。
特点：不稳定排序，但效率较高，时间复杂度为O(nlogn)，空间复杂度为O(logn)。
示例代码
public class QuickSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用快速排序对数组进行排序
quickSort(arr, 0, arr.length - 1);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 快速排序方法
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi是分区索引，arr[p]现在已经到位
int pi = partition(arr, low, high);
// 分别对分区前后部分进行排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 分区操作
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最右边的元素作为轴点
int i = (low - 1); // 最小元素索引
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于轴点
if (arr[j] <= pivot) {
i++; // 递增索引
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将轴点元素放到最终的位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
5. 归并排序（Merge Sort）
基本思想：将两个或两个以上的有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。
特点：稳定排序，时间复杂度为O(nlogn)，但空间复杂度较高，为O(n)。
public class MergeSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用归并排序对数组进行排序
arr = mergeSort(arr, 0, arr.length - 1);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 归并排序方法
public static int[] mergeSort(int[] arr, int left, int right) {
if (left < right) {
// 找到中间索引
int mid = left + (right - left) / 2;
// 对左半部分进行归并排序
arr = mergeSort(arr, left, mid);
// 对右半部分进行归并排序
arr = mergeSort(arr, mid + 1, right);
// 合并两个已排序的部分
merge(arr, left, mid, right);
}
return arr;
}
// 合并两个已排序的部分
public static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
int[] L = new int[n1];
int[] R = new int[n2];
// 复制数据到临时数组
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];
// 合并临时数组到arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制L[]的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制R[]的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
}
6. 堆排序（Heap Sort）
基本思想：利用堆这种数据结构的特性，首先将待排序的数据构建成一个最大（或最小）堆，然后将堆顶元素与最后一个元素交换，并重新调整堆，这样就得到了最大（或最小）值。重复这个过程直到所有数据元素有序。
特点：不稳定排序，但效率较高，时间复杂度为O(nlogn)，空间复杂度为O(1)。
public class HeapSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用堆排序对数组进行排序
heapSort(arr);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 堆排序方法
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 一个个从堆顶取出元素
for (int i = n - 1; i >= 0; i--) {
// 将当前最大的元素arr[0]和arr[i]交换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新对剩下的元素进行堆化
heapify(arr, i, 0);
}
}
// 堆化方法
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 初始化最大值为根
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点比根大
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点比当前最大的还大
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大元素不是根
if (largest != i) {
// 交换
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归堆化受影响的子树
heapify(arr, n, largest);
}
}
}
7. 希尔排序（Shell Sort）
基本思想：先将整个待排记录序列分割为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
实例代码
public class ShellSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {64, 34, 25, 12, 22, 11, 90};
// 使用希尔排序对数组进行排序
shellSort(arr);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 希尔排序方法
public static void shellSort(int[] arr) {
int n = arr.length;
int gap = n / 2; // 初始间隔
// 动态定义间隔序列
while (gap > 0) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
// 对每个子序列进行插入排序
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
// 更新间隔
gap /= 2;
}
}
}
特点：不稳定排序，是插入排序的一种更高效的改进版本，时间复杂度依赖于增量序列的选择。
8. 基数排序（Radix Sort）
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
特点：稳定排序，适用于整数排序，时间复杂度取决于整数的位数和采用的基数。
示例代码
public class RadixSortExample {
public static void main(String[] args) {
// 示例数组
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
// 使用基数排序对数组进行排序
radixSort(arr);
// 输出排序后的数组
for (int num : arr) {
System.out.print(num + " ");
}
}
// 基数排序方法
public static void radixSort(int[] arr) {
// 找到数组中的最大数
int max = findMax(arr);
// 获取最大数的位数
int maxDigit = getMaxDigit(max);
// 初始化临时数组
int[][] temp = new int[10][arr.length];
int[] count = new int[10]; // 用于计数
// 对每一位进行排序
for (int i = 1; i <= maxDigit; i++) {
// 将数组元素分配到临时数组
for (int j = 0; j < arr.length; j++) {
int digit = getDigit(arr[j], i);
temp[digit][count[digit]] = arr[j];
count[digit]++;
}
// 将临时数组中的元素拷贝回原数组
int index = 0;
for (int k = 0; k < 10; k++) {
if (count[k] != 0) {
for (int l = 0; l < count[k]; l++) {
arr[index++] = temp[k][l];
}
count[k] = 0; // 重置计数
}
}
}
}
// 找到数组中的最大数
private static int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 获取最大数的位数
private static int getMaxDigit(int num) {
int count = 0;
while (num != 0) {
num /= 10;
count++;
}
return count;
}
// 获取一个数的第i位（从最低位开始计数）
private static int getDigit(int num, int i) {
return (num / (int) Math.pow(10, i - 1)) % 10;
}
}