c语言快速排序

谁借莪１个温暖的怀抱￠ 2023-02-16 12:02 14阅读 0赞

## 快速排序的: ##

原理:  
若序列中有n个元素，降低一个数据作为支点，将它放在表中合适的位置。以支点为界，序列分成两部分。  
其中左边数据小于等于支点，右边数据大于等于支点。然后，对左右两部分分别进行递归处理，直至排好序为止。

算法:  
将至点放在合适的位置—划分算法  
1.设两个指针，i和j,开始分别指向表的开始与结束，某一时刻，支点或在a处(开始时)，或在j处。  
（1）支点在i处:若r\[i\]<=r\[j\],两者位置合适，j减1;否则，两者位置不合适，r\[i\]与r\[j\]对换，i加1;  
（2）支点在j处:若r\[i\]<=r\[j\],两者位置合适，i加1;否则，两者位置不合适，r\[i\]与r\[j\]对换，j减1;  
2.重复直到i与j相等。

注:  
(1)最好情况:(每次支点总是在中间) T(n)=O(n*log2n)。  
(2)最坏情况:(数据已是递增或递减) T(n)=O(n*n)。  
所以说:快速排序在表已基本有序的情况下不合适。

#include"stdio.h"
    #define maxsize 100
    typedef struct
    { 
    	int r[maxsize];
    	int length;
    }link;
    
    void swap(link *a,int i,int j)//完成数值之间的交换
    { 
    	int temp;
    	temp=a->r[i];
    	a->r[i]=a->r[j];
    	a->r[j]=temp;
    }
    
    int quasi(link *a,int low,int high)//这是核心步骤
    { 
    	int value;//作为支点
    	value=a->r[low];//用第一个记录做枢轴
    	while(low<high)
    	{ 
    	//值得注意的是，以下两个while循环不能写错位置
    		while(low<high&&a->r[high]>=value)
    			high--;
    		swap(a,low,high);//将比枢轴记录小的记录交换到低端
    
    			while(low<high&&a->r[low]<=value)
    			low++;
    		swap(a,low,high);//将比枢轴记录大的记录交换到高端
    
    	}
    	return low;//返回枢轴所在位置
    
    }
    
    
    void recursion(link *a,int low,int high)/*通过递归的方式，使支点左右两端都有序*/
    { 
    	int centre;//用他作为中间支点
    	if(low<high)
    	{ 
    		centre=quasi(a,low,high);
    
    		recursion(a,low,centre-1);//递归
    		recursion(a,centre+1,high);
    
    	}
    }
    
    void quicksort(link *a)
    /*将输入的顺序表快速的排序，将顺序表一分为二, 小的都在支点左侧，大的都在支点右侧，将第一个数据作为支点*/
    { 
    	recursion(a,1,a->length);	//注意：是a->length而非a->length+1
    }
    
    main()
    { 
    	int i,n;
    	link a;
    	printf("请输入数组的长度n:\t");
    	scanf("%d",&n);
    	a.length=n;
    
    	printf("请输入数值:\n");
    	for(i=1;i<a.length+1;i++)
    	{ 
    		printf("请输入第%d个数\t",i);
    		scanf("%d",&a.r[i]);
    	}
    
    	printf("未排序之前的数组为:\t");
    	for(i=1;i<a.length+1;i++)
    		printf("%d\t",a.r[i]);
    
    	quicksort(&a);
    	printf("\n");
    
    	printf("排序之后的数组为:\t");
    	for(i=1;i<a.length+1;i++)
    		printf("%d\t",a.r[i]);
    	printf("\n");
    }

运行之后：  
![运行之后][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200609181022584.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjM0MjA5,size_16,color_FFFFFF,t_70