常用排序算法的实现与介绍

常用排序算法的实现与介绍

在计算机科学中，排序算法是非常基础且重要的一类算法。本文将通过C语言代码实现，介绍几种常见的排序算法，包括冒泡排序、选择排序、插入排序和快速排序。以下是这些排序算法的具体实现和简要介绍。

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。这个过程会重复进行直到没有元素需要交换为止。

void bupsort(TYPE *arr, size_t len) {bool flag = true; // 标记是否发生交换for (size_t i = len - 1; i > 0 && flag; i--) {flag = false;for (size_t j = 0; j < i; j++) {if (arr[j] > arr[j + 1]) {swap(&arr[j], &arr[j + 1]);flag = true; // 发生交换}}}printf("%s\n", __func__);
}

2. 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

void select_sort(TYPE *arr, size_t len) {for (size_t i = 0; i < len - 1; i++) {size_t min_index = i;for (size_t j = i + 1; j < len; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}if (min_index != i) {swap(&arr[i], &arr[min_index]);}}printf("%s\n", __func__);
}

3. 插入排序（Insertion Sort）

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void insert_sort(TYPE *arr, size_t len) {for (size_t i = 1, j = 0; i < len; i++) {TYPE key = arr[i];for (j = i - 1; j >= 0 && arr[j] > key; j--) {arr[j + 1] = arr[j];}arr[j + 1] = key;}printf("%s\n", __func__);
}

4. 快速排序（Quick Sort）

快速排序是一种分治法的排序算法。它通过选择一个基准元素，将待排序数组分割成两部分，递归地排序两个子数组。

// 处理分区逻辑的函数
int _Qsort(int *arr, int low, int high) {int pivot = arr[high];int index = low - 1;for (int i = low; i < high; i++) {if (arr[i] < pivot) {index++;swap(&arr[i], &arr[index]);}}swap(&arr[index + 1], &arr[high]);return index + 1;
}// 递归调用函数
void _Qsort_recursive(int *arr, int low, int high) {if (low < high) {int pi = _Qsort(arr, low, high);_Qsort_recursive(arr, low, pi - 1);_Qsort_recursive(arr, pi + 1, high);}
}// 公共接口函数
void Qsort(int *arr, size_t len) {if (arr != NULL && len > 0) {_Qsort_recursive(arr, 0, len - 1);}printf("%s\n", __func__);
}

5.希尔排序（shell sort）

//希尔排序
void shell_sort(TYPE *arr, size_t len) 
{for(int gap = len / 2; gap > 0; gap /= 2){for(int i = gap,j=0; i < len; i++){TYPE key = arr[i];for(j = i; j-gap >= 0 && arr[j-gap] > key; j -= gap){arr[j] = arr[j-gap];}if(i != j)arr[j] = key;}}
printf("%s\n",__func__);
}

主函数和测试

在主函数中，我们使用一个函数数组分别调用以上几种排序算法，并对随机生成的数组进行排序。

int main() {TYPE arr[LEN];sort_func sorts[] = {bupsort, Qsort, select_sort, insert_sort};for (int i = 0; i < sizeof(sorts) / sizeof(sorts[0]); i++) {for (int j = 0; j < LEN; j++) {arr[j] = rand() % 100; // 填充数组随机值}printf("排序前: ");show_arr(arr, LEN);sorts[i](arr, LEN); // 调用排序函数printf("排序后: ");show_arr(arr, LEN);printf("==========================\n");printf("\n");}return 0;
}

在这个例子中，我们展示了如何使用C语言实现几种常见的排序算法，并通过函数指针数组动态调用不同的排序函数。通过这样的实现方式，可以方便地扩展和测试不同的排序算法。希望本文能帮助读者更好地理解和掌握这些基础的排序算法。

完整代码：

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#define TYPE int
#define LEN 15void swap(int *a, int *b) 
{int temp = *a;*a = *b;*b = temp;
}
void show_arr(TYPE *arr,size_t len)
{for(size_t i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
typedef void (*sort_func)(TYPE *arr,size_t len);// 排序函数类型定义//冒泡排序
void bupsort(TYPE *arr,size_t len)
{bool flag=true;// 标记是否发生交换for(size_t i=len-1;i>0&&flag;i--)//发生过交换才继续{flag=false;// 标记是否发生交换for(size_t j=0;j<i;j++){if(arr[j]>arr[j+1]){swap(&arr[j],&arr[j+1]);flag=true;// 发生交换}}}printf("%s\n",__func__);
}//选择排序
void select_sort(TYPE *arr, size_t len) {for (size_t i = 0; i < len - 1; i++) {size_t min_index = i;for (size_t j = i + 1; j < len; j++) {if (arr[j] < arr[min_index]) {min_index = j;}}if (min_index != i) {swap(&arr[i], &arr[min_index]);}}printf("%s\n",__func__);
}//插入排序
void insert_sort(TYPE *arr, size_t len) 
{for (size_t i = 1,j=0; i < len; i++) {TYPE key = arr[i];for( j = i - 1; j >= 0 && arr[j] > key; j--){arr[j+1] = arr[j];}arr[j+1] = key;}printf("%s\n",__func__);
}//快速排序
// 处理分区逻辑的函数
int _Qsort(int *arr, int low, int high) {int pivot = arr[high]; // 最后一个元素作为基准int index = low - 1; // 记录小于基准元素的位置for (int i = low; i < high; i++) {if (arr[i] < pivot) {index++;swap(&arr[i], &arr[index]); // 将小于基准的元素移到左边}}swap(&arr[index + 1], &arr[high]); // 将基准元素放到中间return index + 1;
}// 递归调用函数
void _Qsort_recursive(int *arr, int low, int high) {if (low < high) {int pi = _Qsort(arr, low, high);_Qsort_recursive(arr, low, pi - 1); // 排序左半部分_Qsort_recursive(arr, pi + 1, high); // 排序右半部分}
}// 公共接口函数
void Qsort(int *arr, size_t len) {if (arr != NULL && len > 0) {_Qsort_recursive(arr, 0, len - 1);}printf("%s\n",__func__);
}
int main() {TYPE arr[LEN];sort_func sorts[] = {bupsort, Qsort, select_sort , insert_sort};// 排序函数数组for (int i = 0; i < sizeof(sorts) / sizeof(sorts[0]); i++) {for (int j = 0; j < LEN; j++) {arr[j] = rand() % 100; // 填充数组随机值}printf("排序前: ");show_arr(arr, LEN);sorts[i](arr, LEN); // 调用排序函数printf("排序后: ");show_arr(arr, LEN);printf("==========================\n");printf("\n");}return 0;
}