七、排序

troysps 2020-01-24

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:谁拿了最多奖学金

相关推荐

whats / 0评论 2011-04-10