算法笔记(1)| 排序

1.简单选择排序

void selectSort(){
    for(int i=0;i<n;i++){
        int k=i;
        for(int j=i;j<n;j++){
            if(a[j]<a[k]){
                k=j;
            }
        }
        int t=a[k];
        a[k]=a[i];
        a[i]=t;
    }
}

2.直接插入排序

void insertSort(){
    for(int i=1;i<n;i++){
        int t=a[i];
        int j=i;
        while(j>0 && t<a[j-1]){
            a[j]=a[j-1];
            j--;
        }
        a[j]=t;
    }
}

3.sort()函数

#include<algorithm>
#inclue<iostream>
using namespace std;

bool cmp(int a,int b){
    return a<b;  //按照从小到大的顺序排列
}


int main(){
    int a[5] = {12,2,43,8,0};
    sort(a,a+5,cmp);  //进行排序
    return 0;
}

4.解题技巧

1.相关结构体的定义
在某些题目中可能会出现学生的考试成绩，学号，排名等信息。这些信息在排名的时候可能会用到，因此可以直接使用结构体来创建学生对象：

struct Student{
    char name[10];
    int score;
    char num[20];
    int rank;
}stu[1000];  //直接定义一个Student的数组

2.cmp函数的编写
在有些题目中可能会有这样的要求：即当学生的成绩相同时，按照学生姓名的字典序进行排列。此时就可以用到cmp函数来使用sort()进行排序：

bool cmp(Student a,Student b){
    if(a.score == b.score){
        return strcmp(a.name,b.name)<0;
    }
    else{
        return a.score<b.score;
    }
}

3.排名的实现
在有一些需要排名的题目当中，可能会有这样的要求：分数不同的排名不同，分数相同的排名相同，但是需要占用一个排名位。解决此类问题的方法是直接再结构体当中定义排名(rank)，然后再进行遍历：

stu[0].rank = 1;
for(int i=1;i<n;i++){
    if(stu[i].score == stu[i-1].score){
        stu[i].rank = stu[i-1].rank; 
    }
    else{
        stu[i].rank = i+1;
    } 
}