目录
一、概述
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
二、常见的排序算法
2.1 冒泡排序
2.1.1 定义
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复进行直到没有再需要交换的元素，这意味着数列已经排序完成。
2.1.2 C语言实现
这段代码首先定义了一个冒泡排序函数bubble_sort，它接受一个整型数组和数组的长度作为参数。然后定义了两个辅助函数print_array用于打印数组和main函数作为程序的入口。在main函数中，我们首先打印原始数组，然后调用冒泡排序函数进行排序，并再次打印排序后的数组。
#include <stdio.h>
void bubble_sort(int arr[], int len) {
int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
void print_array(int arr[], int len) {
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int len = (int) sizeof(arr) / sizeof(*arr);
printf("Original array: ");
print_array(arr, len);
bubble_sort(arr, len);
printf("Sorted array: ");
print_array(arr, len);
return 0;
}2.2 快速排序
2.2.1 定义
快速排序作为多种排序方法中效率最高的一种，其底层原理被广泛运用，他的核心思想与二叉树结构中的递归逻辑相似，首先标记一个元素作为基准点，然后利用该基准点把数组分成左右两个区间，并且使小于该基准点的元素放在左区间，大于该基准点的元素放在右区间，如此反复递归，直到数组为一个有序数组。
2.2.2 C语言实现
这段代码首先定义了一个辅助函数swap用于交换数组中的元素。然后定义了partition函数来选择一个基准点并重新排列数组，使得比基准点小的元素都在它的左侧，比基准点大的元素都在它的右侧。最后，quickSort函数递归地对数组的左右部分进行排序。printArray函数用于打印排序后的数组。在main函数中，我们定义了一个数组并对它进行排序，然后打印排序结果。
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
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++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi