当前位置：首页 > backend >正文

常见排序算法及复杂度分析

backend 2025/5/14 7:10:25

冒泡排序 (Bubble Sort)

基本思想

相邻元素比较，大的元素后移

每轮将最大元素"冒泡"到末尾

代码实现

void bubbleSort(int arr[], int n) {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], arr[j+1]);}}}}

复杂度分析

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：稳定

最好情况：O(n)

最坏情况：O(n²)

2. 选择排序 (Selection Sort)

基本思想

每次从未排序区域选择最小元素

放到已排序区域末尾

代码实现

void selectionSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int min_idx = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}swap(arr[i], arr[min_idx]);}}

复杂度分析

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：不稳定

最好情况：O(n²)

最坏情况：O(n²)

3. 插入排序 (Insertion Sort)

基本思想

将元素插入到已排序区域的合适位置

适合小数据量或基本有序数据

代码实现

void insertionSort(int arr[], int n) {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;}}

复杂度分析

时间复杂度：O(n²)

空间复杂度：O(1)

稳定性：稳定

最好情况：O(n)

最坏情况：O(n²)

4. 快速排序 (Quick Sort)

基本思想

选择基准元素

将小于基准的元素放在左边

将大于基准的元素放在右边

递归处理左右两部分

代码实现

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);}}

复杂度分析

时间复杂度：平均O(nlogn)

空间复杂度：O(logn)

稳定性：不稳定

最好情况：O(nlogn)

最坏情况：O(n²)

5. 归并排序 (Merge Sort)

基本思想

将数组分成两半

递归排序两半

合并两个有序数组

代码实现

void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r-l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);}}

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(n)

稳定性：稳定

最好情况：O(nlogn)

最坏情况：O(nlogn)

6. 堆排序 (Heap Sort)

基本思想

构建最大堆

将堆顶元素与末尾元素交换

重新调整堆

代码实现

void heapSort(int arr[], int n) {for (int i = n/2-1; i >= 0; i--)heapify(arr, n, i);for (int i = n-1; i > 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}}

复杂度分析

时间复杂度：O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

最好情况：O(nlogn)

最坏情况：O(nlogn)

7. 希尔排序 (Shell Sort)

基本思想

是插入排序的改进版

通过不同的间隔序列进行分组插入排序

代码实现

void shellSort(int arr[], int n) {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^1.3)

空间复杂度：O(1)

稳定性：不稳定

最好情况：O(n)

最坏情况：O(n²)

8. 计数排序 (Counting Sort)

基本思想

统计每个元素出现的次数

根据统计结果重建数组

代码实现

void countingSort(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++)if (arr[i] > max)max = arr[i];int count[max+1] = {0};for (int i = 0; i < n; i++)count[arr[i]]++;int index = 0;for (int i = 0; i <= max; i++)while (count[i]--)arr[index++] = i;}

复杂度分析

时间复杂度：O(n+k)，k为数据范围

空间复杂度：O(k)

稳定性：稳定

最好情况：O(n+k)

最坏情况：O(n+k)

9. 基数排序 (Radix Sort)

基本思想

按照位数进行排序

从最低位到最高位依次排序

代码实现

void radixSort(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++)if (arr[i] > max)max = arr[i];for (int exp = 1; max/exp > 0; exp *= 10)countSort(arr, n, exp);}