入门篇（2）-算法初步-排序

1， 选择排序

对一个序列A中的元素A[1]~A[n],令i从1到n枚举，进行n趟操作，

每趟从待排序部分[i,n]中选择最小的元素。令其与其待排序部分的第一个元素A[i]进行交换，

这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]，于是在n趟操作后，所有元素就会是有序的。

总共进行n趟操作（1<=i<=n）,每趟操作选出排序部分[i,n]中最小的元素，令其与A[i]交换

#include
using namespace std;

void selectSort(){
	for(int i=1;i<=n;i++){
		int k=i;
		for(int j=i;j<=n;j++){
			if(A[j] 
4.1插入排序
 
​ 插入排序中的直接插入排序。
 
直接插入排序是对序列A的n个元素A[1]~A[n],令i从2到n枚举，进行n-1趟操作。
 
假设某一趟时，序列A的前i-1个元素A[1]A[i-1]已经有序，而范围[i,n]还未有序，那么从该趟从范围[1,i-1]中寻找某个位置j，使得将A[i]插入位置j后（此时A[j]A[i-1]会后移一位至A[j+1]~A[i]）,范围[1,i]有序
 
插入排序是将待插入元素一个个插入初始已有序部分的过程，而插入位置的选择遵循了是插入后仍然保持有序的原则，具体做法一般是从后往前枚举已有序部分来确定插入位置
 
int A[maxn],n;
void insertSort(){
	for(int i=2;i<=n;i++){
		int temp=A[i],j=i;
		while(j>1&&temp
 
4.1.3 C++中的sort()函数
 
（1）结构体：
 
const int M=100010;
struct Student{
	char name[10]; //姓名 
	char id[10];  //准考证号 
	int score ; //分数 
	int rank;   //排名 
	
}stu[M];
 
（2）cmp函数的编写
 
bool cmp(Student a, Student b) {
	if(a.score != b.score)
		return a.score >b.score;
	else
	return strcmp(a.name,b.name)<0; 
// return strcmp(a.name,b.name)==-1 是错误的写法。
	}
 
strcmp（）函数是string.h头文件下用来比较两个char型数组的字典序大小的，
strcmp(str1，str2)；
        （1）当str1字典序小于str2时返回一个负数
            (2)当str1字典序等于str2时返回一个0
            （3）当str1字典序大于str2时返回一个正数
 
 
   strcpy(字符数组1，字符数组2)； 把字符数组2复制给字符数组1，包括结束符
 
#include 
#include 
#include 
const int max =100010;
using namespace std;
struct Student {
	char id[15];    //准考证号 
	int score;      //分数 
	int location_number; // 考场号
	int local_rank;  //考场内排名 
}stu[1000010]; 
bool cmp(Student a, Student b){
	if(a.score != b.score)
		return a.score>b.score;
	else
		return a.id0 && stu[i].score !=stu[i-1].score){
			r=i+1;  //当前考生与上一个考生分属不同时，让r更新为人数+1 
		}
		printf("%s ",stu[i].id);
		printf("%d %d %dn",stu[i].location_number,stu[i].local_rank) ;
	} 
	return 0;
}