欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速排序

程序员文章站 2022-03-02 08:10:29
...

快排是对冒泡排序的一种改进,是目前认为最好的内排序算法之一。
核心思想:在当前排序的序列(ks,ks+1,…,kt)中任意选择一个元素作为分界元素或者基准元素,把小于或等于分界元素的所有元素都移到分界元素前面,把大于或等于的所有元素移到分界元素后边。这样,分界元素正好处在排序的最终位置上,并且把当前排序的序列划分成前后两个子序列(前一个子序列中所有元素都小于或等于分界元素,后一个子序列中的元素都大于或等于分界元素)。然后再对上述子序列递归地进行上述过程

#include <stdio.h>
#include <string.h>
int a[] = {49,38,65,97,76,13,27,49};
void QUICK_SORT(int a[],int l,int r){
	int i=l,j=r;
	int key = a[l]; //不能是a[0],子序列开头的元素不一定是a[0]
	if (i>=j) //缺少该if条件,将进入无限循环
	{
		return;
	}
	while(i<j){
		while(a[j]>=key && i<j)
			j--;   //找到小于key的值,替换他
		a[i] =a[j];

		while(a[i]<key && i<j)
			i++;  //原来的j位置上的值已经替换了i位置上的值,目前存在两个j位置上对应的值,用a[i]的值将他替换掉
		a[j] = a[i];
	}
	a[i] = key;


	QUICK_SORT(a,l,i-1);



	QUICK_SORT(a,i+1,r);

	
	

}
int main(){
	
	int n = (sizeof(a))/sizeof(int); //求数组的长度
	QUICK_SORT(a,0,n-1);

	for (int i=0;i<n;i++)
	{
		if (i==n-1)
		{
			printf("%d\n",a[i]);
		}else{
			printf("%d ",a[i]);
		}
		
	}
	return 0;
}
相关标签: 快速排序