受到宫学长讲座的启发，学到不少的排序方法，所以也想记下来总结一下。所有排序默认都是从大到小排序
冒泡排序的优化
#include<stdio.h>
void swap(int *a,int *b)
void bubble1_sort(int *a,int len);
void bubble2_sort(int *arr,int n);
void bubble3_sort(int *arr,int len);
int main()//立flag优化
{
int a[]={10,9,8,7,6,5,4,3,2,1};
bubble3_sort(a,10);
for(int i=0;i<10;i++)
printf("%d ",a[i]);
putchar('\n');
}
void bubble1_sort(int *a,int len)
{
int flag=1;
for(int i=0;i<len&&flag;i++)
{
flag=0;
for(int j=0;j<len-i-1;j++)
{
if(a[j]>a[j+1])
{
flag=1;
swap(&a[j],&a[j+1]);
}
}
}
}
void bubble2_sort(int *arr,int n)
{
int index=0;
int len=n-1;
for(int i=0;i<n;i++)
{
index=0;
for(int j=0;j<len;j++)
{
if(arr[j]>arr[j+1])
{
index=j;//记住每次最后交换的序列
swap(&arr[j],&arr[j+1]);
}
}
len=index;//每次一趟就会有一个数排序，
//所以就只需要到最后交换的地方就可以了
}
}
void bubble3_sort(int *arr,int len)//鸡尾酒排序，两边同时进行
{
int right=len-1;
int left=0;
while(left<right)
{
for(int i=left;i<right;i++)//在左边找出最大元素
{
if(arr[i]>arr[i+1])
swap(&arr[i],&arr[i+1]);
}
right--;//右边最大数已经有了
for(int i=right;i>left;i--)//在右边找到最小的元素
{
if(arr[i-1]>arr[i])
swap(&arr[i-1],&arr[i]);
}
left++;//左边最小数已经有了
}
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
选择排序优化
#include<stdio.h>
void swap(int *a,int *b)
void select_sort(int A[],int n);
int main()
{
int a[10]={1,2,3,4,5,6,7,8,9,10};
select_sort(a,10);
for(int i;i<10;i++)
printf("%d ",a[i]);
}
void select_sort(int *arr,int len)//优化的方法就是一次性选出最大和最小
{
int left=0;
int right=len-1;
int max=0,min=0;
for(int left=0,right=len-1;left<right;left++,right--)//让区间左右都缩小
{
min=left;
max=right;
for(int i=left;i<right;i++)
{
if(arr[i]>arr[max])
max=i;
if(arr[i]<arr[min])
min=i;
}
if(max!=right)
swap(&arr[max],&arr[right]);
if(min==right)//最小值刚好在最右边
min=max;
if(min!=left)
swap(&arr[min],&arr[left]);
}
}
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
插入排序优化(二分法）
#include<stdio.h>
int binarysearch(int *arr,int start,int end,int k );
void insert_sort(int *arr,int len);
int main()
{
int a[]={10,9,8,7,6,5,4,3,2,1};
insert_sort(a,10);
for(int i=0;i<10;i++)
printf("%d ",a[i]);
}
int binarysearch(int *arr,int start,int end,int k )
{
//算出来之前k大于的数的终点
while(start<=end)
{
int middle=(start+end)/2;
if(arr[middle]>k)
end=middle-1;
else
start=middle+1;
}
return start;
}
void insert_sort(int *arr,int len)
{
int temp;
int insert;
for(int i=0;i<len-1;i++)
{
if(arr[i]>arr[i+1])
{
temp=arr[i+1];
insert=binarysearch(arr,0,i+1,arr[i+1]);
for(int j=i;j>=insert;j--)//将大数往后移动
arr[j+1]=arr[j];
arr[insert]=temp;//将小数放在比他小的数字之后
}
}
}
堆排序
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void MAX_HEADPIFY(int *arr,int i,int len);//建立最大堆
void swap(int *str1,int *arr2);//交换函数
void BULD_MAX_HEAP(int *arr,int len);//建立堆
void HEADPSORT(int *arr,int len);//排序
int main()
{
int len;
int arr[]={12,11,13,10,9,8,7,6,5,4,3,2,1};
HEADPSORT(arr-1,13);//因为堆排序找左右孩子的时候是2*i,2*i+1
//如果不这样，计算i=0的时候会出错
for(int i=0;i<13;i++)
printf("%d ",arr[i]);
}
void swap(int *arr1,int *arr2)
{
int t;
t=*arr1;
*arr1=*arr2;
*arr2=t;
}
void MAX_HEADPIFY(int *arr,int i,int len)//保证最大堆的性质
{
int max=i;
int left=2*i;
int right=2*i+1;
if(left<=len&&arr[left]>arr[max])//第二个不能使用str[i]，因为左孩子可能比节点大
max=left; //如果还是使用str[i]会让数据错误，切记！！！
if(right<=len&&arr[right]>arr[max])
max=right;
if(max!=i)
{
swap(&arr[max],&arr[i]);
MAX_HEADPIFY(arr,max,len);
}
}
void BULD_MAX_HEAP(int *arr,int len)//自底而上建堆
{
int i;
for(i=len/2;i>=1;i--)//i的len/2是树叶的个数
MAX_HEADPIFY(arr,i,len);
}
void HEADPSORT(int *arr,int len)
{
int i;
BULD_MAX_HEAP(arr,len);//先建立堆
for(i=len;i>=1;i--)
{
swap(&arr[1],&arr[i]);//取出最大值,保证之前str[1]永远是最大的
len=len-1;
MAX_HEADPIFY(arr,1,len);
}
}
qsort使用
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *a, const void *b)
{
return (*(int *)a)-(*(int *)b);//升序列
}
int main()
{
int arr[]={10,9,8,7,6,5,4,3,2,1};
qsort(arr,10,sizeof(int),cmp);
for(int i=0;i<10;i++)
printf("%d ",arr[i]);
}