算法导论基础-几种排序算法总结

我是基于ChatGPT-turbo-3.5实现的AI助手，在此网站上负责整理和概括文章

这篇文章总结了几种常见的排序算法，包括插入排序、归并排序、堆排序、快速排序、计数排序、基数排序和桶排序。每种算法的最坏情况运行时间和平均情况/期望运行时间也有详细列出。文章中展示了每种算法的图示和C代码示例，以及对应的实现原理和步骤。其中，插入排序通过比较和移动元素实现排序，归并排序采用分治法，堆排序利用二叉树的性质进行排序，快速排序通过选择枢纽元素和分区实现排序，计数排序和基数排序则是对数字进行计数和分配桶进行排序，桶排序则是根据桶的数量将元素分类放入桶中再进行排序。

---

算法	最坏情况运行时间	平均情况 / 期望运行时间
插入排序	Θ(n²)	Θ(n²)
归并排序	Θ(nlgn)	Θ(nlgn)
堆排序	Θ(nlgn)	——
快速排序	Θ(n²)	Θ(nlgn)
计数排序	Θ(n+k)	Θ(n+k)
基数排序	Θ(d(n+k))	Θ(d(n+k))
桶排序	Θ(n²)	Θ(n)

# 1 插入排序算法

插入排序示意图：
插入排序图示

演示 C 代码：

	void insertionSort(int a[], int n) {
	for (int i = 1; i < n; ++i) {
	int value = a[i];
	int j = i - 1;
	while (j >= 0 && a[j] > value) {
	a[j + 1] = a[j];
	--j;
	}
	a[j + 1] = value;
	}
	}

# 2 归并排序算法（分治法）

归并排序图示：

演示 C 代码：

	void mergeSort(int a[], int n) {
	if (n <= 1) {
	return;
	}

	int mid = n / 2;
	int left[mid];
	int right[n - mid];

	for (int i = 0; i < mid; ++i) {
	left[i] = a[i];
	}

	for (int i = mid; i < n; ++i) {
	right[i - mid] = a[i];
	}

	mergeSort(left, mid);
	mergeSort(right, n - mid);
	merge(a, left, mid, right, n - mid);
	}

	void merge(int a[], int left[], int leftCount, int right[], int rightCount) {
	int i = 0, j = 0, k = 0;

	while (i < leftCount && j < rightCount) {
	if (left[i] <= right[j]) {
	a[k++] = left[i++];
	} else {
	a[k++] = right[j++];
	}
	}

	while (i < leftCount) {
	a[k++] = left[i++];
	}

	while (j < rightCount) {
	a[k++] = right[j++];
	}
	}

# 3 堆排序（二叉树）

建堆图示：

堆排序图示：
堆排序1
堆排序2
演示 C 代码：

	void heapSort(int a[], int n) {
	// 建立大顶堆
	buildMaxHeap(a, n);

	for (int i = n - 1; i > 0; --i) {
	// 将堆顶元素与末尾元素交换
	swap(a[0], a[i]);
	// 调整堆结构，排除末尾元素
	adjustHeap(a, 0, i - 1);
	}
	}

	void buildMaxHeap(int a[], int n) {
	for (int i = n / 2 - 1; i >= 0; --i) {
	adjustHeap(a, i, n - 1);
	}
	}

	void adjustHeap(int a[], int i, int end) {
	int child = i * 2 + 1;
	while (child <= end) {
	// 左右子节点中选取最大值
	if (child + 1 <= end && a[child] < a[child + 1]) {
	child++;
	}

	if (child <= end && a[i] < a[child]) {
	// 将子节点的值与父节点的值交换
	swap(a[i], a[child]);
	i = child;
	child = i * 2 + 1;
	} else {
	return;
	}
	}
	}

	void swap(int a, int b) {
	int temp = *a;
	a = b;
	*b = temp;
	}

# 4 计数排序

计数排序图示：

演示 C 代码：

	void countingSort(int a[], int n) {
	int min = a[0], max = a[0];
	for (int i = 1; i < n; ++i) {
	if (a[i] < min) {
	min = a[i];
	} else if (a[i] > max) {
	max = a[i];
	}
	}

	int count[max - min + 1];
	for (int i = 0; i <= max - min; ++i) {
	count[i] = 0;
	}

	for (int i = 0; i < n; ++i) {
	count[a[i] - min]++;
	}

	int i = 0;
	for (int j = min; j <= max; ++j) {
	while (count[j - min] > 0) {
	a[i++] = j;
	count[j - min]--;
	}
	}
	}

# 5 基于计数排序的基数排序

基数排序图示：

演示 C 代码：

	void radixSort(int a[], int n) {
	int max = a[0];
	for (int i = 1; i < n; ++i) {
	if (a[i] > max) {
	max = a[i];
	}
	}

	for (int exp = 1; exp <= max; exp *= 10) {
	int count[10];
	for (int i = 0; i < 10; ++i) {
	count[i] = 0;
	}

	for (int i = 0; i < n; ++i) {
	count[(a[i] / exp) % 10]++;
	}

	int i = 0;
	for (int j = 0; j < 10; ++j) {
	while (count[j] > 0) {
	a[i++] = j * exp;
	count[j]--;
	}
	}
	}
	}

# 6 桶排序

桶排序图示：

演示 C 代码：

	void bucketSort(int arr[], int n) {
	// 设置桶的数量
	int bucketCount = 10; // 假设元素范围为 0 到 99

	// 创建桶
	int buckets[bucketCount][]; // 存储桶

	// 初始化空桶
	for (int i = 0; i < bucketCount; ++i) {
	buckets[i] = (int )malloc(n sizeof(int)); // 为每个桶分配内存
	for (int j = 0; j < n; ++j) {
	buckets[i][j] = 0; // 初始化桶元素为 0
	}
	}

	// 将元素分配到桶中
	for (int i = 0; i < n; ++i) {
	int bucketIndex = arr[i] / bucketCount; // 计算桶索引
	buckets[bucketIndex][i % bucketCount] = arr[i]; // 将元素放入相应桶
	}

	// 对每个桶中的元素排序
	for (int i = 0; i < bucketCount; ++i) {
	int bucketSize = 0; // 非零元素计数器
	for (int j = 0; j < n; ++j) {
	if (buckets[i][j] != 0) { // 非零元素
	buckets[i][bucketSize++] = buckets[i][j]; // 移动非零元素到桶前面
	}
	}
	}

	// 合并桶中排序后的元素
	int index = 0;
	for (int i = 0; i < bucketCount; ++i) {
	for (int j = 0; j < n; ++j) {
	if (buckets[i][j] != 0) {
	arr[index++] = buckets[i][j]; // 将非零元素复制到排序数组
	}
	}
	}

	// 释放分配的内存
	for (int i = 0; i < bucketCount; ++i) {
	free(buckets[i]); // 释放每个桶的内存
	}
	}

	int main() {
	int arr[] = {5, 2, 4, 6, 1, 3};
	int n = sizeof(arr) / sizeof(arr[0]);

	printf("未排序数组：");
	for (int i = 0; i < n; ++i) {
	printf("%d ", arr[i]);
	}

	bucketSort(arr, n);

	printf("\n排序后的数组：");
	for (int i = 0; i < n; ++i) {
	printf("%d ", arr[i]);
	}

	return 0;
	}

# 7 快速排序

快速排序图示：
输入图片说明

演示 C 代码：

	void swap(int a, int b) {
	int temp = *a; // 临时变量用于存储要交换的值
	a = b; // 将 a 的值赋给 b
	*b = temp; // 将 temp 的值赋给 b
	}

	int partition(int arr[], int low, int high) {
	int pivot = arr[high]; // 选择最后一个元素作为枢纽元素
	int i = (low - 1); // 初始化 i 变量为 low - 1

	for (int j = low; j < high; j++) { // 从 low 循环到 high - 1
	if (arr[j] <= pivot) { // 如果当前元素小于或等于枢纽元素
	i++; //i 递增
	swap(&arr[i], &arr[j]); // 交换当前元素和 arr [i] 的值
	}
	}

	swap(&arr[i + 1], &arr[high]); // 将枢纽元素移到正确的位置
	return (i + 1); // 返回枢纽元素的位置
	}

	void quickSort(int arr[], int low, int high) {
	if (low < high) { // 如果 low 小于 high，则继续排序
	int pi = partition(arr, low, high); // 对数组进行分区，并返回枢纽元素的位置

	quickSort(arr, low, pi - 1); // 递归排序左子数组
	quickSort(arr, pi + 1, high); // 递归排序右子数组
	}
	}

	int main() {
	int arr[] = {5, 2, 4, 1, 3}; // 待排序数组
	int n = sizeof(arr) / sizeof(arr[0]); // 数组长度

	printf("未排序数组：");
	for (int i = 0; i < n; i++) {
	printf("%d ", arr[i]); // 输出未排序数组
	}

	quickSort(arr, 0, n - 1); // 对数组进行快速排序

	printf("\n排序后数组：");
	for (int i = 0; i < n; i++) {
	printf("%d ", arr[i]); // 输出排序后数组
	}

	return 0;
	}

# 1 插入排序算法

# 2 归并排序算法（分治法）

# 3 堆排序（二叉树）

# 4 计数排序

# 5 基于计数排序的基数排序

# 6 桶排序

# 7 快速排序

算法导论基础-几种递归式解法总结