C语言排序方法 C语言所有经典排序方法的实现代码

#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");
}