[数据结构与算法]Day 14 算法笔记之算法初步4.1 排序

之前的题目都是codeup的，从这一章开始跟着上级训练实战指南刷题了???????

目录

1.选择排序

2.插入排序

3.PAT RANKING

???????

1.选择排序

这里写了一个选择排序的模板，因为现在这个阶段整数数组还不好求长度，就直接对数组长度赋了个4

选择排序分这么几步：

1.要进行n次循环，每次都找出剩下里面最小的那个放到无序的第一位

? ? ? ? 2.无序里面最小的就是通过第二层for循环找出这个最小值的坐标

? ? ? ? 3.找到坐标之后，就将其与第一个进行交换

所以就是双重for循环

void selectSort(int A[]){
	
	int n = 4;
	
	for(int i=0;i<n;i++){
		
		int min_1 = i;
		for(int j=i;j<n;j++){
			if(A[j]<A[min_1]){
				min_1 = j;
			}
		}
		
		int temp = A[min_1];
		A[min_1] = A[i];
		A[i] = temp;
		
	}
	
	for(int i=0;i<n;i++){
		printf("%d ",A[i]);
	}
	
}

2.插入排序

插入排序是假定数组的前一部分是有序，后一部分无序，我们要做的是把无序部分的第一个元素插入到有序部分中去，然后一直重复这个过程，使无序部分消失。

思路如下：

首先我们可以把数组的第一个元素看做是有序的，因为只有它一个。那么从第二个元素开始就是无序的

我们取出无序段的第一个元素，第一次取就是取到整个数组的第二个元素，将其与有序段从后往前比较（因为我们这里是从小到大排列，有序段最后一个就是最大的）。

如果这个元素小于有序段的最后一个元素，那么说明有序段的最后一个元素需要后移一个，

如果这个元素大于该有序段的最后一个元素，那么说明该元素不用移动，就在这个位置

void selectSort(int A[]){
	
	int n = 5;
	
	for(int i=1;i<n;i++){
		
		int min = i;
		int temp = A[i];
		
		for(int j=i-1;j>=0;j--){
			if(temp<A[j]){
				A[j+1]=A[j];
			}else{
				A[j+1] = temp;
				break;
			}
		}
		
	}
	
}

3.PAT RANKING

这一题很有意思

#include <cstdio>
#include <cctype>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;

struct testee{
	
	char reg_num[14];
	int score;
	int local_num;
	
	int local_rank;
	int final_rank;
	
}stu[30000];

bool cmp(testee a, testee b){
	if(a.score!=b.score){
		return a.score>b.score;
	}else{
		return strcmp(a.reg_num,b.reg_num)<0;
	}
}

int main(){
	
	int location;
	scanf("%d",&location);
	
	int whole_num = 0;
	
	for(int j=0;j<location;j++){
		

		
		int local_num;
		scanf("%d",&local_num);
		
		int x = whole_num;
			
		for(int i=x;i<local_num+x;i++){
			whole_num++;
			stu[i].local_num = j+1;
			scanf("%s %d",stu[i].reg_num,&stu[i].score);
		}
		
		sort(stu+x,stu+whole_num,cmp);
		
		stu[x].local_rank=1;
		
		for(int i =x+1;i<local_num+x;i++){
			if(stu[i].score==stu[i-1].score){
				stu[i].local_rank = stu[i-1].local_rank;
			}else{
				stu[i].local_rank = i -x  + 1;
			}
		}
		
	}
	
	sort(stu,stu+whole_num,cmp);
	
	stu[0].final_rank = 1;
	
	for(int i=1;i<whole_num;i++){
		if(stu[i].score==stu[i-1].score){
			stu[i].final_rank = stu[i-1].final_rank;
		}else{
			stu[i].final_rank = i+1;
		}
	}
	
	
	
	
	for(int i=0;i<whole_num;i++){
		printf("%s %d %d %d\n",stu[i].reg_num,stu[i].final_rank,stu[i].local_num,stu[i].local_rank);
	}
	
	
		
	return 0;
}