乐趣区

关于c++:数据结构与算法入门指南-排序

jiezi

数据结构与算法入门指南

理解各个排序的算法原理比拟适宜找工作面试的时候用，在刷题比赛的时候间接应用 sort 函数即可

sort 函数

sort 作为 C ++ 自带的函数，应用频率比拟高，个别遇到须要排序的数组用就行了，能解决大部分须要排序的问题。上面演示一下各种用法。

根底用法

最根底的用法，对数组间接排序（默认从小到大排序）。

int A[10] = {5,4,8,7,6,4,1,6,5,1};
sort(A, A + 10); // A = {1,1,4,4,5,5,6,6,7,8}

sort 函数的前两个参数为首地址与尾地址，示意须要排序一段数组。在上例中，A 有 10 个元素，而应用 A 时会返回 A 的首地址，A + 10 示意在首地址上向后偏移 10 个地位后的地址，用 (A，A + 10) 能够示意 A[0 ~ 9]。

如果只想对前五位排序，也能够这样写sort(A, A + 5)。

对于 STL 中的 vector 也是如此，应用对象中的 begin() 与end()获取首地址与尾地址。

vector<int> A = {5,4,6,8,7,4,1,6,9};
sort(A.begin(), A.end()); // A = {1,4,4,5,6,6,7,8,9}

那么对于自定义的构造体呢？看上面。

自定义排序用法

sort 函数还有第三个可选参数，就是自定义排序的办法，传入办法名或者匿名函数即可。传入的办法的参数必须是两个同类型的且返回值为 bool 类型。

如果不应用第三个参数，sort 函数会默认调用对象的 < 办法来比拟两个对象的大小关系，应用构造体时须要重写一下operator<。

  • 应用匿名函数

    int A[10] = {5,1,7,9,5,4,8,3,1,0};
sort(A, A + 10, [](int a, int b) {return a > b;}); // 从大到小排序
//A = {9,8,7,5,5,4,3,1,1,0}

  • 应用办法

    // 从大到小排序
bool cmp(int a, int b) {return a > b;}

int main()
{int A[10] = {5,1,7,9,5,4,8,3,1,0};
    sort(A, A + 10, cmp); //A = {9,8,7,5,5,4,3,1,1,0}
    return 0;
}

  • 构造体重载operator<

    struct Node 
{
    int a, b;
    // 按 a 对 Node 从小到大排序（与传入的 Node 比拟）bool operator<(Node u) const
    {return a < u.a;}
};

int main()
{Node A[3] =  {{1, 6}, {8, 0}, {4, 5} };
    sort(A, A + 3); // A =  {{1, 6}, {4, 5}, {8, 0} };

    return 0;
}

    当然，也能够抉择不重载operator<，间接传匿名函数或者办法。

less<T>()与greater<T>()

如果只是想让元素 从小到大 或者 从大到小 排序，那么大可不必本人手写一个办法实现，间接应用零碎内置的 less<T>() 与greater<T>()即可，T 为元素类型。

sort(A, A + 10, less<int>()); // 从小到大排序
sort(A, A + 10, greater<int>()); // 从大到小排序
  • less<T>()须要类重载operator<()
  • greater<T>()须要类重载operator>()

疾速排序与归并排序都用了递归实现，如果你对递归并不是很纯熟，能够大略理解后临时跳过，当前再回来看看。

QuickSort 疾速排序

疾速排序先会随机找一个基准点，把小于基准点的数放到右边，把大于基准点的数放到左边，再将区间划分为两半递归执行，始终如此划分上来，就达到了排序的目标。

具体的排序办法：确定基准点后，双指针从数组两端向两头挪动，右边指针先找到大于基准点的，而后右指针挪动到小于基准点的，替换两个指针的数值即可。

援用一下《啊哈！算法》这本书中的疾速排序流程图，将双指针看成两个哨兵。（以左端点 6 为基准点，右指针先登程）

左右指针找到符合条件的值，替换！

替换完之后持续查找，找到后持续替换，直到两个哨兵（双指针）相遇为止。

两个哨兵相遇后，咱们要把基准值放到相遇的地位，也就是两头，毕竟右边都是比基准值小的，左边都是比基准值大的数嘛。



到此第一轮排序结束，但咱们发现整个数组其实并没有齐全排好序，接下来须要将其一直分成左右两个区间反复上述过程最初就能将整个数组排序结束了。

上面咱们来写写代码吧，上模板题！（代码实现与上述过程有所差别，不过原理大致相同）

P1177【模板】疾速排序（留神：该题如果随机选取的数为最右边的数，即 x = A[L]，则会超时）

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 10;
int n, A[maxn];

void quick_sort(int l, int r)
{if (l >= r) return; // 不能再划分区间了，终止
    
    // x 为随机选取的值，i 为终点，j 为起点。int x = A[(l + r) / 2], i = l - 1, j = r + 1;
    while (i < j)
    {while (A[++i] < x); // 找出右边大于 x 的值 (当 A[j] > x 时循环进行 即目前 A[j] > x
        while (A[--j] > x); // 同理找出左边小于 x 的值
        if (i < j) swap(A[i], A[j]); // 如果符合要求则替换
    }
    quick_sort(l, j); // 持续划分右边
    quick_sort(j + 1, r); // 划分左边
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> A[i];

    quick_sort(0, n - 1);

    for (int i = 0; i < n; i++)
        cout << A[i] << ' ';

    return 0;
}

MergeSort 归并排序

归并排序与疾速排序最大的不同就是 疾速排序是先排序再划分，而归并排序是先划分再排序，其中间过程能够了解为合并两个有序数组（这一步须要开额定空间实现）。

合并两个有序数组的办法：比拟两个数组结尾的数，谁小就选谁，最初如果有数组不为空，则一次性全副选取即可。具体题目：88. 合并两个有序数组

咱们没有对数组排过序，又怎么会失去有序数组让咱们合并呢，其实划分最终会划分到每个元素上，对于单个元素而言不须要在意程序了。

仍旧能够应用下面的题目来练手归并排序 P1177【模板】疾速排序

#include<bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 10;
int n, A[maxn], B[maxn];

void merge_sort(int l, int r)
{if (l >= r) return;

    int mid = (l + r) / 2; // 找出中点
    merge_sort(l, mid); merge_sort(mid + 1, r); // 划分两边
    // 合并两个有序数组（当划分到只有一个元素的时候也是有序的）int k = l, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (A[i] <= A[j]) B[k++] = A[i++];
        else B[k++] = A[j++];
    // 两个数组合并结束，只有数组中有元素就放进去（只有一组有，能够保障另一组为空，所以不必做判断）while (i <= mid) B[k++] = A[i++];
    while (j <= r) B[k++] = A[j++];

    for (i = l; i <= r; i++) A[i] = B[i]; // 将排序好的数组笼罩放入原数组中
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> A[i];

    merge_sort(0, n - 1);

    for (int i = 0; i < n; i++)
        cout << A[i] << ' ';

    return 0;
}

对于其余排序算法

大部分算法的工夫复杂度与空间复杂度都没有疾速排序与归并排序好，所以这里就不一一细说了，列举一下其余常见的排序算法，有趣味能够本人理解理解。

  • 冒泡排序
  • 插入排序
  • 希尔排序
  • 抉择排序
  • 桶排序
  • 计数排序
  • 基数排序
  • …

题目

题目列表待减少，洛谷的官网题单是个不错的抉择。

【算法 1 -2】排序 – 题单 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

退出移动版