c语言快速排序法代码及注释_快速排序c语言代码以及解释

#include <stdio.h>
 
//总共需要三部分，part1：快速排列的排列部分
//part2：递归部分； 
//part3：主函数
 
 
//part1
int sorted(int a[],int low,int high){//需要一个数列两个指针
   int temp;
   temp=a[low];//将判断值取出来
   while(low<high) {
   	while(low<high && temp<=a[high])
   		high--;
   	if(low<high)
   		a[low]=a[high];
   	while(low<high && a[low]<=temp)
   	    low++;
   	if(low<high)
   		a[high]=a[low];
   }//该循环结束时两个指针重合
   a[low]=temp;//基础值归位
   return low;//返回的是指针返回位置 ，此时low和high的值一样，所以返回值是谁无所谓 
} 
 
 
//part2 递归部分
void Quick_sort(int a[], int start,int end){
	int pos;
	if(start<end){
	pos =sorted(a,start,end);//第一遍循环，找到中间值位置
	Quick_sort(a,start,pos-1);//开始循环将已经分为两半的（0~pos-1）小于基础值的部分递归排序
	Quick_sort(a,pos+1,end) ;//开始循环将已经分为两半的(pos+1~end)大于基础值的部分递归排序
 
 
 return;
}
}
 
 
//part3:编写主函数
int main(){
	int a[]={1,54,89,7,56,42,63};
	int len=(int)sizeof(a)/sizeof(*a);
	Quick_sort(a,0,len-1);
	for(int i=0;i<len;i++)
	printf("%d\n",a[i]);
	return 0;
} 

本人学习笔记，

重难点：

  1：为什么a[low]可以直接等于a[high]？

       因为在编写快速排列部分时，我们已经将基础值暂存在temp中，所以a[low]=a[high]时，原来的数据并不会消失。同时我们一定是交替使用a[low]=a[high]和a[high]=a[low]两条语句。这样便不会有数据的丢失。

2:递归部分语句是否可以省略一句？

  不可以。对于每一小段的队列进行排序，都有三步。确定基础值位置，基础值左边的数据全部小于基础值。右边数据大于基础值。三条递归语句对应三个排序步骤。

画图最可以清晰易懂。

以下内容为排序部分的单步执行状态

例如：25，56，34，15，5

第一次temp=25;low=0,high=4;

经过比较，5<25,不执行high--；high=4，low=0;给a[low]赋值

temp=25;a[0]=a[high]=5;   a[]={5,56,34,15,5}

再从从左往右比较；low=0,a[0]<25;low++;   low=1 ;a[1] = 56;   56>25  此时low=1；  high=4；

给a[high]赋值，a[4]=a[1] = 56      a[]={5,56,34,15,56}

a[4]=56>25;high--;   high=3;  a[3]=15 <25;   low=1;  high=3;

给a[low]赋值  a[1]=a[3]=15     a[]={5,15,34,15,56}

由于a[1]=15<25，所以low++;     low = 2 ;     a[2] =34>25   hign=3;

给a[high]赋值，a[3]=a[2]=34      a={5,15,34,34,56}

a[high]=34>25;  high--;   high=2=low  所有循环结束

此时low=high=2

a[low]=temp=a[2]=25;

a[]={5,15,25,34,56}

25左边的数都小于25，右边的数都大于25