C语言5个常用的排序算法实例代码
本文旨在讲解C语言中常用的5种排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序。以下将逐一介绍它们的实现过程,并提供示例代码。
冒泡排序(Bubble Sort)
-
算法思想:冒泡排序是一种简单的排序算法,它会首先比较相邻的元素,如果它们的顺序不正确,就交换它们的位置。这样一遍比较下来,最后一个元素就已经是最大的了,接着再执行n-1遍排序,每次比较的元素数量减一。
-
算法步骤:
-
遍历数组,比较相邻的两个元素,如果它们的顺序不正确则进行交换,将较大的元素交换到后面
- 执行n-1遍遍历
-
排序完成
-
示例代码:
void bubbleSort(int arr[], int n){
int i, j, temp;
for (i = 0; i < n-1; i++){
for (j = 0; j < n-i-1; j++){
if (arr[j] > arr[j+1]){
// 交换arr[j]与arr[j+1]的值
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
选择排序(Selection Sort)
-
算法思想:选择排序的基本思想是每一次选择一个最小的元素放到数组的头部,再选择一个次小的元素放到数组的第二个位置,以此类推。
-
算法步骤:
-
遍历数组,记录数组中最小元素的下标
- 交换最小元素和数组头部元素的位置
-
重复以上操作,直到数组排序完成。
-
示例代码:
void selectionSort(int arr[], int n){
int i, j, min_idx, temp;
for (i = 0; i < n-1; i++){
// 找到数组中最小元素的下标
min_idx = i;
for (j = i+1; j < n; j++){
if (arr[j] < arr[min_idx]){
min_idx = j;
}
}
// 交换arr[i]和arr[min_idx]的值
temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
插入排序(Insertion Sort)
-
算法思想:插入排序的基本思想是通过将未排序的元素逐一插入到已排序的序列中,从而依次排好序。
-
算法步骤:
-
将当前元素存储在一个临时变量中,然后向前扫描已排序好的元素,将当前元素插入到合适的位置。
-
重复以上操作,直到数组排序完成。
-
示例代码:
void insertionSort(int arr[], int n){
int i, j, key;
for (i = 1; i < n; i++){
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
快速排序(Quick Sort)
-
算法思想:快速排序使用了一种分治的策略,在数据集之中选择一个元素作为"基准"(pivot),所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准的后面(相同的数可以放到任一边)。然后递归地在两个子序列上重复该过程,直至每个子序列只有一个元素为止。
-
算法步骤:
-
选择一个元素作为基准值(pivot)。
- 将数组分成两个子数组:小于基准值的元素构成一个子数组,大于等于基准值的元素构成另一个子数组。
-
对子数组进行递归操作,直至子数组中只有一个元素。
-
示例代码:
void quickSort(int arr[], int low, int high){
if (low < high){
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot-1);
quickSort(arr, pivot+1, high);
}
}
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++;
// 交换arr[i]和arr[j]的位置
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换arr[i+1]和arr[high]的位置
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return (i + 1);
}
归并排序(Merge Sort)
-
算法思想:归并排序使用了一种分治的策略,将待排序的数组递归地分成两个大小大致相同的子数组,再将两个子数组排序,最后将排好序的子数组合并成一个排序好的数组。
-
算法步骤:
-
分割:将数组从中间分成两个子数组,继续递归分割。
- 排序:将两个元素排序。
-
合并:将两个排好序的子数组合并成一个数组。
-
示例代码:
void mergeSort(int arr[], int left, int right){
if (left < right){
int mid = (left+right)/2;
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
}
void merge(int arr[], int left, int mid, int right){
int i,j,k;
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for(i = 0; i < n1; i++){
L[i] = arr[left + i];
}
for(j = 0; j < n2; j++){
R[j] = arr[mid + 1+ j];
}
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++;
}
}
以上便是C语言中5种常用排序算法的实现过程和示例代码,选择何种排序算法主要应根据数据的规模、性质和要求决定。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:c语言5个常用的排序算法实例代码 - Python技术站