十种基础排序算法(C语言实现，带源码)(有具体排序例子，适合学习理解)

学习了十种常见的排序方法，此文章针对所学的排序方法进行整理（通过C语言完成排序）。
参考内容：
https://blog.csdn.net/mwj327720862/article/details/80498455
https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，属于交换排序的一种。通过重复遍历待排序的列表，依次比较相邻的两个元素并根据大小进行交换。

1. 从左到右依次比较相邻的两个元素，如果前面的元素大于后面的元素，就交换它们的位置。
2. 重复此过程，将最大（或最小）的元素移动到当前未排序部分的末尾。
3. 对未排序部分重复上述步骤，直到所有元素都排好序。

时间复杂度（平均）：$O(n^2)$

空间复杂度：$O(1)$

如图中数组排序，用了5轮成功排好序，但实际运行了8轮（不判断数组已经有序的情况下），以下是排序实现代码。

#include <stdio.h>int bubbleSort(int arr[],int size)
{for(int i = 0; i < size - 1; i++){for(int j = 0; j <size - i - 1;j++){if(arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}void printArr(int arr[], int size)
{for(int i = 0; i < size; i++){printf("%-5d",arr[i]);}printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);bubbleSort(arr,size);printArr(arr,size);return 0;
}

2. 选择排序（Selection Sort）

选择排序是一种简单排序算法，它的基本思想是通过多次选择，将没排序部分中的最小（或最大）元素找到，将其放在已排序部分的末尾（或开头）。

1. 从未排序部分中找到最小（或最大）的元素。
2. 将该元素与未排序部分的第一个元素交换，完成一轮排序。
3. 将剩余未排序部分重复上述步骤，直到所有元素都排序完成。

时间复杂度（平均）：$O(n^2)$

空间复杂度：$O(1)$

#include <stdio.h>int selectSort(int arr[],int size)
{int i,j,k;for(i = 0; i < size - 1; i++){k = i;for(j = i + 1; j < size; j++){if(arr[k] > arr[j])k = j;}int temp = arr[k];arr[k] = arr[i];arr[i] = temp;}
}int printArr(int arr[],int size)
{for(int i = 0; i < size; i++){printf("%-5d",arr[i]);}printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);selectSort(arr,size);printArr(arr,size);return 0;
}

3. 插入排序（Insert Sort）

插入排序是一种简单的排序算法，它的基本思想是：将待排序的数组划分为已排序部分和未排序部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置，直到整个数组变得有序。

1. 从第二个元素开始，依次将未排序部分的元素插入到已排序部分的合适位置，使已排序部分始终有序。
2. 重复上述步骤，直到所有元素都排好序。

时间复杂度（平均）：$O(n^2)$

空间复杂度：$O(1)$

#include <stdio.h>int insertSort(int arr[],int size)
{int i,j;for( i = 1; i < size; i++){int temp = arr[i];for(j = i; j > 0 && arr[j - 1] > temp; j--){arr[j] = arr[j - 1]; }arr[j] = temp;}
}void printArr(int arr[], int size)
{for(int i = 0; i < size; i++)printf("%-5d",arr[i]);printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);insertSort(arr,size);printArr(arr,size);return 0;
}

4. 希尔排序（Shell Sort）

希尔排序是一种基于插入排序的高级排序算法，它的基本思想是通过逐步减少数据的间隔（gap），将数据分组并排序，从而逐步逼近整体有序；它的核心思想是分组插入排序，通过对数据进行预排序以减少逆序对，从而优化了插入排序的效率。

1. 将数组分成多个间隔为gap的子序列（每隔gap个元素视为一个分组）。
2. 对每个子序列进行插入排序，使子序列内局部有序。
3. 减小gap值，重复步骤 1 和 2，直到gap=1，此时对整个数组进行最后一次插入排序。
4. 最终数组完全有序

时间复杂度（平均）：介于$O(nlogn)$和$O(n^2)$之间

空间复杂度：$O(1)$

#include <stdio.h>int shellSort(int arr[],int size)
{int i,j,temp,increment;for(increment = size / 2; increment > 0; increment /= 2){for(i = increment; i < size; i++){temp = arr[i];for(j = i - increment; j >= 0 && arr[j] > temp; j -= increment){arr[j + increment] = arr[j];}arr[j + increment] = temp;}}
}void printArr(int arr[],int size)
{for(int i = 0; i < size; i++)printf("%-5d",arr[i]);printf("\n");}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);shellSort(arr,size);printArr(arr,size);return 0;
}

5. 归并排序（Merge Sort）

归并排序是一种分治算法，它通过将数组不断拆分成更小的子数组进行排序，并将排序后的子数组合并成一个有序的数组。它的主要思想是分而治之：

1. 分解：将数组递归地分成两半，直到每个子数组只有一个元素或为空。
2. 合并：将两个有序的子数组合并成一个更大的有序数组。

1. 将数组从中间拆分成两个子数组。
2. 递归地对左右两个子数组进行归并排序。
3. 合并两个有序子数组，使整个数组有序。

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

空间复杂度：$O(n)$（需要额外数组存储合并结果）

#include <stdio.h>
#include <stdlib.h>void merge(int arr[], int left, int mid, int right)
{int n1 = mid - left + 1;int n2 = right - mid;int *L = (int *)malloc(n1 * sizeof(int));int *R = (int *)malloc(n2 * sizeof(int));for(int i = 0; i < n1; i++)L[i] = arr[left + i];for(int i = 0; i < n2; i++)R[i] = arr[mid +i + 1];int 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 printArr(int arr[],int size)
{for(int i = 0; i < size; i++){printf("%-5d",arr[i]);}printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);mergeSort(arr,0,size - 1);printArr(arr,size);return 0;
}

6. 快速排序（Quick Sort）

快速排序是一种基于分治思想的高效排序算法。它通过选择一个基准值，将数组划分为两个部分：小于基准值的元素和大于基准值的元素，然后递归地对这两部分进行排序。

1. 选择基准值：从数组中选择一个基准值（通常是第一个元素、最后一个元素或者任意元素）
2. 分区：将数组重新排序，使所有小于基准值的元素位于基准值左侧，大于基准值的元素位于右侧
3. 递归排序：对基准值两侧的子数组继续递归快速排序
4. 重复上述步骤，直到有序

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

空间复杂度：$O(logn)$（递归栈空间）

#include <stdio.h>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);}
}void printArr(int arr[],int size)
{for(int i = 0; i < size; i++)printf("%-5d",arr[i]);printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);quickSort(arr,0,size-1);printArr(arr,size);return 0;
}

7. 堆排序（Heap Sort）

堆排序是一种基于堆结构的比较排序算法。堆是一颗完全二叉树，并且满足堆性质：

• 大顶堆：每个节点的值都大于或等于其左右子节点的值。
• 小顶堆：每个节点的值都小于或等于其左右子节点的值。

堆排序利用大顶堆的特性来实现升序排序（或小顶堆实现降序排序）（此处实现升序排序）

1. 构建初始堆：将数组是为完全二叉树，并调整其为大顶堆。
2. 交换堆顶和堆尾：堆顶元素是最大值，与最后一个元素交换，将最大值移到最终位置。
3. 调整堆：交换后，重新调整为大顶堆。
4. 重复步骤2、3。直到堆中只有一个元素

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

空间复杂度：$O(1)$

#include <stdio.h>void heapify(int arr[],int n,int i)
{int lastest = i;int left = 2 * i + 1;int right = 2 * i + 2;if(left < n && arr[left] > arr[lastest]){lastest = left;}if(right < n && arr[right] > arr[lastest]){lastest = right;}if(lastest != i){int temp = arr[lastest];arr[lastest] = arr[i];arr[i] = temp;heapify(arr,n,lastest);}
}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;){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;i--;heapify(arr,i,0);}
}void printArr(int arr[],int size)
{for(int i = 0; i < size; i++){printf("%-5d",arr[i]);}printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {1,3,7,5,4,6,2,9,8};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);heapSort(arr,size);printArr(arr,size);return 0;
}

8. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，适用于对整数或范围有限的离散数据进行排序。它通过统计每个元素出现的次数来确定元素在排序后的位置。它的核心思想是：

1. 统计每个元素的出现次数
2. 利用这些计数信息计算元素的位置索引
3. 根据索引将元素放入正确的位置，从而完成排序

1. 计算频率：

2. 找到数组中最大值和最小值，确定数值范围

3. 创建一个计数数组，记录每个值在原数组中出现次数

4. 累积计数：

将计数数组转换为累积计数数组，表示每个值在排序后的位置范围

3. 填充结果：

倒叙遍历原数组，根据累积计数数组将元素放到结果数组中，并更新计数数组

时间复杂度：$O(n+k)$：n是数组大小，k是数据范围

空间复杂度：$O(n+k)$：需要额外计数数组和结果数组

#include <stdio.h>
#include <stdlib.h>void countSort(int arr[],int size)
{int max = arr[0],min = arr[0];for(int i = 0; i < size; i++){if(arr[i] > max)max = arr[i];if(arr[i] < min)min = arr[i];}int len = max - min + 1;int *count = (int *)calloc(len,sizeof(int));for(int i = 0; i < size; i++){count[arr[i]-min]++;}for(int i = 1; i < len; i++){count[i] += count[i-1];}int *output = (int *)calloc(size,sizeof(int));for(int i = size - 1; i >= 0; i--){output[count[arr[i]-min]-1] = arr[i];}for(int i = 0; i < size; i++){arr[i] = output[i];}free(count);free(output);
}void printArr(int arr[],int size)
{for(int i = 0;i < size; i++)printf("%-5d",arr[i]);printf("\n");
}int main(int argc,char *argv[])
{int arr[] = {57, 31, 67, 89, 4, 12, 5, 54, 32, 63};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr,size);countSort(arr,size);printArr(arr,size);return 0;
}

9. 桶排序（Bucket Sort）

桶排序是一种基于分布的排序算法，它通过将数据分配到多个桶中，然后分别对每个桶中的数据进行排序，最后合并所有桶中的数据来完成排序。适用于输入数据分布均匀的情况，特别是当数据范围有限且可以被分成多个区间时，效率较高。

1. 分桶：根据数据范围，将数据分配到多个桶中，每个桶对应一个区间
2. 桶内排序：对每个桶中的数据分别进行排序（推荐插入排序）
3. 合并桶：依次合并每个桶中的数据

时间复杂度（平均）：$O(n+k+nlog(n/k))$

空间复杂度：$O(n+k)$

#include <stdio.h>
#include <stdlib.h>// 链表节点
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表中插入节点并保持排序顺序
void sortedInsert(Node** head, int data) {Node* newNode = createNode(data);if (*head == NULL || (*head)->data >= data) {newNode->next = *head;*head = newNode;} else {Node* current = *head;while (current->next != NULL && current->next->data < data) {current = current->next;}newNode->next = current->next;current->next = newNode;}
}// 桶排序函数
void bucketSort(int arr[], int size) {if (size <= 0) return;// 找到数组中的最大值和最小值int max = arr[0], min = arr[0];for (int i = 1; i < size; i++) {if (arr[i] > max) max = arr[i];if (arr[i] < min) min = arr[i];}int bucketCount = 5; // 假设有5个桶int range = (max - min + bucketCount) / bucketCount; // 每个桶存储的整数范围Node** buckets = (Node**)malloc(bucketCount * sizeof(Node*));for (int i = 0; i < bucketCount; i++) {buckets[i] = NULL;}// 将元素分配到对应的桶for (int i = 0; i < size; i++) {int bucketIndex = (arr[i] - min) / range;sortedInsert(&buckets[bucketIndex], arr[i]);}// 将桶内的元素合并回原数组int index = 0;for (int i = 0; i < bucketCount; i++) {Node* current = buckets[i];while (current != NULL) {arr[index++] = current->data;Node* temp = current;current = current->next;free(temp); // 释放链表节点}}free(buckets); // 释放桶数组
}void printArr(int arr[], int size) {for (int i = 0; i < size; i++) printf("%-5d", arr[i]);printf("\n");
}int main() {int arr[] = {21, 33, 17, 5, 44, 26, 32, 19, 38};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr, size);bucketSort(arr, size);printArr(arr, size);return 0;
}

10.基数排序（Radix Sort）

基数排序是一种非比较排序算法，通过按位对数据进行多轮排序来实现。它是一种稳定的排序算法，适用于整数或字符串等离散数据的排序。基数排序的核心思想是将数据拆分为多个位，按照位的优先级（从低位到高位或从高位到低位）依次进行排序。

1. 确定最大位数：找到数组中元素的最大数，决定排序的轮数

2. 按位排序：

3. 从最低为开始，对每一位进行排序

4. 使用稳定的排序算法（如计数排序）对当前位上的数字进行排序

5. 完成排序：

重复2，直到最高位

时间复杂度：$O(d\ast (n+k))$，其中d是位数，n是数据大小，k是基数

空间复杂度：$O(n+k)$

#include <stdio.h>
#include <stdlib.h>// 使用计数排序对数组的某一位进行排序
void countSort(int arr[], int size, int exp) {int output[size]; // 输出数组int count[10] = {0}; // 计数数组// 统计当前位数字的频率for (int i = 0; i < size; i++) {int digit = (arr[i] / exp) % 10;count[digit]++;}// 计算累积频率for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 按当前位数字将元素放入输出数组for (int i = size - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10;output[count[digit] - 1] = arr[i];count[digit]--;}// 将排序结果复制回原数组for (int i = 0; i < size; i++) {arr[i] = output[i];}
}// 基数排序主函数
void radixSort(int arr[], int size) {// 找到最大值，确定最高位int max = arr[0];for (int i = 1; i < size; i++) {if (arr[i] > max) {max = arr[i];}}// 从个位开始，对每一位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countSort(arr, size, exp);}
}void printArr(int arr[], int size) {for (int i = 0; i < size; i++) printf("%-5d", arr[i]);printf("\n");
}int main() {int arr[] = {1705, 43, 76, 90, 802, 24, 2, 66, 635};int size = sizeof(arr) / sizeof(arr[0]);printArr(arr, size);radixSort(arr, size);printArr(arr, size);return 0;
}