前言
本篇文章带大家来学习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语言中的排序算法,在笔试面试当中可能会经常考察到这些排序算法。