嵌入式C语言阶段复习——排序方法-程序员充电站

一、冒泡排序

冒泡排序通过重复比较相邻元素并交换位置完成排序。每一轮将最大（或最小）元素“冒泡”到数组

末尾。

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]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } }

时间复杂度：平均和最坏情况为 O(n^2)，最好情况（已排序）为 O(n)。

二、选择排序

选择排序每次遍历未排序部分，找到最小（或最大）元素，与未排序部分的起始位置交换。

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; } } int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } }

时间复杂度：始终为 O(n^2)

三、插入排序

插入排序将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。

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^2)，最好情况（已排序）为 O(n)

四、快速排序

快速排序采用分治策略，选择一个基准值（pivot），将数组分为小于基准和大于基准的两部分，递

归排序子数组。
实现代码：

int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; 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; } 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(n *log n)，最坏（已排序或逆序）为 O(n^2)

五、归并排序

归并排序通过递归将数组分为两半，分别排序后合并。

void merge(int arr[], int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; int i = 0, j = 0, k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) arr[k++] = L[i++]; else arr[k++] = R[j++]; } while (i < n1) arr[k++] = L[i++]; while (j < n2) arr[k++] = R[j++]; } 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(n *log n)，但需要额外空间 O(n)。

六、堆排序

堆排序利用堆数据结构（完全二叉树），通过构建最大堆并交换堆顶元素实现排序。

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 temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapify(arr, n, largest); } } 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--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } }

时间复杂度：始终为 O(n *log n)