【考研复试上机】Ch2 排序与查找

排序

比较函数的法则：当比较函数的返回值为true时，表示的是：比较函数的第一个参数会排在第二个参数前面。

• sort()函数有sort(),stable_sort()和partial_sort()

• sort()函数是对给定区间的元素进行排序，但是会改变值相同的元素的相对位置。

• stable_sort()是对给定区间的元素进行稳定排序，如果两个元素相等，那么排序完成后两个元素的相对位置保持不变

• partial_sort()是对给定区间的元素进行部分排序。默认的顺序是由小到大进行排序。

• nth_element这个函数主要用来将数组元素中第k小的整数排出来并在数组中就位，随时调用

• 三种函数的用法如下

• //comp函数默认为升序方式
  bool ascending(int a, int b) // 升序排序，让小元素放在前面
  {
      // 把a看作序列中前一个元素，b看作后一个元素
      return a < b; // 如果返回true就说明a<b成立，a是较小的元素
  };
  
  bool descending(int a, int b) // 降序排序，让大元素放在前面
  {
      // 把a看作序列中前一个元素，b看作后一个元素
      return a > b; // 如果返回true就说明a>b成立，a是较大的元素
  };
  
  sort(v.begin(),v.end(),comp);
  sort(arr,arr+n);
  
  stable_sort(v.begin(),v.end(),comp)
  
  stable_sort的用法与sort类似
  
  partial_sort(v.begin(),v.begin()+4,v.end(),comp);
  
  nth_element(数组名,数组名+第k小元素,数组名+元素个数)
  

结构体排序

bool cmp(stu x,stu y){
	if(x.score == y.score){
        return x.num<y.num;
    }else{
        return x.score<y.score;
    }
}

vector排序

bool cmp(typename x, typename y){
    return x>y;
}
vector<typename> vi;
sort(vi.begin(),vi.end(),cmp);

查找

二分查找

• 有时会出现left和right非常接近整型最大值的情况，这时如果再用int mid=(left+right)/2会出现溢出的情况，故，改用代码：int mid = left+(right-left)/2;

bool BinarySearch(int arr[],int x){
    int left = 0;
    int right = arr.size()-1;
    while(left<=right){
        int mid = left+(right-left)/2;
        if(arr[mid] == x) return true;
        else if(arr[mid]<x) low = mid+1;
        else high = mid-1;
    }
    return false;
}