C 语言常用数组排序模板大揭秘：原理详解与代码实现

以下是几种常用的 C 语言数组排序算法模板及其原理： 1. 冒泡排序（Bubble Sort） ```c void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n - 1; i++) { for (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; } } } } ``` 原理：通过相邻元素的两两比较，将较大的元素逐步“浮”到数组的末尾。每次遍历数组，最大的未排序元素就会“冒”到正确的位置。 2. 插入排序（Insertion Sort） ```c void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } ``` 原理：将待排序的元素插入到已排序部分的适当位置。从第二个元素开始，将当前元素与已排序部分的元素依次比较并移动位置，直到找到合适的插入位置。 3. 选择排序（Selection Sort） ```c void selectionSort(int arr[], int n) { int i, j, min_idx; for (i = 0; i < n - 1; i++) { min_idx = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; if (min_idx!= i) { int temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; } } } ``` 原理：每次在未排序部分找到最小的元素，与未排序部分的起始位置元素交换位置，逐步将数组排序。 4. 快速排序（Quick Sort） ```c 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++; 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^2)，快速排序的平均时间复杂度为 O(n log n)。 ######[AI写代码神器 | 836点数解答 | 2024-11-02 22:54:55]