1. 选择排序
xuanze_sort.c
#include<stdio.h>
#include<stdlib.h>
//选择排序
void xuanze_sort(int arr[],int sz){
//正着
for(int i=0;i<sz;i++){
//外层循环从第一个数据开始依次作为基准数据
for(int j =i+1;j<sz;j++){//int j =i+1 因为第一个数据作为了基准数据，所以每次比较从他的下一个数据开始
if(arr[i]>arr[j]){//arr[i]作为基准数据如果有元素小于基准数据，就将此元素作为基准数据
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
//反着
// for(int i=0;i<sz;i++){
// //外层循环从第一个数据开始依次作为基准数据
// for(int j =sz-1;j>i;j--){//int j =i+1 因为第一个数据作为了基准数据，所以每次比较从他的下一个数据开始
// if(arr[i]>arr[j]){//arr[i]作为基准数据如果有元素小于基准数据，就将此元素作为基准数据
// int tmp = arr[i];
// arr[i] = arr[j];
// arr[j] = tmp;
// }
// }
// }
}
int main()
{
int arr[] = {5, 4,3,15,12,24,2,1};
int sz = sizeof(arr)/sizeof(arr[0]);
xuanze_sort(arr,sz);
for(int i=0;i<sz;i++){
printf("%d ",arr[i]);
}
return 0;
}
2.快速排序
思路：
1）创建一张表，表对顺序没有要求
2）从表中找到一个数据，作为基准数据，基准数据一般是用表中的第一个数据（最后一个数据）作为基准数据
3）设置两个哨兵A和B，一个哨兵A是指向表中的第一个数据元素，另外一个哨兵B指向表中的最后一个数据元素
4）哨兵B开始从右往左开始行走，直到走到比基准数据小的就停下；哨兵A从左往右开始行走，直到走到比基准数据大的就停下；只要哨兵A和哨兵B没有相遇，就将哨兵A指向的数据与哨兵B指向的数据进行交换；当哨兵A和哨兵B相遇（即指向同一个数据元素），这时候就将哨兵指向的数据元素与基准数据进行交换
qiuck_sort.c
#include<stdio.h>
#include<stdlib.h>
void quick_sort(int arr[],int left,int right){
if(left>=right){//跳出递归的条件
return;
}
int l = left;
int r = right;
int base = arr[left];//指定基准数据
while(l != r){//只要左右哨兵不相遇就一直循环
//右边遇到比基准数据小的停止
while(l<r && arr[r]>=base){
r--;
}
//左边遇到比基准数据大的停止
while(l<r && arr[l]<=base){
l++;
}
//左右哨兵停止且没有相遇时，交换各自所指向的元素
if(l<r){
int tmp = arr[l];
arr[l] = arr[r];
arr[r] = tmp;
}
}
//左右哨兵相遇时，就将烧饼所指的数据和基准数据交换
//至此到这，交换后的基准数，左边都比自己小，右边都比自己大
if(l == r){
int tmp = arr[left];
arr[left] = arr[r];
arr[r] = tmp;
}
//以刚刚的基准数据为中心将数组分为两半
quick_sort(arr,left,r-1);//左半部分递归
quick_sort(arr,r+1,right);//右半部分递归
}
int main()
{
int arr[] = {2,2,3,2,2};
int sz = sizeof(arr)/sizeof(arr[0]);
quick_sort(arr,0,sz-1);
for(int i=0;i<sz;i++){
printf("%d ",arr[i]);
}
return 0;
}
3.插入排序
取出数组中的第二个元素，从此开始遍历，将此此元素从后向前依次比较，如果被比较元素比他大，被比较元素就往后移，直到找到比他小的元素为止，然后将他放入比它小的元素的位置后面
insert_sort2.c
#include<stdio.h>
//插入排序
void insert_sort(int arr[],int sz){
for(int i=1;i<sz;i++){
//首先取出数组的第二个元素，从此开始遍历
int tmp = arr[i];//成为基准数据 拿到第元素后，从这个元素开始由后向前与其前面的元素做比较
int pos = i-1;//记录基准数据前一个数据的下标
while(pos>=0 && tmp<arr[pos]){//如果基准元素小于前一个元素，就将其往前移动，即前面的元素向后移动,以此类推循环
arr[pos+1] = arr[pos];//即前面的元素向后移动
pos--;
}
arr[pos+1] = tmp;//将基准数据放入空位
}
}
int main()
{
int arr[] = {8,2,1,4,2,9,3};
int sz = sizeof(arr)/sizeof(arr[0]);
insert_sort(arr,sz);
for(int i=0;i<sz;i++){
printf("%d ",arr[i]);
}
return 0;
}
