茶类网站建设方案,网站建设公司电话销售客源,wordpress获取缩略图,html网站开发 工具常用排序算法的实现与介绍 在计算机科学中#xff0c;排序算法是非常基础且重要的一类算法。本文将通过C语言代码实现#xff0c;介绍几种常见的排序算法#xff0c;包括冒泡排序、选择排序、插入排序和快速排序。以下是这些排序算法的具体实现和简要介绍。
1. 冒泡排序排序算法是非常基础且重要的一类算法。本文将通过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,j0; 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语言实现几种常见的排序算法并通过函数指针数组动态调用不同的排序函数。通过这样的实现方式可以方便地扩展和测试不同的排序算法。希望本文能帮助读者更好地理解和掌握这些基础的排序算法。
完整代码
#includestdlib.h
#includestdio.h
#includestring.h
#includestdbool.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 i0;ilen;i){printf(%d ,arr[i]);}printf(\n);
}
typedef void (*sort_func)(TYPE *arr,size_t len);// 排序函数类型定义//冒泡排序
void bupsort(TYPE *arr,size_t len)
{bool flagtrue;// 标记是否发生交换for(size_t ilen-1;i0flag;i--)//发生过交换才继续{flagfalse;// 标记是否发生交换for(size_t j0;ji;j){if(arr[j]arr[j1]){swap(arr[j],arr[j1]);flagtrue;// 发生交换}}}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,j0; i len; i) {TYPE key arr[i];for( j i - 1; j 0 arr[j] key; j--){arr[j1] arr[j];}arr[j1] 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;
}
