数据结构之排序算法说明与举例 C语言实现
排序算法是计算机科学中的一个重要概念，它用于将一组数据按照一定的顺序排列。常见的排序算法有很多种，下面介绍十大常用的排序算法，并给出C语言实现的示例。
- 冒泡排序（Bubble Sort）：
冒泡排序是一种简单但效率低下的排序算法，它重复地比较相邻的两个元素并交换位置，直到整个序列有序为止。
C语言实现示例：
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]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
- 选择排序（Selection Sort）：
选择排序是一种简单但效率较低的排序算法，它每次选择最小的元素放到已排好序的序列的末尾。
C语言实现示例：
void selectionSort(int arr[], int n) {
int minIndex;
for (int i = 0; i < n-1; i++) {
minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
- 插入排序（Insertion Sort）：
插入排序是一种简单且高效的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
C语言实现示例：
void insertionSort(int arr[], int n) {
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
- 希尔排序（Shell Sort）：
希尔排序是插入排序的一种改进版本，它将整个序列分成若干个较小的子序列进行插入排序，然后逐渐减小子序列的长度，最终完成整个序列的排序。
C语言实现示例：
void shellSort(int arr[], int n) {
for (int gap = n/2; gap > 0; gap /= 2) {
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;
}
}
}
- 归并排序（Merge Sort）：
归并排序是一种分治算法，它将一个序列分成两个子序列，分别对子序列进行排序，然后将两个已排序的子序列合并成一个有序序列。
C语言实现示例：
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0;
int j = 0;
int 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++;
}
}
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);
}
}
- 快速排序（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);
}
}
- 堆排序（Heap Sort）：
堆排序是一种利用堆数据结构进行排序的算法，它将待排序序列构建成最大堆，然后依次从堆顶取出最大元素并调整堆，最终得到有序序列。
C语言实现示例：
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
- 计数排序（Counting Sort）：
计数排序是一种线性时间复杂度的排序算法，它通过统计每个元素的出现次数，然后根据出现次数将元素放入合适的位置。
C语言实现示例：
void countingSort(int arr[], int n) {
int output[n];
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
int count[max + 1];
for (int i = 0; i <= max; ++i)
count[i] = 0;
for (int i = 0; i < n; i++)
count[arr[i]]++;
for (int i = 1; i <= max; i++)
count[i] += count[i - 1];
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];
}
原文地址：https://blog.csdn.net/qq_39311377/article/details/142278014
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！