【Linux C编程】第二十四章 C中的排序算法

本文将提出一个有趣且重要的主题，即 C 中的排序算法。本文将涵盖以下指针，

• Bubble Sort
• Insertion Sort
• Selection Sort
• Quick Sort
• Merge Sort

简单来说，排序意味着按有序的顺序排列给定的元素或数据。排序的主要目的是轻松快速地在排序列表中找到一个元素并围绕它设计一个有效的算法。在这篇博客中，我们将了解不同的排序算法以及如何在 C 中实现它们。

那么让我们开始吧，

冒泡排序

冒泡排序是一种简单的排序算法，它反复比较给定数组的相邻元素并在它们顺序错误时交换它们。
假设我们有一个数组 X，其中包含需要使用冒泡排序进行排序的 n 个元素。排序工作如下：

第 1 关：

•  比较 X[0] 和 X[1]，如果 X[0] > X[1] 则交换
•  比较 X[1] 和 X[2]，如果 X[1] > X[2] 则交换
•  X[2] & X[3] 进行比较，如果 X[2] > X[3] 则交换，依此类推……

在第 1 轮结束时，列表中最大的元素被放置在列表的最高索引处。

通过 2：

• 比较 X[0] 和 X[1]，如果 X[0] > X[1] 则交换
• 比较 X[1] 和 X[2]，如果 X[1] > X[2] 则交换
• X[2] & X[3] 进行比较，如果 X[2] > X[3] 则交换，依此类推……

在 Pass 2 的末尾，列表的第二大元素被放置在列表的第二大索引处。

通过 n-1：

• 比较 X[0] 和 X[1]，如果 X[0] > X[1] 则交换
• 比较 X[1] 和 X[2]，如果 X[1] > X[2] 则交换
• X[2] & X[3] 进行比较，如果 X[2] > X[3] 则交换，依此类推……

在这个通行证结束时。列表的最小元素放置在列表的第一个索引处。

继续这篇关于 C 中排序算法的文章，

C 中的冒泡排序程序

#include <stdio.h> 
// Function to swap elements 
void swap(int *a, int *b) 
{ 
int temp = *a; 
*a = *b; 
*b = temp; 
}  
// bubble sort function
void bubbleSort(int array[], int n) 
{ 
int i, j; 
for (i = 0; i < n-1; i++)       
for (j = 0; j < n-i-1; j++) if (array[j] > array[j+1]) 
swap(&array[j], &array[j+1]); 
}   
// Function to print the elements of an array
void printArray(int array[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", array[i]); 
printf("n"); 
}   
// Main Function
int main() 
{ 
int array[] = {89, 32, 20, 113, -15}; 
int size = sizeof(array)/sizeof(array[0]); 
bubbleSort(array, size); 
printf("Sorted array: n"); 
printArray(array, size); 
return 0; 
}

输出：

继续这篇关于 C 中排序算法的文章，

插入索尔Ť

插入排序是一种排序算法，通过一次取一个元素来对数组进行排序。插入排序的原理是取一个元素，遍历已排序的数组并找到它在已排序数组中的正确位置。

步骤 1 - 如果元素是第一个元素，则它已经排序。
步骤 2 – 移动到下一个元素
步骤 3 – 将当前元素与排序数组中的所有元素进行比较
步骤 4 – 如果排序数组中的元素小于当前元素，则迭代到下一个元素。否则，将数组中所有较大的元素向右移动一个位置
Step 5 - 在正确位置插入值
Step 6 - 重复直到整个列表排序

C中的插入排序程序

#include <math.h> 
#include <stdio.h>   
// Insertion Sort Function
void insertionSort(int array[], int n) 
{ 
int i, element, j; 
for (i = 1; i < n; i++) { element = array[i]; j = i - 1; while (j >= 0 && array[j] > element) { 
array[j + 1] = array[j]; 
j = j - 1; 
} 
array[j + 1] = element; 
} 
}   
// Function to print the elements of an array
void printArray(int array[], int n) 
{ 
int i; 
for (i = 0; i < n; i++) 
printf("%d ", array[i]); 
printf("n"); 
}  
// Main Function 
int main() 
{ 
int array[] = { 122, 17, 93, 3, 56 }; 
int n = sizeof(array) / sizeof(array[0]); 
insertionSort(array, n); 
printArray(array, n); 
return 0; 
}

输出

继续这篇关于 C 中排序算法的文章，

选择排序

选择排序从数组的未排序部分重复搜索最小元素，并将其放在数组已排序部分的末尾。选择排序首先在未排序的数组中找到最小的元素并将其与第一个元素交换。然后它在未排序的数组中找到第二小的元素并将它与第二个元素交换，算法会一直这样做直到整个数组被排序。

C语言选择排序程序

#include <stdio.h>  
// Function to swap elements
void swap(int *a, int *b) 
{ 
int temp = *a; 
*a = *b; 
*b = temp; 
}   
// Selection Sort
void selectionSort(int array[], int n) 
{ 
int i, j, min_element; 
for (i = 0; i < n-1; i++) 
{
min_element = i; 
for (j = i+1; j < n; j++) 
if (array[j] < array[min_element]) 
min_element = j; 
swap(&array[min_element], &array[i]); 
} 
}   
// Function to print the elements of an array
void printArray(int array[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", array[i]); 
printf("n"); 
}   
// Main Function
int main() 
{ 
int array[] = {15, 10, 99, 53, 36}; 
int size = sizeof(array)/sizeof(array[0]); 
selectionSort(array, size); 
printf("Sorted array: n"); 
printArray(array, size); 
return 0; 
}

输出

继续这篇关于 C 中排序算法的文章，

快速排序

QuickSort是一种分而治之的算法。QuickSort 算法围绕枢轴元素对整个数组进行分区。可以通过多种方式选择枢轴元素：

• 第一个元素作为枢轴
• 最后一个元素作为枢轴
• 中间元素作为枢轴
• 随机元素作为枢轴

在这篇博客中，我们将选择最后一个元素作为枢轴元素。
partition() 是 QuickSort 算法背后的关键过程。在分区中，枢轴元素起着重要的作用。Pivot 被放置在排序数组中的正确位置，所有小于 pivot 的元素放在它之前，所有大于 pivot 的元素放在它之后。所有这些操作都是在线性时间内完成的。
然后将数组从枢轴元素分为两部分（即小于枢轴的元素和大于枢轴的元素）& 使用快速排序算法对两个数组进行递归排序。

继续这篇关于 C 中排序算法的文章，

C语言快速排序程序

#include<stdio.h>  
// Function to swap two elements 
void swapElements(int* x, int* y) 
{ 
int temp = *x; 
*x = *y; 
*y = temp; 
}   
// Partition function
int partition (int arr[], int lowIndex, int highIndex) 
{ 
int pivotElement = arr[highIndex];
int i = (lowIndex - 1); 
for (int j = lowIndex; j <= highIndex- 1; j++) 
{ 
if (arr[j] <= pivotElement) 
{ 
i++; 
swapElements(&arr[i], &arr[j]); 
} 
} 
swapElements(&arr[i + 1], &arr[highIndex]); 
return (i + 1); 
}   
// QuickSort Function
void quickSort(int arr[], int lowIndex, int highIndex) 
{ 
if (lowIndex < highIndex) 
{ 
int pivot = partition(arr, lowIndex, highIndex); 
// Separately sort elements before & after partition 
quickSort(arr, lowIndex, pivot - 1); 
quickSort(arr, pivot + 1, highIndex); 
} 
}   
// Function to print array
void printArray(int arr[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", arr[i]); 
}   
// Main Function 
int main() 
{ 
int arr[] = {81, 27, 38, 99, 51, 5}; 
int n = sizeof(arr)/sizeof(arr[0]); 
quickSort(arr, 0, n-1); 
printf("Sorted array: "); 
printArray(arr, n); 
return 0; 
}

输出：

继续这篇关于 C 中排序算法的文章，

归并排序

归并排序是分而治之算法的最好例子之一。在归并排序中，我们递归地将数组分成两半，直到每个子数组都包含一个元素，然后我们将子数组合并成一个排序数组。merge() 函数将两个已排序的子数组合并为一个，其中假设 array[l .. n] 和 arr[n+1 .. r] 已排序。

C中的合并排序程序

#include<stdlib.h> 
#include<stdio.h> 
// Merge Function
void merge(int arr[], int l, int m, int r) 
{ 
int i, j, k; 
int n1 = m - l + 1; 
int n2 =  r - m; 
int L[n1], R[n2]; 
for (i = 0; i < n1; i++) 
L[i] = arr[l + i]; 
for (j = 0; j < n2; j++) 
R[j] = arr[m + 1+ j]; 
i = 0; 
j = 0; 
k = l; 
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++; 
} 
}
// Merge Sort Function in C 
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); 
} 
} 
// Functions to Print Elements of Array
void printArray(int A[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", A[i]); 
printf("n"); 
}   
// Main Method
int main() 
{ 
int arr[] = {85, 24, 63, 45, 17, 31, 96, 50}; 
int arr_size = sizeof(arr)/sizeof(arr[0]); 
printf("Given array is n"); 
printArray(arr, arr_size); 
mergeSort(arr, 0, arr_size - 1); 
printf("nSorted array is n"); 
printArray(arr, arr_size); 
return 0; 
}

输出：

现在通过上面的排序程序，您应该了解各种排序算法以及如何用C语言实现它们。我希望这个博客能给你提供信息并增加价值。