赞
踩
上期回顾: 【数据结构|C语言版】栈和队列
个人主页:C_GUIQU
归属专栏:【数据结构(C语言版)学习】
各位小伙伴大家好!上次小编给大家讲解了数据结构中的树、二叉树和堆,接下来我们讲解一下排序算法中的四大排序!
直接插入排序(Straight Insertion Sort)是一种简单的排序算法,其主要思想是通过构建有序序列,对于未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入。该算法通常适用于少量数据的排序,时间复杂度为 (O(n^2))。
以下是直接插入排序的详细步骤:
初始化:
从第一个未排序元素开始:
寻找插入位置:
插入:
重复步骤2-4:
以下是直接插入排序的伪代码:
InsertionSort(A):
for i = 1 to length(A) - 1:
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j = j - 1
A[j + 1] = key
通过一个具体的例子来说明:
假设有一个数组 A = [5, 2, 4, 6, 1, 3]
最终排序后的数组为 [1, 2, 3, 4, 5, 6]
直接插入排序的特点:
直接插入排序适用于数据量较小或者部分有序的序列,当数据量较大时,性能较差。
希尔排序(Shell Sort)是插入排序的一种改进版本,它通过将整个待排序的记录序列分割成若干子序列分别进行直接插入排序,以便在整个序列基本有序时,再对全体记录进行一次直接插入排序。这种方法克服了直接插入排序的局限性,使得希尔排序的时间复杂度显著降低。
以下是希尔排序的详细步骤:
选择初始增量:
分组:
排序子序列:
减小增量:
以下是希尔排序的伪代码:
ShellSort(A):
n = length(A)
gap = n // 2
while gap > 0:
for i = gap to n - 1:
temp = A[i]
j = i
while j >= gap and A[j - gap] > temp:
A[j] = A[j - gap]
j = j - gap
A[j] = temp
gap = gap // 2
通过一个具体的例子来说明希尔排序的过程:
假设有一个数组 A = [9, 8, 3, 7, 5, 6, 4, 1]
初始状态:
第一次分组和排序:
缩小增量 gap = 2:
缩小增量 gap = 1:
希尔排序的特点:
希尔排序通过分组和多次插入排序,显著减少了数据移动的次数,适用于中等规模的数据排序。
选择排序(Selection Sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
以下是选择排序的详细步骤:
初始状态:
选择最小元素:
交换元素:
缩小范围:
以下是选择排序的伪代码:
SelectionSort(A):
n = length(A)
for i = 0 to n - 2:
min_index = i
for j = i + 1 to n - 1:
if A[j] < A[min_index]:
min_index = j
if min_index != i:
swap A[i] and A[min_index]
通过一个具体的例子来说明选择排序的过程:
假设有一个数组 A = [64, 25, 12, 22, 11]
初始状态:
第一次选择和交换:
第二次选择和交换:
第三次选择和交换:
第四次选择和交换:
最终排序后:
选择排序的特点:
选择排序适用于数据量较小的序列排序,当数据量较大时,性能较差。
在C语言中实现堆排序涉及到构建最大堆以及从最大堆中提取最大元素并重新调整堆的过程。下面是堆排序的完整实现代码:
堆排序的实现步骤
定义堆调整函数 heapify
:
构建最大堆:
排序过程:
C语言代码
#include <stdio.h> // 交换两个元素的宏 #define SWAP(x, y) { int temp = x; x = y; y = temp; } // 堆调整函数,维护最大堆性质 void heapify(int arr[], int n, int i) { int largest = i; // 初始化largest为根节点 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; // 如果largest不是根节点 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 n) { for (int i = 0; i < n; 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("Unsorted array: \n"); printArray(arr, n); heapSort(arr, n); printf("Sorted array: \n"); printArray(arr, n); return 0; }
代码说明
宏定义 SWAP
:
heapify
函数:
arr
是待调整的数组,n
是数组的长度,i
是当前节点的索引。heapSort
函数:
printArray
函数:
main
函数:
heapSort
函数进行排序,然后打印排序后的数组。特点
堆排序适用于需要保证较好最坏情况性能的排序场景。
冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的列表,比较相邻的元素并交换它们的位置,如果它们的顺序错误。遍历列表的工作是重复进行的,直到不需要再交换为止,也就是说列表已经排序完成。
以下是冒泡排序的详细步骤和在C语言中的实现:
遍历数组:
重复步骤1:
优化:
C语言实现代码
#include <stdio.h> // 冒泡排序函数 void bubbleSort(int arr[], int n) { for (int i = 0; i < n-1; i++) { // 标志变量用于检测是否发生交换 int swapped = 0; 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; swapped = 1; } } // 如果在某一轮没有发生交换,说明数组已排序完成 if (swapped == 0) break; } } // 打印数组函数 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("Unsorted array: \n"); printArray(arr, n); bubbleSort(arr, n); printf("Sorted array: \n"); printArray(arr, n); return 0; }
代码说明
bubbleSort
函数:
arr
和数组的长度 n
。swapped
检测在每一轮中是否发生交换,如果没有发生交换,说明数组已经有序,可以提前退出。printArray
函数:
main
函数:
bubbleSort
函数进行排序,然后打印排序后的数组。特点
冒泡排序适用于数据量较小或基本有序的数组,对于较大的数据集,效率较低。
快速排序(Quick Sort)是一种高效的排序算法,基于分治法(Divide and Conquer)。它的主要思想是选择一个基准元素(pivot),通过一趟排序将待排序列分成两部分,其中一部分的所有元素都比基准元素小,另一部分的所有元素都比基准元素大,然后递归地对这两部分进行快速排序。以下是快速排序的详细步骤和在C语言中的实现:
选择基准元素:
分区操作:
递归排序:
C语言实现代码
#include <stdio.h> // 交换两个元素的宏 #define SWAP(x, y) { int temp = x; x = y; y = temp; } // 分区函数 int partition(int arr[], int low, int high) { int pivot = arr[high]; // 选择最后一个元素作为基准 int i = (low - 1); // i是较小元素的索引 for (int j = low; j < high; j++) { // 如果当前元素小于或等于基准 if (arr[j] <= pivot) { i++; // 增加较小元素的索引 SWAP(arr[i], arr[j]); // 交换 } } SWAP(arr[i + 1], arr[high]); // 交换基准和i+1位置的元素 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("Unsorted array: \n"); printArray(arr, n); quickSort(arr, 0, n-1); printf("Sorted array: \n"); printArray(arr, n); return 0; }
代码说明
宏定义 SWAP
:
partition
函数:
pivot
。i
为 low - 1
。pivot
的元素移到数组的左侧,大于 pivot
的元素移到右侧。i+1
位置的元素,并返回 i+1
作为分区索引。quickSort
函数:
printArray
函数:
main
函数:
quickSort
函数进行排序,然后打印排序后的数组。特点
快速排序适用于大多数情况下的排序任务,尤其适合大规模数据的排序,因为其平均时间复杂度较低。
归并排序(Merge Sort)是一种经典的排序算法,其基本思想是将两个或两个以上的有序表组合成一个新的有序表。在C语言中实现归并排序,通常采用递归的方式。下面我会详细讲解C语言中归并排序的实现步骤和代码。
C语言实现:
#include <stdio.h> #include <stdlib.h> // 归并所需的辅助数组 int *temp; // 归并函数,将两个有序数组合并成一个有序数组 void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; // 左子数组的长度 int n2 = r - m; // 右子数组的长度 // 将数组复制到辅助数组中 for (i = 0; i < n1; i++) temp[l + i] = arr[l + i]; for (j = 0; j < n2; j++) temp[m + 1 + j] = arr[m + 1 + j]; // 合并临时数组回到原数组中 i = 0; // 初始索引第一个子数组 j = 0; // 初始索引第二个子数组 k = l; // 初始索引合并的子数组 while (i < n1 && j < n2) { if (temp[l + i] <= temp[m + 1 + j]) { arr[k] = temp[l + i]; i++; } else { arr[k] = temp[m + 1 + j]; j++; } k++; } // 复制剩余的元素到数组(如果有的话) while (i < n1) { arr[k] = temp[l + i]; i++; k++; } while (j < n2) { arr[k] = temp[m + 1 + j]; j++; k++; } } // 主函数,用于递归地排序数组 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); } } // 辅助函数,用于打印数组 void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } // 主函数 int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int arr_size = sizeof(arr) / sizeof(arr[0]); // 动态分配临时数组 temp = (int *)malloc(arr_size * sizeof(int)); printf("给定的数组:\n"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); printf("排序后的数组:\n"); printArray(arr, arr_size); // 释放临时数组 free(temp); return 0; }
mergeSort()
函数是递归函数,用于不断地将数组对半分,直到每个子数组的长度为1。merge()
函数负责将两个有序数组合并成一个有序数组。temp
是一个辅助数组,用于在合并过程中存储数据,避免直接在原数组上操作可能导致的元素丢失。main()
函数中初始化了待排序的数组,并调用了 mergeSort()
进行排序,最后打印排序后的数组。以上就是小编对四大排序的讲解。
如果觉得小编讲的还可以,还请一键三连。互三必回!
持续更新中~!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。