快速排序

快速排序思想:

通过一趟排序将待排序记录分割成独立的两部分(取出一个分割点),分割点左边的记录均<分割点,分割点右边的记录均>分割点;

再分别对左边和右边的记录进行排序;

一趟快速排序的具体做法:

1.附设两个直针low和high,他们的初值分别为low和high,设枢轴记录的关键字为pivot,

2.则首先从high所指位置开始向前搜索找到第一个<=pivot的记录,将此记录和枢轴记录交换,

3.然后从low所指位置开始向后搜索,找到第一个>=pivot的记录,将此记录和枢轴记录交换,

4.重复这两步直到low=high为止。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef float ElementType;

void Quick_Sort(ElementType n[], int left, int right);  //快速排序
int Division(ElementType a[], int left, int right);  //快速排序中用到的分割
void Swap(ElementType *a, ElementType *b);

int main()
{
	int num;
	float sum;
	float score[100];
	float result;
	while (scanf("%d", &num) != EOF){
		sum = 0;
		for (int i = 0; i < num; i++){
			scanf("%f", &score[i]);
		}
		Quick_Sort(score, 0, num-1);
		for (int i = 1; i < num - 1; i++){
			sum += score[i];
		}
		for (int i = 0; i < num; i++){
			printf("%.0f ",score[i]);
		}
		result = (float)(sum / (num - 2.0));
		printf("%.2f\n", result);
	}
}

void Swap(ElementType *a, ElementType *b)
{
	ElementType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_Sort(ElementType n[], int left, int right) //快速排序
{
	int i;
	if (left < right){
		i = Division(n, left, right);
		Quick_Sort(n,left,i-1);
		Quick_Sort(n,i+1,right);
	}
}

int Division(ElementType n[], int left, int right)  //快速排序中用到的分割
{
	ElementType base = n[left]; //基准元素
	while (left < right)
	{
		while (left < right && n[right] >= base)
			--right;   //从右向左找第一个比基准小的元素
		n[left] = n[right]; //将比枢轴记录小的记录交换到低端
		while (left < right && n[left] <= base)
			++left;    //从左向右找第一个比基准大的元素
		n[right] = n[left]; //将比枢轴记录大的记录交换到高端
	}
	/*
	一旦两个直针相遇就交换相遇的地方的元素和基准元素,
	这一步的效果是把基准元素放到它应该出现的地方,
	即基准元素左边的元素都<基准元素,基准元素右边的元素都>基准元素。
	*/
	n[left] = base; //基准元素到位
	return left; //返回基准元素所在的位置
}

  

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。