快速排序
快速排序思想:
通过一趟排序将待排序记录分割成独立的两部分(取出一个分割点),分割点左边的记录均<分割点,分割点右边的记录均>分割点;
再分别对左边和右边的记录进行排序;
一趟快速排序的具体做法:
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; //返回基准元素所在的位置 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。