【C语言补充01】快速排序算法(递归)

一、思路

• 选取待排序段的第一个元素x为临界点，使其左侧数字均小于等于x，右侧均大于等于x，完成一次分割
  • 标记两个检查断点low和high，保证low和high所在的数字分别小于和大于x，不满足条件则交换，满足则low和high向中间靠拢，继续检查余下位置。
• 完成一次分割之后，low和high相遇处为分割点，将分割点两侧再次进行排序。
• 以此类推，直到完成全部排序。

二、代码示例

#include 

/*********************************
 *                               *
 *         快速排序算法           *
 *                               *
 *********************************/

#define N 10   //排序数字个数
void quicksort(int a[], int low, int high);
int split(int a[], int low, int high);

int main(int argc, char *argv[]) {
	
	int a[N], i;
	printf("输入%d个待排序数字: \n", N);
	for(i=0; i<N; i++){
		scanf("%d", &a[i]);
	}
	
	//调用快速排序函数 
	quicksort(a, 0, N-1);
	
	//打印排序结果 
	printf("排序结果: \n", N);
	for(i=0; i<N; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	
	return 0;
}
//快速排序函数 
void quicksort(int a[], int low, int high)
{
	int middle;
	if(low>=high) return;
	middle = split(a, low, high);    //middle为一次排序后的分割点
	//middle两侧继续分割 
	quicksort(a, low, middle-1);
	quicksort(a, middle+1, high);
	
}
//分隔函数, 返回分割后的断点 
int split(int a[], int low, int high)
{
	int split_element = a[low];
	for(;;){
		while( low<high && split_element <= a[high] ) high--; //排序匹配, high左移 
		if( low>=high ) break;     //移动结束 
		a[low] = a[high];
		low++;
		
		while( low<high && a[low] <= split_element ) low++;   //排序匹配, low右移 
		if( low>=high ) break;     //移动结束 
		a[high] = a[low];
		high--;
	}
	//此时分割完成, low = high
	a[high] = split_element; 
	return high;
}