几种排序方式的C语言实现（冒泡、选择、插入、希尔等）
## 分类
存储器类型：
- 内排序（数据规模小 内存）
- 外排序（数据库 磁盘）
是否基于元素之间的比较
- 基数排序
- 其他排序：冒泡、选择、插入、快速、归并、希尔、堆……
时间复杂度
- O（nlogn）：快速、归并、堆...
- OO（n*n）：冒泡、选择、插入、希尔...
## 冒泡排序
相邻两个元素比较，若前面一个元素大，就交换位置，一轮进行n-1次比较，一共执行n-1轮
将最大值移动到最后
每轮可能有多次交换
## 选择排序
假设未排序的第一个为最小值，然后遍历未排序的内容，找到真正的最小值，和未排序的第一个位置互换，
每轮只有一次交换
## 插入排序
将第一个元素看作有序区，从第2个开始向前比较，放到有序区的正确位置
对于小规模数据或基本有序的数据效率较高
## 希尔排序
希尔排序是对插入排序的优化
将数据分间隔 d/（2 的n次方）进行预排序
## 快速排序
分治、递归
1、选择一个元素做基准，、
基准：第一个或者最后一个元素， 优化方案：第一个、最后一个，中间元素 ，三个数的中间值
定义两个指针， Left Right 左指针右移找到比基准大的数， 右指针左移找到比基准小的数，两个指针交换内容，
## 基数排序
通过分配、收集的过程实现排序
0~9号桶，先按照个位，放入对应同，从0号桶开始输出，这样所有数据的个位有序。
然后按十位开始放入桶内，然后从0号桶输出，这样数据的个位和十位都有序；
然后百位……
代码示例：
#include<stdio.h>
//冒泡排序
void bub(int *arr,int len)
{//从左向右 相邻两数作比较，将大的放到右侧，每次将未排序的最大值送达最右侧。for (int i = 0; i < len-1; i++){for (int j = 1; j < len-i; j++){if (arr[j-1]>arr[j]){int temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}
}
//选择排序
void select(int *arr,int len)
{//从左向右开始，找到未排序部分的最小值//先假设未排序部分最左边的为最小值，找到最真正最小值后交换到最左侧for (int i = 0; i < len-1; i++){int min=i;for (int j = i+1; j < len; j++){if (arr[j]<arr[min]){min=j;}}//如果最左侧不是最小值，则交换真正的最小值到左侧if(i!=min){int temp=arr[i];arr[i]=arr[min];arr[min]=temp;}}
}
//插入排序
void insert(int *arr,int len)
{//从第一个数开始，左侧视为已排序区for (int i = 1; i < len; i++){//选择排序区后的内容放入已排序区的正确位置for (int j = i; j >0 ; j--){if (arr[j-1]>arr[j]){int temp=arr[j];arr[j]=arr[j-1];arr[j-1]=temp;}}}
}
//希尔排序，对插入排序的优化
void shell_sort(int *arr, int len)
{// 将数组分为len/2的长度，然后进行插入排序
// 然后再分组 len/2/2for (int gap = len / 2; gap > 0; gap /= 2){for (int i = gap; i < len; i++){int temp=arr[i];//退出j循环后还需要减去gap的j所以要循环外声明jint j;for (j = i; j >= gap&&arr[j-gap]>temp; j-=gap){arr[j]=arr[j-gap];}//for循环退出后已经-gap 所以下方的arr[j]就是原来的arr[j-gap]arr[j]=temp;}}
}
//交换函数
void swap(int *a,int *b)
{int temp=*a;*a=*b;*b=temp;
}
//递归 快速排序
void quick_sort(int *arr ,int left,int right)
{if (left>=right){return ;}int i=left;int j=right;int temp=arr[left];//找到基准值的正确位置//当数组中有不符合条件的数据时，循环内会交换，使基准值最左边全小于基准值，右边全大于基准值while (i!=j){//先从右向左找小于基准的数while (arr[j]>=temp&&i<j){j--;}//再从左向右找大于基准的数while (arr[i]<=temp&&i<j){i++;}//跳出两个循环则表示找到，然后交换两个数if (i<j){swap(&arr[i],&arr[j]);}}//当i=j时跳出循环，swap(&arr[i],&arr[left]);quick_sort(arr,left,i-1);quick_sort(arr,i+1,right);}