首页 > 代码库 > 快速排序

快速排序

快速排序思想:

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

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

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

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; //返回基准元素所在的位置}

  

快速排序