七、排序

7.1 简介

• 在c++算法库里有一个强大的排序函数sort,使用方便，速度快，基本上能解决我们在平时遇到的大多数排序问题，使用 sort函数需要包含算法库：#include <algorithm>

7.2 sort 排序

• 定义原型：

  1. void sort (RandomAccessIterator first, RandomAccessIterator last);
  2. void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
  3. 对序列[first,last) 区间的元素默认按升序，如有比较函数，按比较函数规则排序
  4. sort 不是稳定排序(相同的元素在排序后相对位置会发生变化)

• sort(begin, end, cmp)

  • begin ：为指向待待排序数组的第一个元素的指针

  • end ：为指向待排序数组的最后一个元素的下一个位置的指针

  • cmp ：参数为排序的准则，默认以非降序排序

  • 举例说明：

    #include <algorithm>//算法库
    int main() {
        int a[5] = {1, 3, 4, 2, 5};
        std::sort(a+0, a + 5);
        for (int i = 0; i < 5; i++) printf("%d ",a[i]);
        return 0;
    }

  • 自定义cmp参数，降序排序

    #include <cstdio>
    #include <algorithm>//算法库
    bool cmp(int x, int y) {
        return x > y;//这样是降序排序，改成return x<y;呢？
    }
    int main() {
        int a[5] = {1, 3, 4, 2, 5};
        sort(a+0, a + 5, cmp);
        for (int i = 0; i < 5; i++) printf("%d ",a[i]);
        return 0;
    }

  • 对基本数据类型的数组进行排序，我们也可以使用标准库函数进行排序，例如，上述排序的代码可以修改为：

    sort(a, a + 5, less<int>());

7.3 stable_sort 排序

• 定义原型：
  1. void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
  2. void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );
  3. 对序列[first,last) 区间的元素默认按升序，如有比较函数，按比较函数规则排序
  4. stable_sort 是稳定排序(相同的元素在排序后相对位置不变)

7.4 partial_sort 排序

7.4.1 定义原型：

1. void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
2. void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last, Compare comp);
3. 重排元素，使得范围 [first, middle) 含有范围[first, last)中已排序的 middle - first 个最小元素。
4. 范围 [middle, last) 中剩余的元素顺序未指定。
5. 不稳定排序
6. 默认用 operator< 比较元素。否则用给定的二元比较函数comp 比较元素。

7.4.2 实现原理

1. 对原始容器内区间为[first, middle)的元素执行make_heap()操作构造一个最大堆
2. 拿[middle, last)中的每个元素和first进行比较，first内的元素为堆内的最大值
3. 如果小于该最大值，则互换元素位置，并对[first, middle)内的元素进行调整，使其保持最大堆序
4. 比较完之后在对[first, middle)内的元素做一次对排序sort_heap()操作，使其按增序排列。
5. 时间复杂度约 (last-first)log(middle-first) 次应用 cmp。

7.5 结构体排序

1. sort 函数内部排序是用小于号进行比较的，所以我们只需对该类型结构体的小于号进行重载即可

2. 对于结构体排序，还可以用重载结构体或类的比较运算符的方法，上述代码可以修改为：

   struct Stu{
       int yw;
       int sx;
       bool operator <(const Stu& A) const {
           if (yw == A.yw) return sx > A.sx;
           else return yw < A.yw;
       }
   };
   Stu a[1000];
   sort(a+0,a+100);//对数组下标从0～99之间元素按照cmp排序规则排序

   例题：noi.openjudge.cn 1.9 04:谁拿了最多奖学金