Part1:回顾

1.快速排序

快速排序的思路是这样的，首先选取一个pivot(枢轴元素)，然后将待排数组分为两部分，小于pivot的元素，大于pivot的元素，小于pivot的元素放在pivot元素的前面，大于pivot的元素放在pivot后面，然后对小于pivot的元素和大于pivot的元素分别再采取这个方式处理，具体过程如下：

显然快速排序有随机性，出现随机性的原因是pivot的选取缘故，这里来看个最坏的情形。

为了避免这种情形，老师建议取头，中，尾元素的中位数作为pivot。这里老师还提到在小规模数据时，快速排序可能还不如插入排序，所以老师提出如下解决方案：

2.表排序

在对很庞大的结构排序时，交换两个元素的时间和空间都是很大的，如果使用之前的算法效果会不好，所以就有了表排序这种间接排序。表排序的意思构造指针数组，排序时不交换元素本身，只交换指向元素的指针来排序，可以参考下面一个图来理解：

这里的意思是根据key来排序，可以看到table的第一个指针指向A[3]，因为它的key为a，可以看到table的第二个指针指向A[5]，因为它的key为b，其余的元素同理。

3.基数排序

之前考虑的问题对于待排元素的值没有任何限制，这里考虑待排元素的值有限的情况，就有了桶排序。下面来看个例子。

这里分数只有101种可能，所以构造101个桶，每个桶中放入对应分数的元素，可以看到这种排序的时间复杂度是线性的，比之前直接排序效果要好很多。但这里又有一个问题，如果桶太多，而待排元素较少的时候怎么办呢？如果直接采用桶排序效果肯定不太好，所以就有了基数排序。来看个例子。

这里的思路是首先对个位数排序，然后对十位排序，最后对百位排序，可以看到这样比直接使用桶排序效果要好很多。

基数排序可以应用在多关键字排序，例如扑克牌的排序。

4.各种排序算法的比较

Part2:作业

作业1

10-排序4 统计工龄（20 分）
给定公司N名员工的工龄，要求按工龄增序输出每个工龄段有多少员工。

输入格式:
输入首先给出正整数N（≤100000 ），即员工总人数；随后给出N个整数，即每个员工的工龄，范围在[0, 50]。

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

输入样例:
8
10 2 0 5 7 2 5 2

输出样例:
0:1
2:3
5:2
7:1
10:1

很基础，直接构造51个桶，遍历之后对对应的桶值加1即可。

#include <stdio.h>

int main(){
	//年龄的桶 
	int a[51]={0};
	
	//记录循环次数 
	int n;
	scanf("%d",&n);
	
	//记录年龄 
	int x;
	for(int i=0;i<n;i++){
		scanf("%d",&x);
		a[x]++;
	}
	
	for(int i=0;i<51;i++){
		if(a[i]!=0){
			printf("%d:%d\n",i,a[i]);
		}
	}
	
	return 0;
}

作业2

10-排序5 PAT Judge（25 分）
The ranklist of PAT is generated from the status list, which shows the scores of the submissions. This time you are supposed to generate the ranklist for PAT.

Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive integers, N (≤10000 ), the total number of users, K (≤5), the total number of problems, and M (≤100000 ), the total number of submissions. It is then assumed that the user id’s are 5-digit numbers from 00001 to N, and the problem id’s are from 1 to K. The next line contains K positive integers p[i] (i=1, …, K), where p[i] corresponds to the full mark of the i-th problem. Then M lines follow, each gives the information of a submission in the following format:
user_id problem_id partial_score_obtained
where partial_score_obtained is either −1 if the submission cannot even pass the compiler, or is an integer in the range [0, p[problem_id]]. All the numbers in a line are separated by a space.

Output Specification:
For each test case, you are supposed to output the ranklist in the following format:
rank user_id total_score s[1] … s[K]
where rank is calculated according to the total_score, and all the users with the same total_score obtain the same rank; and s[i] is the partial score obtained for the i-th problem. If a user has never submitted a solution for a problem, then “-“ must be printed at the corresponding position. If a user has submitted several solutions to solve one problem, then the highest score will be counted.
The ranklist must be printed in non-decreasing order of the ranks. For those who have the same rank, users must be sorted in nonincreasing order according to the number of perfectly solved problems. And if there is still a tie, then they must be printed in increasing order of their id’s. For those who has never submitted any solution that can pass the compiler, or has never submitted any solution, they must NOT be shown on the ranklist. It is guaranteed that at least one user can be shown on the ranklist.

Sample Input:
7 4 20
20 25 25 30
00002 2 12
00007 4 17
00005 1 19
00007 2 25
00005 1 20
00002 2 2
00005 1 15
00001 1 18
00004 3 25
00002 2 25
00005 3 22
00006 4 -1
00001 2 18
00002 1 20
00004 1 15
00002 4 18
00001 3 4
00001 4 2
00005 2 -1
00004 2 0

Sample Output:
1 00002 63 20 25 - 18
2 00005 42 20 0 22 -
2 00007 42 - 25 - 17
2 00001 42 18 18 4 2
5 00004 40 15 0 25 -

这题最后一个测试点没过，卡了很久，暂时放一下。题目其实就是有多个比较条件，条件直接有优先级，所以我就对优先级最高的条件乘以一个很大的权重，优先级次之的乘以一个相对较小的权重，以此类推。

#include <stdio.h>
void Swap(int *a,int *b);
void PercDown( int A[], int p, int N );
void HeapSort( int A[], int N );

int main(){
	const int n1=1000000;
	const int n2=10000;
	
	int n,k,m;
	scanf("%d %d %d",&n,&k,&m);
	//读入分值,第一个元素为0 
	int p[k+1]={0};
	for(int i=1;i<k+1;i++){
		scanf("%d",&p[i]);
	}
	
	//读入数据,增加一个维度方便后续处理 
	int a[n+1][k+1]={0};
	//判断有没有交,如果交了则为1 
	int flag[n+1]={0};
	
	for(int i=1;i<n+1;i++){
		for(int j=1;j<k+1;j++){
			a[i][j]=-2;
		}
	}
	
	for (int i=0;i<m;i++){
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		if(z>=-1){
			flag[x]=1;
		}
		if(z>a[x][y]){
			a[x][y]=z;
		}
	}
//	for (int i=0;i<n+1;i++){
//		printf("%d\n",flag[i]);
//	}
	
	//记录总分
	int b[n]={0};
	for (int i=1;i<n+1;i++){
		//记录满分个数 
		int s=0;
		
		for (int j=1;j<k+1;j++){
			if(a[i][j]>0){
				b[i-1]+=n1*a[i][j];
			}
			if(a[i][j]==p[j]){
				s++;
			}
		}
		b[i-1]+=n2*s+(n+1-i);
	}
	HeapSort(b,n);
	
	int index=1;
	int j=1;
	int start=n-1;
	int temp=b[n-1]/n1;
	int s=0;
	
	while(index<=k && j<=n){
		//printf("%d\n",b[n-j]);
		int i=n+1-b[n-j]%n2;
		int score=b[n-j]/n1;
		if (score!=temp){
			index+=s;
			temp=score;
			s=1;
		}else{
			s++;
		}
	if(flag[i]>0){
		printf("%d ",index);
		if(i>=10000){
			printf("%d",i);
		}else if(i>=1000){
			printf("0%d",i);
		}else if(i>=100){
			printf("00%d",i);
		}else if(i>=10){
			printf("000%d",i);
		}else{
			printf("0000%d",i);
		}
		printf(" %d",score);
		for(int p=1;p<=k;p++){
			if(a[i][p]>=0){
				printf(" %d",a[i][p]);
			}else if (a[i][p]==-1){
				printf(" 0");
			}else{
				printf(" -");
			}
		}
		printf("\n");
		}
		j++;
	}
	return 0;
		
}

//交换 
void Swap(int *a,int *b){
	int t=*a;
	*a=*b;
	*b=t;
}

//最大堆下滤 
void PercDown( int A[], int p, int N ){
	/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
	int Parent,Child,x;
	x=A[p];
	
	for(Parent=p;(2*Parent+1)<N;Parent=Child){
		Child=Parent*2+1;
		if((Child<N-1)&&(A[Child]<A[Child+1])){
			Child++;
		}
		if(x>=A[Child]){
			break;
		}else{
			A[Parent]=A[Child];
		}
	}	
	A[Parent]=x;
}

//堆排序 
void HeapSort( int A[], int N ){
	int i;
	
	//从有子节点的点开始 
	for(i=N/2-1;i>=0;i--){
		PercDown(A,i,N);
	}

	for(i=N-1;i>0;i--){
		Swap(&A[0],&A[i]);
		PercDown(A,0,i);
	}
}

作业3

10-排序6 Sort with Swap(0, i)（25 分）
Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:
Each input file contains one test case, which gives a positive N (≤100000) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:
10
3 5 7 2 6 4 9 0 8 1

Sample Output:
9

这题是求最少的交换次数，注释里写的比较详细了，这里不细说。

#include <stdio.h>
void swap(int *a,int *b){
	//printf("%d %d\n",*a,*b);
	int temp=*a;
	*a=*b;
	*b=temp;
	//printf("%d %d\n",*a,*b);
}

int main(){
	int n;
	scanf("%d",&n);
	
	//读入数据 
	int a[n];
	//记录a[i]!=i的元素个数 
	int s=0;
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		if(a[i]!=i){
			s++;
		}
	}
	
	//交换次数 
	int k=0;
	//首先明确一点，除了0以外，其余元素如果已经在自己的位置,那么就不会再移动了 
	//记录和0交换的元素的开始位置 
	int index=1;
	
	
	while(s>0){
		//0在0上，那么和第一个不在自己位置上元素交换 
		if(a[0]==0){
			while(index<n){
				if(a[index]!=index){
					swap(&a[0],&a[index]);
					break;
				}
				//下一次遍历从后一个元素开始 
				index++;
			}
			//a[i]!=i的元素个数加1 
			s++;
			//交换次数加1 
			k++;
		//0不在0上，不妨设a[0]=k,那么直接交换a[0]和a[k]，使得k在a[k]上 
		}else{
			swap(&a[0],&a[a[0]]);
			//如果a[0]正好为0，a[i]!=i的元素个数减少 2，否则减少1 
			if(a[0]==0){
				s-=2;
			}else{
				s--;
			}
			//交换次数加1 
			k++;
		}
	}
	printf("%d",k);
	return 0;
}