C语言快速排序算法代码分析

「爱情、让人受尽委屈。」 2022-08-27 04:56 148阅读 0赞

首先，要对快速排序的原理有一定的了解，先看C语言快速排序的代码。

void sort(int a[],int size)
    {
    	int i=0,j=size-1,value=a[0];
    	if(size>1)
    	{
    		while(i<j)
    		{
    			for(;i<j;j--)
    			{
    				if(a[j]<value)
    				{
    					a[i]=a[j];
    					break;
    				}
    			}
    			for(;i<j;i++)
    			{
    				if(a[i]>value)
    				{
    					a[j]=a[i];
    					break;
    				}
    			}
    		}
    
    		a[i]=value;
    		sort(a,i);
    		sort(&a[i+1],size-i-1);
    	}
    }

分析内部循环：

while(i<j)
    {
    	for(;i<j;j--)//第一个for循环
    	{
    		if(a[j]<value)
    		{
    			a[i]=a[j];
    			break;
    		}
    	}
    	for(;i<j;i++)//第二个for循环
    	{
    		if(a[i]>value)
    		{
    			a[j]=a[i];
    			break;
    		}
    	}
    }

这个循环的作用是：把小的数都放在左端，大的数都放在右端。  
现在假设初始值是：6 9 7 3 4，j=4, i=0，以6为对比值，把小于6的放在数据6的左边，大于6的放在6的右边，看下图，

![Center][]

把6（也就是a\[0\]的值）当作对比值，当执行第一次循环体的时候：

（第一个for循环）从右向左找比6小的，初始值中6 9 7 3 4，可以发现4比6小，于是把4赋给a\[0\]，或许有的朋友会疑惑，a\[0\]的值那不就被覆盖了么，其实刚开始6已经赋值给value了，大家根据代码也可以发现。 于是原来的值等于4的位置，也就是a\[4\]（上图第三行的黄底显示），这就是一个“坑位”，里面好像是保存了数据，但是这个数据没用，因为它的值已经保存到了a\[0\]（原a\[0\]的值保存到了value）。此时数组的元素为 4 9 7 3 4

（第二个for循环）从左向右找比6大的，根据上一个执行结果数组的元素改变为 4 9 7 3 4，9比6大，就是把9装到上面那个坑位中。这个9原来所在的地方，也就是a\[1\]于是空了出来（尽管它里面有个没用的数据），成为坑位。

循环体执行一次成功。

接下来执行，第二次循环。到最后，最后的坑位是a\[2\]。

这个while循环体，执行完之后，i就会等于j。这个地方值得大家注意一下。而且i==2，刚好是坑位所在的位置。当执行完循环体后，a\[2\]=value;

发现没，此时数组元素 4 3 6 7 9，以6为分节点，这个循环成功的完成他的任务。

接下来就是把4 3 看作新数组，7 9看作新数组。接着递归下去，直到这样分割到只剩一个元素为止。

小学生能力有限，请大神帮忙斧正。

[Center]: /images/20220824/b59a6d95242a4f7c9603554ce4177bdd.png