c语言项目实战之排序

向右看齐 2022-02-04 07:13 120阅读 0赞

详细的排序算法讲解大家可以参考这个链接  
[https://mp.csdn.net/postedit/86649581][https_mp.csdn.net_postedit_86649581]  
[https://blog.csdn.net/qq\_44614524/article/details/87881769][https_blog.csdn.net_qq_44614524_article_details_87881769]  
基本排序算法：希尔排序、快速排序、选择排序、堆排序

#include<stdio.h>
    #include<string.h>
    
    #define maxsize 100001
    //希尔，快速，选择，堆 
    struct node{
    	int num;
    	int count;
    }; 
    
    struct node s[maxsize];
    
    void swap(struct node *s, int i, int j) 	//交换数据的函数 
    { 
    	struct node tem;
    	tem = s[i];
    	s[i] = s[j];
    	s[j] = tem;
    		
    } 
    
    
    void shellsort(struct node *s, int length)		//希尔排序 
    {
    	int i, j;
    	int increment = length;
    	do
    	{
    		increment = increment / 3;		
    		for(i = increment + 1;i <= length;i++)
    		{
    			if(s[i].count < s[i - increment].count)
    			{
    				s[0] = s[i];		
    				for(j = i - increment;j > 0 && s[0].count < s[j].count;j -= increment)
    					s[j + increment] = s[j]; 	//数据后移，寻找要插入的位置 
    				s[j + increment] = s[0];	 
    			}
    		}
    	}while(increment > 1);
    }
    
    void build_heap(struct node *a, int s, int m)		//堆排序 
    {
    	struct node tem1;
    	int tem = a[s].count, j;
    	//tem1 = a[s];
    	for(j = 2 * s;j <= m;j *= 2)		//沿关键字较大的节点向下筛选 
    	{
    		if(j < m && a[j].count < a[j + 1].count)
    			++j;					//j为关键字中较大的下标 
    		if(tem >= a[j].count)
    			break;
    		a[s] = a[j];
    		s = j; 
    	}
    	a[s].count = tem;		//插入 
    }
    
    void heap_sort(struct node *s, int length)		 
    {
    		int i;
    		for(i = length / 2;i > 0;i--)
    			build_heap(s, i, length);	
    		for(i = length;i > 0;i--)
    		{
    			swap(s, 1, i);		//将堆顶记录与当前未排序的子序列的最后一个记录交换 
    			build_heap(s, 1, i - 1);	//将剩下的元素重新调成大顶堆 
    		}
    }
    
    int partition(struct node *s, int low, int high)
    {
    	int pivotkey = s[low].count;		
    	while(low < high)
    	{
    		while(low < high && s[high].count >= pivotkey)		//将比枢纽大的数值交换到右半边 
    			high--;
    			swap(s, low, high);
    		while(low < high && s[low].count <= pivotkey)		将比枢纽小的数值交换到左半边
    			low++;
    			swap(s, low, high); 
    	}
    	return low;		 
    }
    
    void digui(struct node *s, int low, int high)
    {
    	int pivot;
    	if(low < high)
    	{
    		pivot = partition(s, low, high);
    		digui(s, low, pivot - 1);		
    		digui(s, pivot + 1, high);	 
    	}
    }
    
    void quick_sort(struct node *s, int length)
    {
    	digui(s, 1, length + 1);
    }
    
    void select_sort(struct node *s, int length)
    {
    	int i, j;
    	struct node tem;
    	for(i = 1;i <= length;i++)
    	{						 
    		for(j = i + 1;j <= length;j++)	
    		if(s[i].count > s[j].count)		
    			{
    				tem = s[i];
    				s[i] = s[j];
    				s[j] = tem;
    			}
    			//swap(s, i, min);
    	}	
    }
    
    void print(struct node *s, int length)
    {
    	for(int i = length;i > 0;i--)
    		printf("%d    ", s[i].count);
    	printf("\n");
    }
    
    int main()
    {
    	int length;
    	int i;
    	puts("请输入职工数");
    	scanf("%d", &length);
    	for(i = 1;i <= length;i++)
    	{
    		printf("请输入第%d职工工号和其对应的产品数量(中间以空格分开)", i);
    		scanf("%d%d", &s[i].num, &s[i].count); 
    	}
    	
    	puts("希尔排序结果为");
    	shellsort(s, length);
    	print(s, length);
    	
    	puts("堆排序结果为");
    	heap_sort(s, length); 
    	print(s, length);
    
    	puts("快速排序结果为");
    	quick_sort(s, length);
    	for(int i = length + 1;i > 1;i--)
    		printf("%d    ", s[i].count);
    	printf("\n");
    
    	puts("选择排序结果为");
    	select_sort(s, length);
    	for(int i = length + 1;i > 1;i--)
    		printf("%d    ", s[i].count);
    	printf("\n");	
    	return 0;
    }
    `在这里插入代码片`/*
    5
    01 55
    02 99
    03 44
    04 11
    05 77
    */

测试的数值在代码末尾已经给出，为了简单起见，我们直接带入得到以下结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]

[https_mp.csdn.net_postedit_86649581]: https://mp.csdn.net/postedit/86649581
[https_blog.csdn.net_qq_44614524_article_details_87881769]: https://blog.csdn.net/qq_44614524/article/details/87881769
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220204/9bf3b6689df84b87a20d168219e78ebb.png