快速排序 - 一个萝卜一个坑

• 快速排序算法的通俗理解

  quick_sort简单来说就是一种用到递归的分治算法，每一个递归基就是采用拔萝卜填坑的思想。假设有一排大小不同的萝卜，我们想要把萝卜从小到大挖坑进行排列，萝卜太多直接对比压根看不过来，小白兔手上只能一手拿一个萝卜进行对比，我们需要先拔出一个萝卜作为参照物，具体对比步骤如下

  • ①拔出一个萝卜作为参照物，具体第几个随意，为了方便我们拔出第一个，此时留出一个坑。

  • ②从后面往前面对比，发现比手上萝卜大的就跳过(因为是从小到大排列，大萝卜肯定在后面)，比手上萝卜小的放到左边参照物的坑里，此时右边留个坑

  • ③再从前往后对比，发现比手上萝卜小的就跳过(小萝卜放前面)，比手上萝卜大的放到右边留下的坑里。

  • ④重复上面②③步骤，直至从前往后和从后往前对比的萝卜刚好是同一个，把参照物萝卜埋入这个坑里，这时在这个坑左边的萝卜都比参照物左边的小，在这个坑右边的萝卜都比参照物萝卜大。

  • ⑤递归调用，把参照物萝卜左边和右边的萝卜当做一堆新萝卜，进行上述①②③④的填坑，只到一堆萝卜只有一个，这样萝卜便按顺序从小到大排列了。

• 快速排序算法的优劣性

  • 优点：快速排序是平均性能最好的算法，其时间复杂度为O(nlogn)。

  • 缺点：

    • 快速排序虽然只用到了一个元素的辅助空间，但是其采用的是递归的思想，需要通过不断的压栈来进行递归。

    • 快速排序属于不稳定排序（不稳定排序即排序时如果两个元素大小相等，但是仍将它们交换的排序方法）。

  • 常见排序的时间复杂度

    

• 快速排序的代码实现

  #include <stdio.h>
  
  void quick_sort(int *buffer, int left,int right)//quick_sort function define
  {
  	int i = left, j = right;
  	int template_value = buffer[left];//选出第一个萝卜为参照物萝卜
  
  	if(left<right)//先判断萝卜堆是不是只有一个萝卜
  	{
  		while(i<j)//判断萝卜堆从左到右和从右到左比较到同一个萝卜则比较完
  		{
  			while(template_value<buffer[j]&&i<j)//从后往前比参照物萝卜大的跳过
  				j--;
  			if(i<j)//从后往前比参照物萝卜小的放到前面坑里
  				buffer[i++] = buffer[j];
  
  			while(template_value>buffer[i]&&i<j)//从前往后比参照物萝卜小的跳过
  				i++;
  			if(i<j)//从前往后比参照物萝卜大的放到后面坑里
  				buffer[j++] = buffer[i];
  		}
  		buffer[i] = template_value;//把参照物萝卜填到最后一个坑里
  		quick_sort(buffer,left,i-1);//将参照物萝卜左边当做一个新萝卜堆递归调用
  		quick_sort(buffer,i+1,right);//将参照物萝卜右边当做一个新萝卜堆递归调用
  	}
  
  }
  
  int main(int *args, char *argv[])
  {
  	int a[10]={9,7,11,2,5,7,59,62,13,0};
  	int i = 0;
  
  	quick_sort(a,0,9);
  	for(i=0;i<10;i++)
  	{
  		printf("%5d", a[i]);
  	}
  	printf("\n", a[i]);
  
  	return 0;
  }

• 测试结果：

•