使用C语言实现12种排序方法

void bubble_sort(int arr[],size_t len){
 size_t i,j;
 for(i=0;i<len;i++){ 
 bool hasSwap = false; //优化，判断数组是否已经有序，如果有序可以提前退出循环
 for(j=1;j<len-i;j++){ //这里j<len-i是因为最后面的肯定都是最大的，不需要多进行比较
 if(arr[j-1]>arr[j]){ //如果前一个比后一个大
 swap(&arr[j-1],&arr[j]); //交换两个数据
 hasSwap = true;
 } 
 }
 if(!hasSwap){
 break; 
 }
 }
}

void insert_sort(int arr[],int len){
 int i,j;
 for(i=1;i<len;i++){
 int key = arr[i]; //记录当前需要插入的数据
 for(j= i-1;i>=0&&arr[j]>key;j--){ //找到插入的位置
 arr[j+1] = arr[j]; //把需要插入的元素后面的元素往后移
 }
 arr[j+1] = key; //插入该元素
 }
}

void half_insert_sort(int arr[],int len){
 int i,j;
 for(i=1;i<len;i++){
 int key = arr[i];
 int left = 0;
 int right = i-1;
 while(left<=right){ //半分查找找到插入的位置
 int mid = (left+right)/2;
 if(key<arr[mid]){
 right = mid-1; 
 }else{
 left = mid+1; 
 } 
 }
 for(j=i-1;j>=left;j--){ //把后面的元素往后移
 arr[j+1]=arr[j]; 
 }
 arr[j+1] = key; //插入元素
 }
}

void shell_sort(int arr[],int len){ //本质上也是一种插入排序，避免了大量数据的移动，在每一组排序过后，每个数据已经到了大致的位置。
 int i,j;
 int step=0;
 for(step = len/2;step>=1;step=step/2){ //分组 分为step组,对每组的元素进行插入排序
 for(i=step;i<len;i++){
 int key = arr[i];
 for(j=i-step;j>=0&&arr[j]>key;j=j-step){
 arr[j+step] = arr[j]; 
 } 
 arr[j+step] = key;
 }
 }
}

void select_sort(int arr[],size_t len){
 size_t i,j;
 for(i=0;i<len-1;i++){
 int max = 0; //最大值下标
 for(j=1;j<len-i;j++){
 if(arr[max]<arr[j]){ //找到最大值的下标
 max = j; 
 } 
 }
 if(max!=j-1){ 
 swap(&arr[max],&arr[j-1]); //把最后一个元素和最大值进行交换
 }
 }
}

void cocktail_sort(int arr[],size_t len){
 size_t i,j;
 for(i=0;i<len/2;i++){
 int max = i; //最大值下标
 int min = i; //最小值下标
 for(j=i+1;j<len-i;j++){
 if(arr[max]<arr[j]){ //找到最大值下标
 max = j; 
 } 
 if(arr[min]>arr[j]){ //找到最小值下标
 min = j; 
 }
 }
 if(max!=j-1){
 swap(&arr[max],&arr[j-1]); //交换最大值和未进行排序的最后一个元素
 }
 if(min == j-1){ //如果最小值在未进行排序的最后一个位置，那么经过最大值的交换，已经交换到了最大值所在的位置
 min = max; //把最小值的坐标进行改变
 }
 if(min!=i){
 swap(&arr[i],&arr[min]); //交换最小值和未进行排序的最前的元素
 }
 }
}

void re_heap(int arr[],size_t index,size_t len){
 size_t child = 2*index+1; //左节点坐标
 int key = arr[index]; //当前节点值
 while(child<len){
 if(child+1<len&&arr[child]<arr[child+1]){ //如果右节点存在且右节点的值比左节点大，那就child记录较大字节点的坐标
 child++; 
 } 
 if(arr[child]>key){ //如果子节点的值比根节点的值大
 arr[index] = arr[child]; //改变根节点的值
 }else{
 break; 
 }
 index = child;
 child = 2*index+1;
 }
 arr[index] = key; //插入记录好的值
}
void heap_sort(int arr[],size_t len){
 int i;
 for(i=len/2;i>=0;i--){
 re_heap(arr,i,len); //对第i个根节点进行大堆化
 }
 for(i=len-1;i>0;i--){
 swap(&arr[0],&arr[i]); //交换第一个和最后一个元素
 re_heap(arr,0,i); //对第一个元素进行大堆化
 }
}

void quick_sort(int arr[],size_t left,size_t right){
 if(left>=right){ //如果只有一个元素，那就是有序的，返回
 return; 
 }
 int i = left;
 int j = right;
 int key = arr[left]; //基准值
 while(i<j){ //找到基准值的位置，使得基准值右边的元素都比基准值大，左边的元素都比基准值小
 while(i<j&&arr[j]>=key){ //从右边找一个比基准值小的数，
 --j;
 }
 arr[i] = arr[j];//把这个值放到基准值的位置处
 while(i<j&&arr[i]<=key){ //从左边找一个比基准值大的数
 ++i; 
 }
 arr[j] = arr[i]; //把这个元素放到j的位置
 }
 arr[i] = key;
 if(i-left>1) //元素个数至少两个才进行递归调用，这样可以少一次递归
 quick_sort(arr,left,i-1); //对基准值左边的元素进行排序
 if(right-i>1)
 quick_sort(arr,i+1,right); //对基准值右边的元素进行排序
}

void merge(int arr[],int left,int right){
 int i,j,k;
 int mid = (left+right)/2;
 int len = mid-left+1;
 int *temp = malloc(sizeof(arr[0])*len);
 for(i=0;i<len;i++){
 temp[i] = arr[i+left]; //把这个数组的所有元素都复制到临时数组中
 }
 i=0,j=mid+1,k=left;
 while(i<len&&j<=right){
 if(temp[i]<arr[j]){ //把临时数组的元素和 [mid+1,right]这部分的元素一个一个的进行比较，如果谁小，那么arr里就存放谁的元素
 arr[k++] = temp[i++]; 
 }else{
 arr[k++] = arr[j++]; 
 }
 }
 while(i<len){ //如果temp这个数组的元素还没有全部遍历完，那就把temp后面的元素都复制到arr里面去，
 //因为arr[mid+1,right] 这部分的元素本来就是arr后面部分的有序的元素，所以如果arr[mid+1,right]这部分没有遍历完也没关系的，
 arr[k++] = temp[i++]; 
 }
 free(temp);
}
void merge_sort(int arr[],int left,int right){
 if(left>=right){ //如果只有一个元素说明这个序列有序，那就返回
 return; 
 } 
 int mid = (left+right)/2; //对两个有序的数组进行排序，
 merge_sort(arr,left,mid); //对[left,mid]这个区间的元素进行排序
 merge_sort(arr,mid+1,right); //对[mid+1,right]这个区间内的元素进行排序
 merge(arr,left,right); //这个序列的[left,mid]为有序的序列 [mid+1,right]也为有序的序列
}

void count_sort(int arr[],size_t len){
 int max = arr[0]; //最大值
 int min = arr[0]; //最小值
 size_t i;
 for(i=0;i<len;i++){
 if(max<arr[i]){ //找到最大值
 max =arr[i]; 
 }
 if(min > arr[i]){ //找到最小值
 min = arr[i]; 
 }
 }
 int cnt = max-min+1; //范围
 int *prr = malloc(cnt*sizeof(int)); //申请临时空间
 for(i=0;i<cnt;i++){ //这个临时数组全部置0
 prr[i] = 0; 
 }
 for(i=0;i<len;i++){ //对需要进行排序的序列进行遍历
 prr[arr[i]-min]++; //让下标为(arr[i]-min)的临时大数组的值+1
 }
 size_t j=0;
 for(i=0;i<cnt;i++){ //遍历这个临时数组
 while(prr[i]){ //如果这个数组下标为i的值不等于0
 arr[j++] = i+min; //那就让需要进行排序的数组的值为i+min;
 --prr[i];
 } 
 }
 free(prr); //释放掉申请的动态内存
}

typedef struct Bucket{
 int vect[100]; //其实这里使用链表更好，但是我比较懒，就懒得用链表了
 int cnt; //当前桶内存放数据的个数
}

void bucket_sort(int arr[],size_t len){
 int min = arr[0];
 int max = arr[0];
 size_t i;
 for(i=0;i<len;i++){
 if(min>arr[i]){ //找到最小值
 min = arr[i]; 
 }
 if(max<arr[i]){ //找到最大值
 max = arr[i]; 
 }
 }
 int size = max-min+1;
 Bucket bucket[5] = {}; //其实桶可以动态规划，但为了方便我这里直接分为5个桶
 for(i=0;i<len;i++){ //遍历待排序的数组，把每个元素放到相应的桶当中，
 //比如[0,200]之间的元素放到下标为0的桶中，[201,400]之间的元素放到下标为1的桶中..
 //以此类推，直到放完所有的数据
 int index = (arr[i]-min)/(size/5); //用来判断当前元素arr[i]需要放到哪个桶当中
 bucket[index].vect[bucket[index].cnt++] = arr[i];
 }
 size_t j=0,k=0;
 for(i=0;i<5;i++){ //对这五个桶进行遍历
 count_sort(bucket[i].vect,bucket[i].cnt); //首先对这个桶内的元素进行排序，
 //这里可以调用其他排序方法，也可以递归调用当前排序方法，但是为了节省内存，我选择调用其他排序方法，
 for(j=0;j<bucket[i].cnt;j++){
 arr[k++] = bucket[i].vect[j]; //对排序好的桶进行遍历，并且把里面的元素复制到arr中去 
 }
 }
}

typedef struct Bucket{
 int vect[100]; //同样的可以用链表
 int cnt;
}Bucket;

void base_sort(int arr[],size_t len){
 size_t i;
 Bucket bucket[10] = {}; //十个桶
 int max = arr[0];
 for(i=0;i<len;i++){ //寻找最大值，就可以判断最大值的位数
 if(arr[i]>max){
 max = arr[i]; 
 } 
 }
 size_t j,k;
 int num = 1; //用来获得相应位数上的数字的关键参数，
 //比如要获得个位上的参数时num = 1;
 //获得十位上的数字时num = 10;
 //以此类推
 do{
 for(i=0;i<len;i++){ //遍历待排序的数组，把每个元素放入相应的桶中
 //比如251，当获得个位上的数字时，251放到下标为1的桶当中
 //当获得十位上的数字时,251放到下标为5的桶当中
 //当获得百位上的数字时,251放到下标为2的桶当中
 //当获得千位上的数字时,251放到下标为0的桶当中
 //以此类推
 int index = arr[i]/num%10; //获得相应位数上的数字
 bucket[index].vect[bucket[index].cnt++] = arr[i]; //把这个数字放到相应的桶中
 }
 k=0;
 for(i=0;i<10;i++){
 for(j=0;j<bucket[i].cnt;j++){
 arr[k++] = bucket[i].vect[j]; //把这些桶按顺序依次遍历，
 //把桶中的元素重新放回arr当中
 } 
 bucket[i].cnt = 0; //记得让桶中的cnt变为0,方便下一次存放
 }
 num*=10; //num*10
 }while(max/=10);//循环条件
}