运行结果正确
还是快速排序难一些。
完整代码
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
#include<malloc.h>
void swap(int *a,int *b);
void select_sort(int arr[],int n);
void tra_arr(int arr[],int n);
void insert_sort(int arr[],int n);
void shell_sort(int arr[],int n);
void perc_down(int arr[],int i,int n);
void heap_sort(int arr[],int n);
void merge(int arr[],int temp_arr[],int left_start,int right_start
,int right_end);
void m_sort(int arr[],int temp_arr[],int left,int right);
void merge_sort(int arr[],int n);
int get_pri(int arr[],int left,int right);
void q_sort(int arr[],int left,int right);
void quick_sort(int arr[],int n);
int main(){
int arr[100]={
10,9,8,7,6,5,4,3,2,1
};
select_sort(arr,10);
printf("\n简单选择排序结果\n");
tra_arr(arr,10);
int arr1[100]={
10,9,8,7,6,5,4,3,2,1
};
insert_sort(arr1,10);
printf("\n插入排序结果\n");
tra_arr(arr1,10);
int arr2[100]={
10,9,8,7,6,5,4,3,2,1
};
shell_sort(arr2,10);
printf("\n希尔排序结果\n");
tra_arr(arr2,10);
int arr3[100]={
10,9,8,7,6,5,4,3,2,1
};
heap_sort(arr3,10);
printf("\n堆排序结果\n");
tra_arr(arr3,10);
int arr4[100]={
10,9,8,7,6,5,4,3,2,1
};
merge_sort(arr4,10);
printf("\n归并排序结果\n");
tra_arr(arr4,10);
int arr5[100]={
10,9,8,7,6,5,4,3,2,1
};
quick_sort(arr5,10);
printf("\n快速排序结果\n");
tra_arr(arr5,10);
return 0;
}
void swap(int *a,int *b){
//在函数内部，如果打算接收的是指针的地址，那就不要加*,
//如果想要的是值，那就加*,我也很讨厌指针，但是没办法
int t=*a;
*a=*b;
*b=t;
}
//简单选择排序
void select_sort(int arr[],int n){
int min;
//这个过程一时半会讲不清楚，看书会清楚一些
for(int i=0;i<n;i++){
min=i;
for(int j=i+1;j<n;j++){
if(arr[i]>arr[j]){
min=j;
}
}
//经过上面的里层for，就找到了最小的元素的下表
swap(&arr[i],&arr[min]) ;
}
}
//插入排序
void insert_sort(int arr[],int n){
int temp,j;
for(int i=1;i<n;i++){
temp=arr[i];
for(j=i;j>0&&arr[j-1]>temp;j--){
//后挪
arr[j]=arr[j-1];
}
//现在就找到空出来的插入位置了
arr[j]=temp;
}
}
//希尔排序
void shell_sort(int arr[],int n){
int in,i,j,temp;
//本来这个排序是很好理解的，就是这个外层的循环
//故弄玄虚，你就把他理解成一个简单的，递减的数组就行
//而且这个2的指数递减的序列的时间复杂度是很坏的
//最好使用SED或者HIB序列会好很多,这里只是演示
//两个里层的for就是插入排序,仔细看看就能看懂
for(in=n/2;in>0;in=in/2){
for(i=in;i<n;i++){
temp=arr[i];
for(j=i;j>=in;j=j-in){
if(arr[j-in]>temp){
//后挪
arr[j]=arr[j-in];
}
else{
//arr[j-in]<temp，说明找到了
break;
}
}
//上面执行完，肯定找到了插入位置
arr[j]=temp;
}
}
}
//首先是下滤操作
//i是根，n是heap的规模
//这里的下滤针对最大堆
void perc_down(int arr[],int i,int n){
int child,temp;
//仔细想想，其实和插入排序差不多
//首先把i取出来，把i在堆里面所在的位置空出来
//这里和原来建堆的下滤又不一样，这里没有设置哨兵
for(temp=arr[i];(2*i+1)<n;i=child){
child=2*i+1;
//如果当前儿子不是最后一个，说明还有右儿子
//两者取最大
if(child!=(n-1)&&arr[child]<arr[child+1]){
child++;
}
if(temp<arr[child]){
arr[i]=arr[child];
}
else{
//当前取出来的值终于大于两个儿子时。
break;
}
}
//上面轮完之后，肯定找到了一个儿子比我们取出来的值还要小的
arr[i]=temp;
}
void heap_sort(int arr[],int n){
int i;
//建堆
for(i=n/2;i>=0;i--){
perc_down(arr,i,n);
}
//取最大值放在最后已经舍弃的位置上，下滤剩下的堆
for(i=n-1;i>0;i--){
//取最大值放在最后已经舍弃的位置上
swap(&arr[0],&arr[i]);
// 滤剩下的堆
perc_down(arr,0,i);
}
}
//归并排序
//第一步，写一个将两个已经排好序列的归并
void merge(int arr[],int temp_arr[],int left_start,int right_start
,int right_end)
{
int i,temp_start,elem_num,left_end;
temp_start=left_start;
left_end=right_start-1;
elem_num=right_end-left_start+1;
//归并的核心
while(left_start<=left_end&&right_start<=right_end){
if(arr[left_start]<=arr[right_start]){
temp_arr[temp_start++]=arr[left_start++];
}
else{
temp_arr[temp_start++]=arr[right_start++];
}
}
while(left_start<=left_end){
temp_arr[temp_start++]=arr[left_start++];
}
while(right_start<=right_end){
temp_arr[temp_start++]=arr[right_start++];
}
//重新拷回去，记住，这里归并的只是原来数组的一部分，所以不能从头开始
for(i=0;i<elem_num;i++,right_end--) {
arr[right_end]=temp_arr[right_end];
}
}
//第二步，递归调用归并，将数组不断分割
void m_sort(int arr[],int temp_arr[],int left,int right){
//tra_arr(arr,10);
int center;
//递归结束条件
if(left<right){
center=(right+left)/2;
m_sort(arr,temp_arr,left,center);
m_sort(arr,temp_arr,center+1,right);
merge(arr,temp_arr,left,center+1,right);
}
}
//第三步，初始化临时数组
void merge_sort(int arr[],int n){
int *temp_arr;
temp_arr=(int*)malloc(n*sizeof(int));
m_sort(arr,temp_arr,0,n-1);
free(temp_arr);
}
//快速排序
//首先，实现三数中值分割法,取一个“裁判” （中值）
int get_pri(int arr[],int left,int right){
int center=(left+right)/2;
if(arr[left]>arr[center]){
swap(&arr[left],&arr[center]);
}
if(arr[left]>arr[right]){
swap(&arr[left],&arr[right]);
}
if(arr[center]>arr[right]){
swap(&arr[center],&arr[right]);
}
//把中值扔到倒数第二个，因为上述操作已经让倒数第一大于中值了
swap(&arr[center],&arr[right-1]);
return arr[right-1];
}
//其次，实现分而治之
void q_sort(int arr[],int left,int right){
int i,j,pri;
//如果规模已经小于三了，就不要再分而治之了，没得分了
if(right-left>=3){
//取中值
pri= get_pri(arr,left,right);
//取左右往中间靠拢的两个指针i,j
i=left;
j=right-1;
//开始判断
while(1){
//如果当前i对应的值小于裁判，继续推进
while(arr[++i]<pri);
// 如果当前i对应的值大于裁判，继续推进
while(arr[--j]>pri);
//上面走完，肯定碰到硬杈了，在i和j没有错位的情况下
//交换
if(i<j){
swap(&arr[i],&arr[j]);
}
else{
break;
}
}
swap(&arr[i],&arr[right-1]);
//这个i的作用远不止此,这个i还记录了上一个裁判的位置
//开始对分下来的两个部分进行同样的操作
q_sort(arr,left,i-1);
q_sort(arr,i+1,right);
}
//如果递归到规模已经无法再分了
//就用普通的方法排序
else{
/*这里稍微讲一下
数组和指针实际上是一样的东西
到这里了，那肯定就剩一个或者两个元素了
所以数组的开头变成left所指的位置，现在left所在位置的下标
就是0，所以后面的n也要相应变化*/
insert_sort(arr+left,right-left+1);
}
}
//最后包装一下
void quick_sort(int arr[],int n){
q_sort(arr,0,n-1);
}
//遍历数组
void tra_arr(int arr[],int n){
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
printf("\n");
}
转载：https://blog.csdn.net/jiangjun_feng/article/details/117404323
查看评论