排序碎碎念（三）：数据结构基础—统计工龄QuickSort

其实呢&＃xff0c;1&＃xff09;Quicksort也有十分简便的写法的&＃xff0c;比如pivot就挑第一个好啦&＃xff0c;比如对所有的直接递归&＃xff0c;不用考虑一定的间隔用插入排序什么的&＃xff0c;但是要知道的是在C&＃43;&＃43;的内置sort函数中确实就像老师说的那样&＃xff0c;是判断子集的长度&＃xff0c;小于某个值就使用插入排序&＃xff0c;这个版本的快排是比简单粗暴版的快排要好很多的。2&＃xff09;输出统计的那个函数不要写错这道题就基本过了。 当然你用heapsort也可以过这道题。

10-排序4 统计工龄&＃xff08;20 分&＃xff09;

给定公司$N$名员工的工龄&＃xff0c;要求按工龄增序输出每个工龄段有多少员工。

输入格式:

输入首先给出正整数$N$&＃xff08;≤10​5​​&＃xff09;&＃xff0c;即员工总人数&＃xff1b;随后给出$N$个整数&＃xff0c;即每个员工的工龄&＃xff0c;范围在[0, 50]。

输出格式:

按工龄的递增顺序输出每个工龄的员工个数&＃xff0c;格式为&＃xff1a;“工龄:人数”。每项占一行。如果人数为0则不输出该项。

输入样例:

8
10 2 0 5 7 2 5 2

输出样例:

0:1
2:3
5:2
7:1
10:1

// Created by air on 2018/5/12.
//
#define Cutoff (32)
#include
#include
#include
typedef int ElementType;
void QuickSort(ElementType A[], int Left, int Right);
ElementType Median3(ElementType A[], int Left, int Right);
void swap(ElementType *a, ElementType *b);
void Insertion_Sort(ElementType* A, int N);
void print(ElementType A[], int N);
void QSort( ElementType A[], int N );
void Scan( ElementType A[], int total);/* 统一接口 */
void QSort( ElementType A[], int N )
{QuickSort( A, 0, N-1 );
}int main(int argc, const char * argv[]) {int total;scanf("%d",&total);ElementType * A;A &＃61; (ElementType *) malloc(sizeof(ElementType) * total);for(int i &＃61; 0; i }
/* 这个 Scan 函数 写对就可以过了 - - */
void Scan( ElementType A[], int total){int i, count;count &＃61; 1;for(i &＃61; 0; i /*-------------------------------------------------------------QuickSort:当两边都发现有不对的元素之后 ---> 对两遍的元素进行交换元素相等的时候&＃xff0c;仍然停下来交换&＃xff0c;为了子集的均等划分的原因&＃xff1b;小规模的数据(<32)&＃xff0c;使用插入排序&＃xff1b;-------------------------------------------------------------*/
void QuickSort(ElementType A[], int Left, int Right){if(Left &＃43; Cutoff <&＃61; Right){int i &＃61; Left;int j &＃61; Right - 1; //Right肯定在pivot的右边int pivot &＃61; Median3(A, Left, Right);for(;;){while(A[ &＃43;&＃43;i ] pivot) { }if( i }ElementType Median3(ElementType A[], int Left, int Right){int center &＃61; ( Left &＃43; Right ) / 2;if( A[ Left ] > A[ center ] )swap( &A[ Left ], &A[ center ] );if( A[Left] > A[Right])swap( &A[ Left ], &A[ Right ] );if( A[ center ] > A[ Right ])swap( &A[ center ], &A[ Right ] );swap( &A[ center ], &A[ Right - 1 ]);return A[ Right - 1 ];}void swap(ElementType *a, ElementType *b){ElementType tmp;tmp &＃61; *a;*a &＃61; *b;*b &＃61; tmp;
}void Insertion_Sort(ElementType* A, int N){ElementType tmp;int i, j;for( i &＃61; 1; i 0) && (*(A &＃43; j - 1) > tmp); j-- ){*(A &＃43; j) &＃61; *(A &＃43; j - 1);}*(A &＃43; j) &＃61; tmp;}
}
/*-------------------------------------------------------------QuickSort 结束-------------------------------------------------------------*/
/* Print for test! */
void print(ElementType A[], int N){int i;for(i &＃61; 0; i }