C 语言排序算法
一、冒泡排序（Bubble Sort）
定义：依次比较相邻的两个元素，并按照升序或降序交换它们的位置，直到整个列表有序为止。这个过程类似于气泡在水中上升，因此得名“冒泡排序”。
基本步骤：
- 比较相邻的元素：如果第一个元素比第二个元素大或小（根据排列顺序决定），则交换他们的位置。
- 遍历整个列表：对每一对相邻元素重复上述比较，从开始的第一对到最后一对。这一趟完成后，最后的元素会是最大或者最小。（数据结构中，冒泡排序的每一趟完成后，都会有个数落在最终位置上）
- 重复上述步骤：针对所有的元素重复以上的步骤，除了最后一个。每次重复这些步骤时，需要比较的元素对数会减少一个。直到没有任何一对数字需要比较时，排序完成。
示例：
有一组数 ： 22，30，15，20，18，29 按照升序的顺序将这组数进行排列 一共6个数，
第一趟比较结果为 22，15，20，18，29，30 这趟一共比较5次，30已经被放到最终的位置（对于步骤二）
第二趟比较结果 15，20，18，22，29，30 这趟一共比较4次 29被放到最终的位置(这种是发生了比较但没交换)
第三趟：15，18，20，22，29，30 比较3次 22被放到最终的位置
第四趟：15，18，20，22，29，30 比较2次 20被放到最终的位置(这种还是发生了比较但没交换)
第五趟：15，18，20，22，29，30 比较1次 20被放到最终的位置(这种还是发生了比较但没交换)
接下就无需比较，排序完成
代码示例：
#include <stdio.h>
// 冒泡排序函数
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
//一趟过后，比较次数会减一 所以是len-1-i；
for (int j = 0; j < len - 1 - i; j++) {
// 交换元素位置
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = { 22, 30, 15, 20, 18, 60 };
int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
bubble_sort(arr, len); // 调用冒泡排序函数
// 打印排序后的数组
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
至此冒泡排序讲解完毕，多手动模拟一下过程就理解了；
二、选择排序
定义：选择排序（Selection Sort）是一种简单直观的排序算法，其基本思想是每次从未排序部分中找到最小（或最大）的元素，并将其放到已排序部分的末尾（或开头）。通过不断选择剩余元素中的最小（或最大）元素，最终实现整个数组的排序。
选择排序的基本步骤：
- 初始状态：将整个数组视为未排序部分。
- 选择最小元素：在未排序部分中找到最小（或最大）的元素。
- 交换位置：将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
- 更新已排序部分：将交换后的元素视为已排序部分的一部分，未排序部分减少一个元素。
- 重复步骤2-4：继续在剩余的未排序部分中进行选择和交换，直到整个数组有序。
代码示例：
//选择排序函数
void select_sort(int arr[], int len){
for(int i=0;i<len-1;i++){
int min_index=i;//记录最小值的索引，初始时将第一个设为最小值
for(int j=i+1;j<len;j++){
if(arr[j]<arr[min_index])
{
min_index=j;//每次找到较小值就记录其索引
}
}
//将找到的最小元素与为排序部分的第一个元素交换
int temp=arr[min_index];
arr[min_index]=arr[i];
arr[i]=temp;
}
}
三、插入排序
定义：插入排序（Insertion Sort）是一种简单直观的排序算法，其基本思想是将数组分为已排序部分和未排序部分，每次从未排序部分中取出一个元素，插入到已排序部分的正确位置，直到整个数组有序。
插入排序的基本步骤：
- 初始状态：将数组的第一个元素视为已排序部分，其余元素视为未排序部分。
- 选择元素：从未排序部分中取出一个元素。
- 插入元素：将取出的元素插入到已排序部分的正确位置。
- 重复步骤2-3：继续从未排序部分中取出元素并插入到已排序部分的正确位置，直到整个数组有序。
代码示例：
//插入排序函数
void insert_sort(int arr[], int len){
int i,j,key,temp;
for(i=1;i<len;i++){
key=arr[i];//当前待插入的元素
j=i;//从i开始向前搜索插入位置
while(j>0&&arr[j-1]>key){
arr[j]=arr[j-1];//向后移动元素
j--;
}
arr[j]=key;//插入元素到正确位置
}
}
四、快速排序
定义：快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略，通过选择一个基准元素（pivot），将数组分为两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后递归地对这两个子数组进行排序。
快速排序的基本步骤：
- 选择基准元素：从数组中选择一个元素作为基准（pivot）。
- 分区操作：将数组中的元素重新排列，使得所有小于基准元素的元素放在基准元素的左边，所有大于基准元素的元素放在基准元素的右边。
- 递归排序：对基准元素左右两边的子数组递归地进行快速排序。
代码示例：
#include <stdio.h>
//划分区间函数
int Partition1(int arr[],int low,int high){
int pivot=arr[low];//将第一个元素作为基准元素
while(low<high){ //当low==high时，即找到pivot元素的最终位置,完成一次划分
while(low<high&&arr[high]>=pivot){ //必须是大于等于pivot，否则当A[low]和A[high]都等于pivot时，会陷入死循环；同时要注意low<high
high--;
}
arr[low]=arr[high];
while(low<high&&arr[low]<=pivot){
low++;
}
arr[high]=arr[low];
}
arr[low]=pivot;//最后low所指的位置即为pivot元素的最终位置
return low;
}
//快速排序算法
void quick_sort(int arr[],int low,int high){
if(low<high){
int pivot_pos=Partition1(arr,low,high);//分区索引
//递归调用
quick_sort(arr,low,pivot_pos-1);
quick_sort(arr,pivot_pos+1,high);
}
}
int main() {
int arr[] = { 22, 30, 15, 29, 18, 60 };
int len = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
quick_sort(arr, 0,len-1); // 调用快速排序函数
// 打印排序后的数组
for(int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
ok,关于排序算法目前就讲解这么多，手动模拟排序过程能够帮助我们快速理解这些算法，所以动起手来试试吧。