基于平均值为枢轴的快速排序算法

题目来源

这是我在2019年研究生入学考试中遇到的一道题目，之前我们所认识的快速排序无外乎是以第一个元素或中位数作为枢轴。但是使用的第一个元素作为枢轴存在一个问题，我在接下来的分析中将进行阐述。但是各种博客以及论文中对于基于平均值的快速排序的具体都闭口不谈，后来我用了大概两三个小时通过修改现有的快速排序代码得到了基于平均值的快速排序代码。这也是我的第一篇博客，希望大家支持，这也是我继续写下去的动力。

原有快速排序算法

假设排序的数组是A[0]…A[n-1]，首选任意选取一个数据，但是通常都是选择A[0]元素作为关键数据，然后将所有比他小的元素都放到他的左边，所有比他大的元素都放到他的右边，这一过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的快速排序。

一趟快速排序的算法是
1）.设置两个变量i，j，排序开始的时候：i=0，j=N-1；
2）. 一般以第一个数字元素作为关键元素，赋值给key，即key=A[0]；
3）. 从j开始向前搜索，即由后向前进行搜索(j–)，扎到第一个小于key的值，将A[j]与A[i]的值交换；
4）. 从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）. 重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
这一部分的分析我就不多进行解释了，因为网上的各种博客都已经写的很清楚的，代码也很成熟了。

原有算法的缺陷

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
如果这个是使用第一个元素进行分割的话，那么将分割9次，这样就将快速排序的时间复杂度从O(nlog₂n）增加到了O(n²）。对于快速排序来说，最优的方式就是平均分割，但是当原有序列基本有序或者基本逆序的情况下，以第一个元素分割的结果就会十分不平衡。所以我们应该选择一个最平均的分割方式，这个方式就是基于平均值为枢轴的快速排序。

代码

#include<stdio.h>
void quicksort(int A[],int low,int high){
	if(low<=high) {
		int i,j,temp,sum=0,ave,t;
		for(i=low;i<=high;i++){
		sum+=A[i];
		}
		i = low;
		j = high;
		ave = sum/(high-low+1);
		while(i<j){
			while(A[i]<ave&&i<=j)  ++i;
			while(A[j]>ave&&i<=j)  --j;
			if(i<j){
				temp = A[i];
				A[i] = A[j];
				A[j] = temp;
				i++;
				j--;
			}
		}

		if(i<high&&j>low){
			quicksort(A,low,j);
			quicksort(A,i,high);
		}
		else return;
	}
}