外观
外观
1128字约4分钟
2025-03-08
冒泡排序：通过相邻元素的比较和交换，逐步将最小或最大的元素冒泡到最后或最前；时间复杂度：最好O(n)，最差O(n^2)，平均O(n^2)，空间复杂度O(1)；
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}插入排序：通过将未排序列元素逐个插入到已排序列的合适的位置，形成有序序列；时间复杂度：最好O(n)，最差O(n^2)，平均O(n^2)，空间复杂度O(1)；
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;
// Move elements of arr[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}选择排序：通过不断选择未排序序列中的最大或最小的元素插入到已排序序列中最前或最后的位置，直到成为一个有序序列；时间复杂度：最好O(n^2)，最差O(n^2)，平均O(n^2)，空间复杂度O(1)；
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}快速排序：通过一个基准元素，将数组分为两个数组，使左数组中的元素都小于或等于（大于或等于）基准元素，右数组中的元素都大于或等于（小于或等于）基准元素，然后对子数组进行递归排序；时间复杂度：最好O(nlogn)，最差O(n^2)，平均O(nlogn)；空间复杂度：最好O(nlogn)，最差O(1)；
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
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); // Index of smaller element
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}归并排序：将数组不断分割为更小的子数组，然后将子数组进行合并，合并过程中进行排序；时间复杂度:最好O(nlogn)，最差O(nlogn)，平均O(nlogn)。空间复杂度:0(n)。
public static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
// Sort first and second halves
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, middle, right);
}
}
public static void merge(int[] arr, int left, int middle, int right) {
int n1 = middle - left + 1;
int n2 = right - middle;
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[middle + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}堆排序：通过将待排序元素构建成一个最大堆(或最小堆)，然后将堆顶元素与末尾元素交换，再重新调整堆，重复该过程直到排序完成。时间复杂度：最好O(nlogn)，最差O(nlogn)，平均、O(nlogn)；空间复杂度:0(1)。
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--) {
// 将当前堆顶（最大值）移到数组末尾
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; // 初始化largest为根节点
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);
}
}