数组排序算法

数组排序算法

用C语言实现的数组排序算法。

排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度是否稳定适用场景
QuickO(n log n)O(n²)O(n log n)O(log n)不稳定大规模数据，通用排序
BubbleO(n²)O(n²)O(n)O(1)稳定小规模数据，教学用途
InsertO(n²)O(n²)O(n)O(1)稳定小规模或部分有序数据
SelectO(n²)O(n²)O(n²)O(1)不稳定小规模数据，简单实现
MergeO(n log n)O(n log n)O(n log n)O(n)稳定大规模数据，稳定排序需求
HeapO(n log n)O(n log n)O(n log n)O(1)不稳定大规模数据，原地排序需求
CountO(n + k)O(n + k)O(n + k)O(n + k)稳定小范围整数排序
RadixO(d(n + k))O(d(n + k))O(d(n + k))O(n + k)稳定整数或字符串排序，位数较小
BucketO(n + k)O(n²)O(n)O(n + k)稳定均匀分布的数据
ShellO(n log n)O(n²)O(n log n)O(1)不稳定中等规模数据，改进的插入排序

快速排序

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。以下是使用C语言实现数组的快速排序的代码：

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 分区函数，返回分区点的索引
int partition(int arr[], int low, int high) {int pivot = arr[high];  // 选择最后一个元素作为基准int i = (low - 1);  // i是较小元素的索引for (int j = low; j <= high - 1; j++) {// 如果当前元素小于或等于基准if (arr[j] <= pivot) {i++;  // 增加较小元素的索引swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);  // 将基准元素放到正确的位置return (i + 1);
}// 快速排序的递归函数
void quickSort(int arr[], int low, int high) {if (low < high) {// pi是分区点，arr[pi]已经排好序int pi = partition(arr, low, high);// 递归地对分区点左边和右边的子数组进行排序quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {10, 7, 8, 9, 1, 5};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);quickSort(arr, 0, n - 1);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. swap函数：用于交换两个元素的值。
  2. partition函数：选择数组的最后一个元素作为基准（pivot），然后将数组分为两部分，左边部分的元素都小于或等于基准，右边部分的元素都大于基准。最后返回基准元素的正确位置。
  3. quickSort函数：递归地对数组进行排序。首先通过partition函数找到分区点，然后对分区点左边和右边的子数组分别进行快速排序。
  4. printArray函数：用于打印数组的内容。
  5. main函数：测试快速排序的实现。

运行结果：

原始数组: 
10 7 8 9 1 5 
排序后的数组: 
1 5 7 8 9 10

时间复杂度：

  • 平均时间复杂度：O(n log n)
  • 最坏时间复杂度：O(n^2)（当数组已经有序或所有元素相等时）
  • 空间复杂度：O(log n)（递归栈的深度）

快速排序是一种非常高效的排序算法，尤其适用于大规模数据的排序。

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地遍历数组，比较相邻的元素并交换它们的位置，直到整个数组有序。以下是使用C语言实现数组的冒泡排序的代码：

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 冒泡排序函数
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]);  // 如果顺序错误，交换元素}}}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);bubbleSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. swap函数：用于交换两个元素的值。
  2. bubbleSort函数：
    • 外层循环控制遍历次数，每次遍历会将当前未排序部分的最大值“冒泡”到正确的位置。
    • 内层循环比较相邻元素，如果顺序错误（前一个元素大于后一个元素），则交换它们。
  3. printArray函数：用于打印数组的内容。
  4. main函数：测试冒泡排序的实现。

运行结果：

原始数组: 
64 34 25 12 22 11 90 
排序后的数组: 
11 12 22 25 34 64 90

优化版本：

如果某次遍历中没有发生任何交换，说明数组已经有序，可以提前结束排序。以下是优化后的冒泡排序代码：

void bubbleSortOptimized(int arr[], int n) {int swapped;  // 标记是否发生交换for (int i = 0; i < n - 1; i++) {swapped = 0;  // 每次遍历前重置标记for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(&arr[j], &arr[j + 1]);swapped = 1;  // 发生交换，标记为1}}if (swapped == 0) {  // 如果没有发生交换，说明数组已经有序break;}}
}

时间复杂度：

  • 最坏情况：O(n²)（当数组完全逆序时）
  • 最好情况：O(n)（当数组已经有序时，优化版本可以达到）
  • 平均情况：O(n²)

空间复杂度：

  • O(1)（原地排序，不需要额外空间）

冒泡排序虽然简单，但在实际应用中效率较低，通常用于教学或小规模数据的排序。对于大规模数据，更高效的排序算法（如快速排序、归并排序等）更为适用。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是使用C语言实现数组的插入排序的代码：

插入排序代码实现

#include <stdio.h>// 插入排序函数
void insertionSort(int arr[], int n) {int i, j, key;for (i = 1; i < n; i++) {key = arr[i];  // 当前需要插入的元素j = i - 1;// 将比key大的元素向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;  // 插入key到正确位置}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 11, 13, 5, 6};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);insertionSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. insertionSort函数：
    • 从第二个元素开始（i = 1），将当前元素key插入到已排序部分的正确位置。
    • 使用while循环将比key大的元素向后移动，直到找到key的正确位置。
    • 将key插入到正确位置。
  2. printArray函数：用于打印数组的内容。
  3. main函数：测试插入排序的实现。

运行结果：

原始数组: 
12 11 13 5 6 
排序后的数组: 
5 6 11 12 13

时间复杂度：

  • 最坏情况：O(n²)（当数组完全逆序时）
  • 最好情况：O(n)（当数组已经有序时）
  • 平均情况：O(n²)

空间复杂度：

  • O(1)（原地排序，不需要额外空间）

插入排序的特点：

  1. 适合小规模数据：对于小规模数据或部分有序的数据，插入排序的效率较高。
  2. 稳定排序：插入排序是稳定的排序算法，相同元素的相对顺序不会改变。
  3. 简单直观：实现简单，易于理解和实现。

优化版本：

插入排序可以通过二分查找来优化查找插入位置的过程，将查找时间从O(n)优化到O(log n)，但整体时间复杂度仍然是O(n²)。

// 使用二分查找优化插入排序
void insertionSortOptimized(int arr[], int n) {int i, j, key, low, high, mid;for (i = 1; i < n; i++) {key = arr[i];low = 0;high = i - 1;// 使用二分查找找到插入位置while (low <= high) {mid = (low + high) / 2;if (arr[mid] > key) {high = mid - 1;} else {low = mid + 1;}}// 将元素向后移动for (j = i - 1; j >= low; j--) {arr[j + 1] = arr[j];}arr[low] = key;  // 插入key到正确位置}
}

插入排序在实际应用中常用于小规模数据排序或作为其他排序算法（如快速排序、归并排序）的辅助排序方法。

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是每次从未排序部分中选择最小（或最大）的元素，将其放到已排序部分的末尾。以下是使用C语言实现数组的选择排序的代码：

选择排序代码实现

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 选择排序函数
void selectionSort(int arr[], int n) {int i, j, min_idx;for (i = 0; i < n - 1; i++) {min_idx = i;  // 假设当前索引i是最小元素的索引// 在未排序部分中找到最小元素的索引for (j = i + 1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 将找到的最小元素与当前元素交换if (min_idx != i) {swap(&arr[min_idx], &arr[i]);}}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);selectionSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. swap函数：用于交换两个元素的值。
  2. selectionSort函数：
    • 外层循环从第一个元素开始，依次选择未排序部分的最小元素。
    • 内层循环在未排序部分中找到最小元素的索引。
    • 将找到的最小元素与当前元素交换。
  3. printArray函数：用于打印数组的内容。
  4. main函数：测试选择排序的实现。

运行结果：

原始数组: 
64 25 12 22 11 
排序后的数组: 
11 12 22 25 64

时间复杂度：

  • 最坏情况：O(n²)（无论数组是否有序，都需要进行完整的比较和交换）
  • 最好情况：O(n²)（即使数组已经有序，仍然需要进行完整的比较）
  • 平均情况：O(n²)

空间复杂度：

  • O(1)（原地排序，不需要额外空间）

选择排序的特点：

  1. 简单直观：实现简单，易于理解和实现。
  2. 不稳定排序：选择排序是不稳定的排序算法，可能会改变相同元素的相对顺序。
  3. 适合小规模数据：对于小规模数据，选择排序的效率尚可，但对于大规模数据效率较低。

优化版本：

选择排序的优化空间较小，但可以通过同时选择最小和最大元素来减少外层循环的次数。

// 优化版本：同时选择最小和最大元素
void selectionSortOptimized(int arr[], int n) {int i, j, min_idx, max_idx;for (i = 0; i < n / 2; i++) {min_idx = i;max_idx = i;// 在未排序部分中找到最小和最大元素的索引for (j = i + 1; j < n - i; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}if (arr[j] > arr[max_idx]) {max_idx = j;}}// 将最小元素放到前面if (min_idx != i) {swap(&arr[min_idx], &arr[i]);}// 如果最大元素的位置被影响，需要更新max_idxif (max_idx == i) {max_idx = min_idx;}// 将最大元素放到后面if (max_idx != n - i - 1) {swap(&arr[max_idx], &arr[n - i - 1]);}}
}

选择排序虽然简单，但在实际应用中效率较低，通常用于教学或小规模数据的排序。对于大规模数据，更高效的排序算法（如快速排序、归并排序等）更为适用。

归并排序

归并排序（Merge Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略。它的核心思想是将数组分成两个子数组，分别对子数组进行排序，然后将排序后的子数组合并成一个有序数组。以下是使用C语言实现数组的归并排序的代码：

归并排序代码实现

#include <stdio.h>
#include <stdlib.h>// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {int i, j, k;int n1 = mid - left + 1;  // 左子数组的大小int n2 = right - mid;     // 右子数组的大小// 创建临时数组int* L = (int*)malloc(n1 * sizeof(int));  // 左子数组int* R = (int*)malloc(n2 * sizeof(int));  // 右子数组// 将数据复制到临时数组for (i = 0; i < n1; i++) {L[i] = arr[left + i];}for (j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}// 合并临时数组到原数组i = 0;  // 左子数组的索引j = 0;  // 右子数组的索引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++;}// 释放临时数组的内存free(L);free(R);
}// 归并排序的递归函数
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;  // 计算中间位置// 递归地对左子数组和右子数组进行排序mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并两个有序子数组merge(arr, left, mid, right);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);mergeSort(arr, 0, n - 1);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. merge函数：
    • 合并两个有序子数组L和R到原数组arr中。
    • 使用临时数组存储子数组的数据，然后按顺序合并到原数组。
  2. mergeSort函数：
    • 递归地将数组分成两个子数组，分别对子数组进行排序。
    • 调用merge函数合并两个有序子数组。
  3. printArray函数：用于打印数组的内容。
  4. main函数：测试归并排序的实现。

运行结果：

原始数组: 
12 11 13 5 6 7 
排序后的数组: 
5 6 7 11 12 13

时间复杂度：

  • 最坏情况：O(n log n)
  • 最好情况：O(n log n)
  • 平均情况：O(n log n)

空间复杂度：

  • O(n)（需要额外的临时数组存储数据）

归并排序的特点：

  1. 稳定排序：归并排序是稳定的排序算法，相同元素的相对顺序不会改变。
  2. 适合大规模数据：归并排序的时间复杂度为O(n log n)，适合处理大规模数据。
  3. 分治法思想：通过递归将问题分解为更小的子问题，然后合并结果。

优化版本：

归并排序可以通过以下方式优化：

  1. 小规模数据使用插入排序：当子数组规模较小时，插入排序的效率更高。
  2. 避免频繁的内存分配：可以预先分配一个临时数组，避免在每次合并时分配内存。
// 优化版本：预先分配临时数组
void mergeSortOptimized(int arr[], int left, int right, int* temp) {if (left < right) {int mid = left + (right - left) / 2;// 递归地对左子数组和右子数组进行排序mergeSortOptimized(arr, left, mid, temp);mergeSortOptimized(arr, mid + 1, right, temp);// 合并两个有序子数组merge(arr, left, mid, right);}
}

归并排序是一种非常高效的排序算法，尤其适用于需要稳定排序的场景或处理大规模数据。

堆排序

堆排序（Heap Sort）是一种基于二叉堆（Binary Heap）数据结构的排序算法。它的核心思想是将数组构建成一个最大堆（或最小堆），然后逐步将堆顶元素（最大值或最小值）与堆的最后一个元素交换，并调整堆，直到整个数组有序。以下是使用C语言实现数组的堆排序的代码：

堆排序代码实现

#include <stdio.h>// 交换两个元素的值
void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp;
}// 调整堆，使其满足最大堆的性质
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) {swap(&arr[i], &arr[largest]);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--) {swap(&arr[0], &arr[i]);  // 将堆顶元素与堆的最后一个元素交换heapify(arr, i, 0);      // 调整堆，使其满足最大堆的性质}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);heapSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. swap函数：用于交换两个元素的值。
  2. heapify函数：
    • 调整堆，使其满足最大堆的性质。
    • 从根节点开始，比较根节点与其左右子节点，找到最大值。
    • 如果最大值不是根节点，交换根节点和最大值，并递归调整堆。
  3. heapSort函数：
    • 构建最大堆：从最后一个非叶子节点开始，逐步调整堆。
    • 逐步将堆顶元素（最大值）与堆的最后一个元素交换，并调整堆。
  4. printArray函数：用于打印数组的内容。
  5. main函数：测试堆排序的实现。

运行结果：

原始数组: 
12 11 13 5 6 7 
排序后的数组: 
5 6 7 11 12 13

时间复杂度：

  • 建堆过程：O(n)
  • 每次调整堆：O(log n)
  • 总时间复杂度：O(n log n)

空间复杂度：

  • O(1)（原地排序，不需要额外空间）

堆排序的特点：

  1. 不稳定排序：堆排序是不稳定的排序算法，可能会改变相同元素的相对顺序。
  2. 适合大规模数据：堆排序的时间复杂度为O(n log n)，适合处理大规模数据。
  3. 基于二叉堆：利用二叉堆的性质实现排序。

优化版本：

堆排序的优化空间较小，但可以通过以下方式改进：

  1. 使用最小堆：如果需要升序排序，可以使用最小堆。
  2. 减少交换次数：在调整堆时，可以减少不必要的交换操作。

堆排序是一种高效的排序算法，尤其适用于需要原地排序的场景或处理大规模数据。

计数排序

计数排序（Counting Sort）是一种非比较型整数排序算法。它的核心思想是通过统计数组中每个元素的出现次数，然后根据统计结果将元素放回正确的位置。计数排序适用于元素范围较小且已知的情况。以下是使用C语言实现数组的计数排序的代码：

计数排序代码实现

#include <stdio.h>
#include <stdlib.h>// 计数排序函数
void countingSort(int arr[], int n) {// 找到数组中的最大值int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}// 创建计数数组，并初始化为0int* count = (int*)calloc(max + 1, sizeof(int));// 统计每个元素的出现次数for (int i = 0; i < n; i++) {count[arr[i]]++;}// 将计数数组转换为前缀和数组for (int i = 1; i <= max; i++) {count[i] += count[i - 1];}// 创建输出数组int* output = (int*)malloc(n * sizeof(int));// 从后向前遍历原数组，将元素放入输出数组的正确位置for (int i = n - 1; i >= 0; i--) {output[count[arr[i]] - 1] = arr[i];count[arr[i]]--;}// 将输出数组的内容复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(count);free(output);
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {4, 2, 2, 8, 3, 3, 1};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);countingSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. countingSort函数：
    • 找到数组中的最大值，确定计数数组的大小。
    • 创建计数数组，统计每个元素的出现次数。
    • 将计数数组转换为前缀和数组，表示每个元素在输出数组中的位置。
    • 从后向前遍历原数组，将元素放入输出数组的正确位置。
    • 将输出数组的内容复制回原数组。
  2. printArray函数：用于打印数组的内容。
  3. main函数：测试计数排序的实现。

运行结果：

原始数组: 
4 2 2 8 3 3 1 
排序后的数组: 
1 2 2 3 3 4 8

时间复杂度：

  • 时间复杂度：O(n + k)，其中n是数组长度，k是数组中元素的最大值。
  • 空间复杂度：O(n + k)（需要额外的计数数组和输出数组）。

计数排序的特点：

  1. 非比较排序：计数排序不直接比较元素的大小，而是通过统计元素的出现次数进行排序。
  2. 稳定排序：计数排序是稳定的排序算法，相同元素的相对顺序不会改变。
  3. 适合小范围整数排序：计数排序适用于元素范围较小且已知的情况。

优化版本：

计数排序的优化可以通过以下方式实现：

  1. 减少空间占用：如果元素范围较大，可以使用哈希表或其他方法减少计数数组的大小。
  2. 处理负数：如果需要处理负数，可以将数组中的元素统一加上一个偏移量，使其变为非负数。

以下是处理负数的优化版本：

void countingSortWithNegative(int arr[], int n) {// 找到数组中的最小值和最大值int min = arr[0], max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < min) {min = arr[i];}if (arr[i] > max) {max = arr[i];}}// 计算偏移量int range = max - min + 1;// 创建计数数组，并初始化为0int* count = (int*)calloc(range, sizeof(int));// 统计每个元素的出现次数for (int i = 0; i < n; i++) {count[arr[i] - min]++;}// 将计数数组转换为前缀和数组for (int i = 1; i < range; i++) {count[i] += count[i - 1];}// 创建输出数组int* output = (int*)malloc(n * sizeof(int));// 从后向前遍历原数组，将元素放入输出数组的正确位置for (int i = n - 1; i >= 0; i--) {output[count[arr[i] - min] - 1] = arr[i];count[arr[i] - min]--;}// 将输出数组的内容复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(count);free(output);
}

计数排序是一种高效的排序算法，尤其适用于元素范围较小的情况。对于元素范围较大的情况，可以考虑使用其他排序算法（如快速排序或归并排序）。

基数排序

基数排序（Radix Sort）是一种非比较型整数排序算法。它的核心思想是将整数按位数切割成不同的数字，然后按每个位数分别进行排序（通常使用计数排序或桶排序作为子排序算法）。基数排序适用于整数或字符串的排序。以下是使用C语言实现数组的基数排序的代码：

基数排序代码实现

#include <stdio.h>
#include <stdlib.h>// 获取数组中的最大值
int getMax(int arr[], int n) {int max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > max) {max = arr[i];}}return max;
}// 使用计数排序对数组按指定位数进行排序
void countingSort(int arr[], int n, int exp) {int* output = (int*)malloc(n * sizeof(int));  // 输出数组int count[10] = {0};  // 计数数组，初始化为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]--;}// 将输出数组的内容复制回原数组for (int i = 0; i < n; i++) {arr[i] = output[i];}// 释放动态分配的内存free(output);
}// 基数排序函数
void radixSort(int arr[], int n) {int max = getMax(arr, n);  // 获取数组中的最大值// 对每个位数进行计数排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSort(arr, n, exp);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);radixSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. getMax函数：获取数组中的最大值，用于确定需要排序的位数。
  2. countingSort函数：
    • 对数组按指定位数（exp）进行计数排序。
    • 使用计数数组统计每个数字出现的次数，并将其转换为前缀和数组。
    • 从后向前遍历原数组，将元素放入输出数组的正确位置。
  3. radixSort函数：
    • 获取数组中的最大值，确定需要排序的位数。
    • 对每个位数调用countingSort函数进行排序。
  4. printArray函数：用于打印数组的内容。
  5. main函数：测试基数排序的实现。

运行结果：

原始数组: 
170 45 75 90 802 24 2 66 
排序后的数组: 
2 24 45 66 75 90 170 802

时间复杂度：

  • 时间复杂度：O(d * (n + k))，其中d是最大数字的位数，n是数组长度，k是基数（通常为10）。
  • 空间复杂度：O(n + k)（需要额外的计数数组和输出数组）。

基数排序的特点：

  1. 非比较排序：基数排序不直接比较元素的大小，而是通过按位数排序。
  2. 稳定排序：基数排序是稳定的排序算法，相同元素的相对顺序不会改变。
  3. 适合整数或字符串排序：基数排序适用于整数或固定长度的字符串排序。

优化版本：

基数排序的优化空间较小，但可以通过以下方式改进：

  1. 使用桶排序：在某些情况下，可以使用桶排序代替计数排序作为子排序算法。
  2. 处理负数：如果需要处理负数，可以将数组分为正数和负数两部分，分别进行基数排序。

基数排序是一种高效的排序算法，尤其适用于整数或字符串的排序场景。

桶排序

桶排序（Bucket Sort）是一种分布式排序算法，它将数组分到有限数量的桶中，每个桶再分别排序（通常使用插入排序或其他排序算法），最后将各个桶中的元素合并成有序数组。以下是使用C语言实现数组的桶排序的代码：

桶排序代码实现

#include <stdio.h>
#include <stdlib.h>// 定义桶的数量
#define BUCKET_SIZE 10// 定义链表节点
typedef struct Node {float data;struct Node* next;
} Node;// 插入节点到链表中（按升序插入）
Node* insert(Node* head, float value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL;if (head == NULL || head->data >= value) {newNode->next = head;head = newNode;} else {Node* current = head;while (current->next != NULL && current->next->data < value) {current = current->next;}newNode->next = current->next;current->next = newNode;}return head;
}// 桶排序函数
void bucketSort(float arr[], int n) {// 创建桶数组Node* buckets[BUCKET_SIZE] = {NULL};// 将元素分配到桶中for (int i = 0; i < n; i++) {int bucketIndex = (int)(arr[i] * BUCKET_SIZE);  // 计算桶的索引buckets[bucketIndex] = insert(buckets[bucketIndex], arr[i]);}// 将桶中的元素合并到原数组int index = 0;for (int i = 0; i < BUCKET_SIZE; i++) {Node* current = buckets[i];while (current != NULL) {arr[index++] = current->data;current = current->next;}}
}// 打印数组
void printArray(float arr[], int size) {for (int i = 0; i < size; i++) {printf("%.2f ", arr[i]);}printf("\n");
}// 主函数
int main() {float arr[] = {0.42, 0.32, 0.75, 0.12, 0.89, 0.63, 0.25, 0.55};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);bucketSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. Node结构体：定义链表节点，用于存储桶中的元素。
  2. insert函数：
    • 将元素按升序插入到链表中。
    • 如果链表为空或当前元素小于链表头节点，则插入到链表头部。
    • 否则，遍历链表找到合适的插入位置。
  3. bucketSort函数：
    • 创建桶数组，每个桶是一个链表。
    • 将数组中的元素分配到对应的桶中。
    • 对每个桶中的元素进行排序（通过插入排序实现）。
    • 将各个桶中的元素合并到原数组。
  4. printArray函数：用于打印数组的内容。
  5. main函数：测试桶排序的实现。

运行结果：

原始数组: 
0.42 0.32 0.75 0.12 0.89 0.63 0.25 0.55 
排序后的数组: 
0.12 0.25 0.32 0.42 0.55 0.63 0.75 0.89

时间复杂度：

  • 平均情况：O(n + k)，其中n是数组长度，k是桶的数量。
  • 最坏情况：O(n²)（当所有元素都分配到同一个桶时）。
  • 最好情况：O(n)（当元素均匀分布在各个桶中时）。

空间复杂度：

  • O(n + k)（需要额外的桶数组和链表节点）。

桶排序的特点：

  1. 分布式排序：将元素分配到多个桶中，分别排序后再合并。
  2. 适合均匀分布的数据：当元素均匀分布在各个桶中时，桶排序的效率较高。
  3. 稳定排序：如果使用的子排序算法是稳定的，桶排序也是稳定的。

优化版本：

桶排序的优化可以通过以下方式实现：

  1. 动态调整桶的数量：根据数据的分布动态调整桶的数量，避免所有元素都分配到同一个桶中。
  2. 使用更高效的子排序算法：例如使用快速排序或归并排序代替插入排序。

桶排序是一种高效的排序算法，尤其适用于数据分布均匀的场景。对于非均匀分布的数据，桶排序的性能可能会下降。

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它的核心思想是通过将数组分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的间隔，最终对整个数组进行一次插入排序。希尔排序的时间复杂度优于普通的插入排序。以下是使用C语言实现数组的希尔排序的代码：

希尔排序代码实现

#include <stdio.h>// 希尔排序函数
void shellSort(int arr[], int n) {// 初始间隔（gap）为数组长度的一半，逐步缩小间隔for (int gap = n / 2; gap > 0; gap /= 2) {// 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];  // 当前需要插入的元素int j;// 将比temp大的元素向后移动for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;  // 插入temp到正确位置}}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 主函数
int main() {int arr[] = {12, 34, 54, 2, 3};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, n);shellSort(arr, n);printf("排序后的数组: \n");printArray(arr, n);return 0;
}

代码说明：

  1. shellSort函数：
    • 初始间隔（gap）为数组长度的一半，逐步缩小间隔。
    • 对每个子序列进行插入排序。
    • 将比当前元素大的元素向后移动，直到找到当前元素的正确位置。
  2. printArray函数：用于打印数组的内容。
  3. main函数：测试希尔排序的实现。

运行结果：

原始数组: 
12 34 54 2 3 
排序后的数组: 
2 3 12 34 54

时间复杂度：

  • 最坏情况：O(n²)（取决于间隔序列的选择）。
  • 平均情况：O(n log n) 到 O(n^(3/2))。
  • 最好情况：O(n log n)。

空间复杂度：

  • O(1)（原地排序，不需要额外空间）。

希尔排序的特点：

  1. 改进的插入排序：通过分组插入排序，减少了元素的移动次数。
  2. 不稳定排序：希尔排序是不稳定的排序算法，可能会改变相同元素的相对顺序。
  3. 适合中等规模数据：希尔排序的效率高于普通的插入排序，适合中等规模的数据排序。

优化版本：

希尔排序的性能取决于间隔序列的选择。常见的间隔序列有：

  1. 希尔原始序列：gap = n / 2, gap /= 2。
  2. Hibbard序列：gap = 2^k - 1。
  3. Sedgewick序列：gap = 9 * 4^i - 9 * 2^i + 1 或 gap = 4^i + 3 * 2^i + 1。

以下是使用Hibbard序列的优化版本：

// 使用Hibbard序列的希尔排序
void shellSortHibbard(int arr[], int n) {// 计算Hibbard序列的最大值int k = 1;while ((1 << k) - 1 < n) {k++;}// 使用Hibbard序列作为间隔for (int gap = (1 << k) - 1; gap > 0; gap = (1 << (--k)) - 1) {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;}}
}

希尔排序是一种高效的排序算法，尤其适用于中等规模数据的排序。通过选择合适的间隔序列，可以进一步提高其性能。

总结

以下是常见排序算法的比较表格，包括时间复杂度、空间复杂度、稳定性以及适用场景等信息：

排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度是否稳定适用场景
QuickO(n log n)O(n²)O(n log n)O(log n)不稳定大规模数据，通用排序
BubbleO(n²)O(n²)O(n)O(1)稳定小规模数据，教学用途
InsertO(n²)O(n²)O(n)O(1)稳定小规模或部分有序数据
SelectO(n²)O(n²)O(n²)O(1)不稳定小规模数据，简单实现
MergeO(n log n)O(n log n)O(n log n)O(n)稳定大规模数据，稳定排序需求
HeapO(n log n)O(n log n)O(n log n)O(1)不稳定大规模数据，原地排序需求
CountO(n + k)O(n + k)O(n + k)O(n + k)稳定小范围整数排序
RadixO(d(n + k))O(d(n + k))O(d(n + k))O(n + k)稳定整数或字符串排序，位数较小
BucketO(n + k)O(n²)O(n)O(n + k)稳定均匀分布的数据
ShellO(n log n)O(n²)O(n log n)O(1)不稳定中等规模数据，改进的插入排序

表格说明：

  1. 时间复杂度：
    • 平均：算法在大多数情况下的性能。
    • 最坏：算法在最差情况下的性能。
    • 最好：算法在最优情况下的性能。
  2. 空间复杂度：算法所需的额外空间。
  3. 稳定性：排序后相同元素的相对顺序是否保持不变。
  4. 适用场景：算法最适合的应用场景。

总结：

  • Quick Sort：通用高效，适合大规模数据，但不稳定。
  • Bubble Sort：简单但效率低，适合小规模数据或教学用途。
  • Insertion Sort：适合小规模或部分有序数据，稳定。
  • Selection Sort：简单但效率低，适合小规模数据。
  • Merge Sort：稳定且高效，适合大规模数据，但需要额外空间。
  • Heap Sort：原地排序，适合大规模数据，但不稳定。
  • Counting Sort：适合小范围整数排序，稳定。
  • Radix Sort：适合整数或字符串排序，稳定。
  • Bucket Sort：适合均匀分布的数据，稳定。
  • Shell Sort：改进的插入排序，适合中等规模数据。

根据具体需求选择合适的排序算法可以提高程序的效率。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/12067.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

在线知识库的构建策略提升组织信息管理效率与决策能力

在线知识库的构建策略提升组织信息管理效率与决策能力

内容概要 在线知识库作为现代企业信息管理的重要组成部分&#xff0c;具有显著的定义与重要性。它不仅为组织提供了一个集中存储与管理知识的平台&#xff0c;还能够有效提升信息检索的效率&#xff0c;促进知识的创新和利用。通过这样的知识库&#xff0c;企业可以更好地应对…
阅读更多...
【汽车电子软件架构】AutoSAR从放弃到入门专栏导读

【汽车电子软件架构】AutoSAR从放弃到入门专栏导读

本文是汽车电子软件架构&#xff1a;AutoSAR从放弃到入门专栏的导读篇。文章延续专栏文章的一贯作风&#xff0c;从概念与定义入手&#xff0c;希望读者能对AutoSAR架构有一个整体的认识&#xff0c;然后对专栏涉及的文章进行分类与链接。本文首先从AutoSAR汽车软件架构的概念&…
阅读更多...
DeepSeek-R1：通过强化学习激励大型语言模型（LLMs）的推理能力

DeepSeek-R1：通过强化学习激励大型语言模型（LLMs）的推理能力

摘要 我们推出了第一代推理模型&#xff1a;DeepSeek-R1-Zero和DeepSeek-R1。DeepSeek-R1-Zero是一个未经监督微调&#xff08;SFT&#xff09;作为初步步骤&#xff0c;而是通过大规模强化学习&#xff08;RL&#xff09;训练的模型&#xff0c;展现出卓越的推理能力。通过强…
阅读更多...
响应式编程与协程

响应式编程与协程

响应式编程与协程的比较 响应式编程的弊端虚拟线程Java线程内核线程的局限性传统线程池的demo虚拟线程的demo 响应式编程的弊端 前面用了几篇文章介绍了响应式编程&#xff0c;它更多的使用少量线程实现线程间解耦和异步的作用&#xff0c;如线程的Reactor模型&#xff0c;主要…
阅读更多...
本地部署DeepSeek-R1模型（新手保姆教程）

本地部署DeepSeek-R1模型（新手保姆教程）

背景 最近deepseek太火了&#xff0c;无数的媒体都在报道&#xff0c;很多人争相着想本地部署试验一下。本文就简单教学一下&#xff0c;怎么本地部署。 首先大家要知道&#xff0c;使用deepseek有三种方式&#xff1a; 1.网页端或者是手机app直接使用 2.使用代码调用API …
阅读更多...
当WebGIS遇到智慧文旅-以长沙市不绕路旅游攻略为例

当WebGIS遇到智慧文旅-以长沙市不绕路旅游攻略为例

目录 前言 一、旅游数据组织 1、旅游景点信息 2、路线时间推荐 二、WebGIS可视化实现 1、态势标绘实现 2、相关位置展示 三、成果展示 1、第一天旅游路线 2、第二天旅游路线 3、第三天旅游路线 4、交通、订票、住宿指南 四、总结 前言 随着信息技术的飞速发展&…
阅读更多...
93，【1】buuctf web [网鼎杯 2020 朱雀组]phpweb

93，【1】buuctf web [网鼎杯 2020 朱雀组]phpweb

进入靶场 页面一直在刷新 在 PHP 中&#xff0c;date() 函数是一个非常常用的处理日期和时间的函数&#xff0c;所以应该用到了 再看看警告的那句话 Warning: date(): It is not safe to rely on the systems timezone settings. You are *required* to use the date.timez…
阅读更多...
如何在电脑上部署deepseek

如何在电脑上部署deepseek

由于免费的网页版经常显示服务器异常&#xff0c;并且每次打开网页麻烦&#xff0c;我们可以采用电脑部署的方法&#xff0c;V3和V2现在都很便宜&#xff0c;试了一下问了一下午问题也才0.1&#xff0c;而且现在注册就送14元&#xff0c;心动不如行动&#xff0c;快来薅羊毛&am…
阅读更多...
SmartPipe完成新一轮核心算法升级

SmartPipe完成新一轮核心算法升级

1. 增加对低质量轴段的修正 由于三维图纸导出造成某些轴段精度较差&#xff0c;部分管路段的轴线段不满足G1连续&#xff0c;SmartPipe采用算法对这种情况进行了修正&#xff0c;保证轴段在一定精度范围内光滑连续。 2. 优化对中文路径的处理 SmartPipeBatch批处理版本优化…
阅读更多...
2.3学习总结

2.3学习总结

今天做了下上次测试没做出来的题目&#xff0c;作业中做了一题&#xff0c;看了下二叉树&#xff08;一脸懵B&#xff09; P2240&#xff1a;部分背包问题 先求每堆金币的性价比&#xff08;价值除以重量&#xff09;&#xff0c;将这些金币由性价比从高到低排序。 对于排好…
阅读更多...
四川正熠法律咨询有限公司正规吗可信吗？

四川正熠法律咨询有限公司正规吗可信吗？

在纷繁复杂的法律环境中&#xff0c;寻找一家值得信赖的法律服务机构是每一个企业和个人不可或缺的需求。四川正熠法律咨询有限公司&#xff0c;作为西南地区备受瞩目的法律服务提供者&#xff0c;以其专注、专业和高效的法律服务&#xff0c;成为众多客户心中的首选。 正熠法…
阅读更多...
【leetcode练习·二叉树拓展】快速排序详解及应用

【leetcode练习·二叉树拓展】快速排序详解及应用

本文参考labuladong算法笔记[拓展&#xff1a;快速排序详解及应用 | labuladong 的算法笔记] 1、算法思路 首先我们看一下快速排序的代码框架&#xff1a; def sort(nums: List[int], lo: int, hi: int):if lo > hi:return# 对 nums[lo..hi] 进行切分# 使得 nums[lo..p-1]…
阅读更多...
FPGA学习篇——开篇之作

FPGA学习篇——开篇之作

今天正式开始学FPGA啦&#xff0c;接下来将会编写FPGA学习篇来记录自己学习FPGA 的过程&#xff01; 今天是大年初六&#xff0c;简单学一下FPGA的相关概念叭叭叭&#xff01; 一&#xff1a;数字系统设计流程 一个数字系统的设计分为前端设计和后端设计。在我看来&#xff0…
阅读更多...
DeepSeek R1 简易指南：架构、本地部署和硬件要求

DeepSeek R1 简易指南：架构、本地部署和硬件要求

DeepSeek 团队近期发布的DeepSeek-R1技术论文展示了其在增强大语言模型推理能力方面的创新实践。该研究突破性地采用强化学习&#xff08;Reinforcement Learning&#xff09;作为核心训练范式&#xff0c;在不依赖大规模监督微调的前提下显著提升了模型的复杂问题求解能力。 技…
阅读更多...
Vue3学习笔记-模板语法和属性绑定-2

Vue3学习笔记-模板语法和属性绑定-2

一、文本插值 使用{ {val}}放入变量&#xff0c;在JS代码中可以设置变量的值 <template><p>{{msg}}</p> </template> <script> export default {data(){return {msg: 文本插值}} } </script> 文本值可以是字符串&#xff0c;可以是布尔…
阅读更多...
Android学习19 -- 手搓App

Android学习19 -- 手搓App

1 前言 之前工作中&#xff0c;很多时候要搞一个简单的app去验证底层功能&#xff0c;Android studio又过于重型&#xff0c;之前用gradle&#xff0c;被版本匹配和下载外网包折腾的堪称噩梦。所以搞app都只有找应用的同事帮忙。一直想知道一些简单的app怎么能手搓一下&#x…
阅读更多...
深度解读 Docker Swarm

深度解读 Docker Swarm

一、引言 随着业务规模的不断扩大和应用复杂度的增加，容器集群管理的需求应运而生。如何有效地管理和调度大量的容器，确保应用的高可用性、弹性伸缩和资源的合理分配，成为了亟待解决的问题。Docker Swarm 作为 Docker 官方推出的容器集群管理工具，正是在这样的背景下崭露头…
阅读更多...
centos stream 9 安装 libstdc++-static静态库

centos stream 9 安装 libstdc++-static静态库

yum仓库中相应的镜像源没有打开&#xff0c;libstdc-static在CRB这个仓库下&#xff0c;但是查看/etc/yum.repos.d/centos.repo&#xff0c;发现CRB镜像没有开启。 解决办法 如下图开启CRB镜像&#xff0c; 然后执行 yum makecache yum install glibc-static libstdc-static…
阅读更多...
玉米苗和杂草识别分割数据集labelme格式1997张3类别

玉米苗和杂草识别分割数据集labelme格式1997张3类别

数据集格式&#xff1a;labelme格式(不包含mask文件&#xff0c;仅仅包含jpg图片和对应的json文件) 图片数量(jpg文件个数)&#xff1a;1997 标注数量(json文件个数)&#xff1a;1997 标注类别数&#xff1a;3 标注类别名称:["corn","weed","Bean…
阅读更多...
Docker入门篇（Docker基础概念与Linux安装教程）

Docker入门篇（Docker基础概念与Linux安装教程）

目录 一、什么是Docker、有什么作用 二、Docker与虚拟机(对比) 三、Docker基础概念 四、CentOS安装Docker 一、从零认识Docker、有什么作用 1.项目部署可能的问题&#xff1a; 大型项目组件较多&#xff0c;运行环境也较为复杂&#xff0c;部署时会碰到一些问题&#xff1…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023