4.1.1选择排序

void selectSort()
{
     for(int i=0;i<n;i++)
   {
          int k=i;
          for(j=i;j<n;j++)//从i到n的最小值
        {
               if(A[j]《A[k])
             {
                  k=j;
              }
         }
        int temp=A[i];
        A[i]=A[k];
        A[k]=temp;
     }
}

4.1.2插入排序

int A[max],n;//数组下标从0-n-1
void insertSort()
{
       for(int i=1;i<n;i++)
       {
            int temp=A[i];//往后移的过程会把它给挤掉，提前保存，找到位置放在那里
            j=i;
           while(j>0&&temp<A[j-1])
           {
                    A[j]=A[j-1];//比temp大就往后移
                    j--;//继续往前寻找
            }
            A[j]=temp;//最后的位置temp<A[j-1]条件没有满足，就是它的位置
       } 
}

4.1.3排序题与sort函数的应用

6.9.6关于sort函数

• 头文件

#include<algorithm>
using namespace std;

• 格式

sort(首元素地址（必填)，尾元素地址的下一个地址（必填），比较函数（非必填））

• 不填比较函数
  • 对数字递增排序
  • 对char数组，默认字典序。
• 自定义比较函数
  • 基本数据类型

//递减排序
bool cmp(int a ,int b)
{
       return a>b;
}
sort(a,a+4,cmp);、
//比较字符串（按字典序从小到大）
bool cmp(Student a,Sudent b)
{
    return strcmp(a.name,b.name)<0;
}

• 结构体数组

//定义结构体
struct node{
     int x,y;
}ssd[10];
//排序函数
bool cmp(node a,node b)
{
       return a.x>b.x;
}
//如果想x先从大到小排，但x相等的时候y按从小到大排
bool cmp(node a,node b)
{
    if(a.x!=b.x) return a.x>b.x;
   else return a.y<b.y;
}
//main函数中的使用
sort(ssd, ssd+4,cmp);

• 容器的排序
  • vector、string、deque允许排序其他不可以
    • vector
      和int型一样

      //cmp函数和int型一样
      //实际在main函数中使用
      sort(vi.begin(),vi.end(),cmp);
      

    -string
    和char一样

排序题中的小技巧

• 输出名次
  • 一般要求的是分数不同排名不同，分数相同排名相同

  \\第一种方法
  \*先将数组第一个个体(假设数组下标从0开始)的排名记为1,然后遍历剩余个体: 如果当前个体的分数等于上一个个体的分数,那么当前个体的排名等于上一个个体的排名; 否则,当前个体的排名等于数组下标加1。*\
  stu[0].r=1;//已经调整过次序了
  for（int i=1;i<n;i++)
  {
       if(stu[i].score==stu[i-1].score)
       {
          stu[i].r=stu[i-1];
       }
       else{
           stu[i].r=i+1;
       }
  }
  \\直接输出的第二种方法
   \*令int型变量r初值为1,然后遍历所有个体:如果当前个体不是第一个个体且当前个体的分数不等于上一个个体的分数,那么令r等于数组下标加1,这时r就是当前个体的排名,直接输出即可。这样的做法适用于需要输出的信息过多,导致第一种方法代码冗长的情况*\
   int r=1;
  for(int i=0;i<n;i++)
  {
  if(i>0&&stu[i].score!=stu[i-1].score)
  {
    r=i+1;
  }
  //输出当前信息
  }