基本排序算法
基本排序算法
1. 冒泡排序（Bubble Sort）
public class BubbleSort {
public void bubbleSort(int[] arr) {
int n = arr.length;
// 外层循环控制排序趟数
for (int i = 0; i < n - 1; i++) {
// 内层循环控制每一趟排序多少次
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > 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)，因为只使用了常数数量的空间。
2. 选择排序（Selection Sort）
public class SelectionSort {
public 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;
}
}
// 将最小元素交换到前面
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}- 时间复杂度：最优时间复杂度是 O(n^2)，最差时间复杂度是 O(n^2)，平均时间复杂度是 O(n^2)。
- 空间复杂度：O(1)，因为只使用了常数数量的空间。
3. 插入排序（Insertion Sort）
public class InsertionSort {
public void insertionSort(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 = j - 1;
}
// 插入新元素
arr[j + 1] = key;
}
}
}- 时间复杂度：最优(数组已经排序)时间复杂度是 O(n)，最差(数组完全逆序)时间复杂度是 O(n^2)，平均时间复杂度是 O(n^2)。
- 空间复杂度：O(1)，因为只使用了常数数量的空间。
4. 希尔排序（Shell Sort）
public class ShellSort {
public void shellSort(int[] arr) {
int n = arr.length;
// 初始间隔
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个间隔序列进行插入排序
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;
}
}
}
}- 时间复杂度：最优时间复杂度是 O(n log n)，最差时间复杂度是 O(n^2)，平均时间复杂度取决于间隔序列。
- 空间复杂度：O(1)，因为只使用了常数数量的空间。
5. 归并排序（Merge Sort）
public class MergeSort {
public 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 void merge(int[] arr, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left, j = mid + 1, 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++];
}
for (int p = 0; p < temp.length; p++) {
arr[left + p] = temp[p];
}
}
}- 时间复杂度：最优时间复杂度是 O(n log n)，最差时间复杂度是 O(n log n)，平均时间复杂度是 O(n log n)。
- 空间复杂度：O(n)，因为需要一个与原始数组同样大小的数组来合并元素。
6. 快速排序（Quick Sort）
public class QuickSort {
public void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
public int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
// 当前元素小于或等于 pivot
if (arr[j] <= pivot) {
i++;
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i+1] 和 arr[high]（或 pivot）
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}- 时间复杂度：最优时间复杂度是 O(n log n)，最差时间复杂度是 O(n^2)，平均时间复杂度是 O(n log n)。
- 空间复杂度：O(log n)，在最坏的情况下，快速排序需要深度为 log n 的递归调用栈。
7.堆排序（Heap Sort）
public class HeapSort {
public void heapSort(int arr[]) {
int n = arr.length;
// 建立堆 (rearrange array)
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);
}
}
void heapify(int arr[], int n, int i) {
int largest = i; // 初始化最大元素为根
int left = 2 * i + 1; // 左 = 2*i + 1
int right = 2 * i + 2; // 右 = 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);
}
}
}- 时间复杂度：最优时间复杂度是O(n log n)，最差时间复杂度是O(n log n)，平均时间复杂度是O(n log n)。
- 空间复杂度：O(1)，因为只使用了常数数量的空间。
8.计数排序（Counting Sort）
核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。这种排序是针对整数数据的，不适用于浮点数或字符串。
public class CountingSort {
void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1; // 找出数组的范围
int[] count = new int[range]; // 存储每个元素的计数
int[] output = new int[arr.length]; // 存储排序后的数组
for (int num : arr) { // 对每个元素进行计数
count[num - min]++;
}
for (int i = 1; i < count.length; i++) { // 改变count[i]，使得它现在包含实际位置
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) { // 构建输出数组
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
System.arraycopy(output, 0, arr, 0, arr.length); // 将结果复制回原数组
}
}- 时间复杂度：最优时间复杂度是O(n+k)，最差时间复杂度是O(n+k)，平均时间复杂度是O(n+k)。其中n是待排序数组的长度，k是数组中的最大值。
- 空间复杂度：O(n+k)，因为我们需要额外的数组来计数和存储排序后的数组。
9. 桶排序（Bucket Sort）：
import java.util.*;
public class BucketSort {
public static void bucketSort(float[] arr, int n) {
if (n <= 0)
return;
@SuppressWarnings("unchecked")
ArrayList<Float>[] bucket = new ArrayList[n];
for (int i = 0; i < n; i++) {
bucket[i] = new ArrayList<Float>();
}
// 将数组中的值分配到桶中
for (int i = 0; i < n; i++) {
int bucketIndex = (int) arr[i] * n;
bucket[bucketIndex].add(arr[i]);
}
// 对每个桶进行排序
for (int i = 0; i < n; i++) {
Collections.sort((bucket[i]));
}
// 获取排序后的数组
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0, size = bucket[i].size(); j < size; j++) {
arr[index++] = bucket[i].get(j);
}
}
}
}- 时间复杂度：最优时间复杂度是O(n+k)，最差时间复杂度是O(n^2)，平均时间复杂度是O(n+k)。其中n是待排序数组的长度，k是桶的数量。
- 空间复杂度：O(n+k)，因为我们需要额外的桶来存储元素。
10. 基数排序（Radix Sort）：
public class RadixSort {
public static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSortByDigit(arr, arr.length, exp);
}
}
public static void countingSortByDigit(int[] arr, int n, int exp) {
int[] output = new int[n];
int[] count = new int[10];
Arrays.fill(count, 0);
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
}- 时间复杂度：最优时间复杂度是O(nk)，最差时间复杂度是O(nk)，平均时间复杂度是O(nk)。其中n是待排序数组的长度，k是数组中的最大数的位数。
- 空间复杂度：O(n+k)，因为我们需要额外的数组来计数和存储排序后的数组。