C语言实现以平均值为界的快速排序算法

平均值为界的快速排序算法"/>

C语言实现以平均值为界的快速排序算法

问题描述：快速分类算法中,如何选取一个界值(又称为轴元素)，影响着快速分类的效率,而且界值也并不一定是被分类序列中的一个元素。例如，可以用被分类序列中所有元素的平均值作为界值。编写算法实现以平均值为界值的快速分类方法。

类似于快速排序 只有
①求平均值Ave的时候要用float值
②while循环结束后不需要再交换
③递归调用的时候，区间范围发生了变化
在快速排序的时候，我们递归调用的区间是head->i-1 和 i+1->tail 就是因为在最后一步交换后可以保证左侧比基准数小，右侧比基准数大。但是在用平均值做基准数的时候我们只能保证最后i、j相遇的地方(设下标为pos)左边比平均值大，右边比平均值小，但是并不能保证左边所有的数一定比pos对应的值小，右边的所有的数一定比pos的值大。所以pos属于没有被拍好的位置，在递归的时候应该把他算作一个边界。

代码如下

/*实现内容
*	按照平均值进行快速排序
* PS：0号不存元素
* VS2019编译通过 王大花 2020.8.21
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define Number_Num 12int* Get_Rand_Num() {int* tmp = (int*)malloc(sizeof(int) * (Number_Num + 1));if (NULL == tmp)return NULL;for (int i = 1; i <= Number_Num; i++)tmp[i] = rand() % 100;return tmp;
}void Print(int* Num) {for (int i = 1; i <= Number_Num; i++)printf("%d ", Num[i]);printf("\n");
}void Swap(int* a, int* b) {int tmp = *a;*a = *b;*b = tmp;
}
//快速排序(平均值为界)
void Quick_Sort(int* Num, int head, int tail) {if (head >= tail)return;int i = head, j = tail, Sum = 0;//计算平均值for (int i = head; i <= tail; i++)Sum += Num[i];float Ave = 1.0f * Sum / (tail - head + 1);while (i < j) {while (i < j && Num[j] >= Ave)j--;while (i < j && Num[i] <= Ave)i++;Swap(Num + i, Num + j);}//注意递归区间Quick_Sort(Num, head, i);Quick_Sort(Num, i + 1, tail);
}int main() {srand((unsigned)time(NULL));int* Num = Get_Rand_Num(Number_Num);Print(Num);Quick_Sort(Num, 1, Number_Num);Print(Num);return 0;
}

运行情况：