前言
本篇文章带大家来学习C语言的基本算法。
一、冒泡排序
冒泡排序是一种基于比较的排序算法。它的概念和思想方法比较简单易懂，下面我将详细解释一下冒泡排序的概念和思想方法：
1.概念：
冒泡排序的目标是对一组数据进行排序，将较大的元素逐步向右移动到数组的末尾（或将较小的元素移动到数组的开头）。
冒泡排序是一种稳定的排序算法，即相同元素的相对位置在排序后保持不变。
2.思想方法：
冒泡排序的关键思想是通过多次迭代，比较并交换相邻元素的位置，以逐步将最大（或最小）的元素移动到正确的位置。
它像气泡在水中逐渐上浮一样，每次迭代都会将当前未排序部分的最大（或最小）元素移动到当前未排序部分的末尾。
冒泡排序算法中使用了两层嵌套的循环结构：
外层循环控制迭代的次数，每次迭代会将一个最大（或最小）元素“冒泡”到当前未排序部分的末尾。
内层循环用于比较相邻元素的大小，并根据需要交换它们的位置。
3.排序过程：
假设有一个待排序的数组，名称为 arr，包含 n 个元素。
冒泡排序的外层循环从第一个元素开始，一直到倒数第二个元素（n-1）。
在每次外层循环的迭代中，内层循环从第一个元素开始，比较相邻的元素并交换它们的位置。
通过多次迭代，最大的元素会逐渐“冒泡”到当前未排序部分的末尾，最终完成排序。
4.时间复杂度：
冒泡排序的时间复杂度为 O(n^2)，其中 n 是待排序数组的长度。这是因为需要进行两层嵌套的循环，并且每次迭代需要比较和可能的交换操作。
总结来说，冒泡排序是一种简单直观的排序方法。它通过多次比较相邻元素并交换它们的位置，逐步将最大（或最小）的元素移动到正确的位置。
这里简单的演示一下排序的过程：
初始数组：[4, 2, 1, 5, 3]
初始状态： [4, 2, 1, 5, 3]
第一次迭代： [2, 1, 4, 3, 5]
第二次迭代： [1, 2, 3, 4, 5]
第三次迭代： [1, 2, 3, 4, 5]
第四次迭代： [1, 2, 3, 4, 5]
代码：
#include <stdio.h>
#include <unistd.h>
void BubBleSort(int* p, int len)
{
int i = 0, j = 0;
for(i = 0; i < len - 1; i++)
{
for(j = 0; j < len - 1 - i; j++)
{
if(p[j] > p[j + 1])
{
int temp = p[j];
p[j] = p[j + 1];
p[j + 1] = temp;
}
}
}
}
int main(void)
{
int a[5] = {2, 4, 1, 3, 5};
int len = sizeof(a) / sizeof(a[0]);
int i = 0;
BubBleSort(a, len);
for(i = 0; i < 5; i++)
{
printf("%d\n",a[i]);
}
return 0;
}
二、选择排序
原理：
选择排序的基本思想是：每次从待排序的数组中选择最小（或最大）的元素，将其放到已排序序列的末尾。具体步骤如下：
从未排序的部分中找出最小的元素。
将找到的最小元素与未排序部分的第一个元素交换位置。
将已排序部分的边界向右扩展一位。
重复上述过程直到所有元素排序完成。
时间复杂度：O(n²)
空间复杂度：O(1)
#include <stdio.h>
void selectionSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element of the unsorted part
if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
三、插入排序
原理：
插入排序的基本思想是：将数组分成已排序部分和未排序部分，每次从未排序部分中取出一个元素，插入到已排序部分的正确位置。具体步骤如下：
从第二个元素开始，假设第一个元素已经排序。
将当前元素与已排序部分的元素逐个比较，找到合适的位置进行插入。
将已排序部分向右移动以腾出位置，然后插入当前元素。
重复上述过程直到所有元素排序完成。
时间复杂度：O(n²)
空间复杂度：O(1)
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
四、希尔排序
原理：
希尔排序通过将整个待排序数组分成若干个小组，然后对每个小组进行插入排序。随着排序的进行，分组的间隔逐渐减小，最终将间隔减小到1，此时的插入排序已经对整个数组进行排序。具体步骤如下：
选择一个初始间隔（通常是数组长度的一半），将数组分成多个子数组。
对每个子数组进行插入排序。
减小间隔，重复步骤2，直到间隔为1时，对整个数组进行插入排序。
时间复杂度：O(n1.5)到O(n2)，具体取决于增量序列的选择
空间复杂度：O(1)
#include <stdio.h>
void shellSort(int arr[], int n) {
int gap, i, j, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
temp = arr[i];
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
shellSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
五、归并排序
原理：
归并排序是一种分治算法，将数组分成两个子数组，递归排序这两个子数组，然后将已排序的子数组合并成一个有序数组。具体步骤如下：
将数组分成两半，递归地排序每一半。
合并两个已排序的子数组。
时间复杂度：O(n log n)
空间复杂度：O(n)
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int *)malloc(n1 * sizeof(int));
int *R = (int *)malloc(n2 * sizeof(int));
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
free(L);
free(R);
}
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) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
六、快速排序
原理：
快速排序是一种分治算法，通过选择一个“基准”元素，将数组分成比基准元素小和大的两个子数组，然后递归地对这两个子数组进行排序。具体步骤如下：
选择一个基准元素。
将数组分成比基准元素小的部分和大的部分。
递归地对两个部分进行排序。
时间复杂度：O(n log n) 平均情况；O(n²) 最坏情况
空间复杂度：O(log n) 平均情况
#include <stdio.h>
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; 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);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
七、堆排序
原理：
堆排序利用堆这种数据结构，先将数组构建成一个最大堆（或最小堆），然后反复取出堆顶元素并重新调整堆。具体步骤如下：
将数组构建成一个最大堆。
取出堆顶元素，将其与堆的最后一个元素交换，缩小堆的大小，并重新调整堆。
重复步骤2，直到堆为空。
时间复杂度：O(n log n)
空间复杂度：O(1)
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) largest = left;
if (right < n && arr[right] >
总结
本篇文章主要为大家讲解了C语言中的排序算法，在笔试面试当中可能会经常考察到这些排序算法。
