0

排序算法的实现

 2 years ago
source link: https://staight.github.io/2019/10/22/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E5%AE%9E%E7%8E%B0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

排序算法简介

排序算法顾名思义，就是用来排序的算法，它可以将一组相同类型的元素从无序转变为有序。

排序算法有多种考量指标：

  • 时间复杂度：描述算法的快慢
  • 空间复杂度：描述算法额外占用的存储空间，如果不占用则可以说是原地排序
  • 稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变

常见的排序算法有：冒泡排序，插入排序，选择排序，归并排序，快速排序，堆排序，计数排序，基数排序，此外似乎还有一个比较奇葩的排序算法叫做睡眠排序。。。

排序算法

接下来实现下前5种排序算法。

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

void popSort(vector<int> &v) {
    for (int i = 0; i < v.size() - 1; i++)
        for (int j = 0; j < v.size() - i - 1; j++)
            if (v[j] > v[j + 1])
                swap(v[j], v[j + 1]);
}

是否原地排序：是
是否稳定：是
时间复杂度：O(n^2)

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

void insertSort(vector<int> &v) {
    for (int i = 1; i < v.size(); i++)
        for (int j = i; j > 0 && v[j] < v[j - 1]; j--)
            swap(v[j], v[j - 1]);
}

是否原地排序：是
是否稳定：是
时间复杂度：O(n^2)

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

void selectSort(vector<int> &v) {
    for (int i = 0; i < v.size() - 1; i++) {
        int pos = i, minn = v[i];
        for (int j = i + 1; j < v.size(); j++) {
            if (v[j] < minn) {
                pos = j;
                minn = v[j];
            }
        }
        swap(v[i], v[pos]);
    }
}

是否原地排序：是
是否稳定：否
时间复杂度：O(n^2)

归并排序使用的就是分治思想，先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

void merge(vector<int> &v, int l, int m, int r) {
    vector<int> num(r - l);
    int t1 = l, t2 = m, t = 0;
    while (t1 != m && t2 != r) {
        if (v[t1] > v[t2])
            num[t++] = v[t2++];
        else
            num[t++] = v[t1++];
    }
    while (t1 != m)
        num[t++] = v[t1++];
    while (t2 != r)
        num[t++] = v[t2++];

for (int i = 0; i < num.size(); i++)
        v[l + i] = num[i];
}

void mergeSort(vector<int> &v, int l, int r) {
    if (l + 1 >= r)
        return;
    int m = (l + r) / 2;
    mergeSort(v, l, m);
    mergeSort(v, m, r);
    merge(v, l, m, r);
}

void mergeSort(vector<int> &v) {
    mergeSort(v, 0, v.size());
}

是否原地排序：否
是否稳定：是
时间复杂度：O(nlogn)

快速排序也使用了分治的思想，快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（哨兵）。

我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。

根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

void quickSort(vector<int> &v, int l, int r) {
    if (l + 1 >= r)
        return;
    int p = v[l];
    int lp = l, rp = r - 1;
    while (lp != rp) {
        while (rp > lp && v[rp] >= p)
            rp--;
        while (lp < rp && v[lp] <= p)
            lp++;
        swap(v[lp], v[rp]);
    }
    swap(v[l], v[lp]);
    quickSort(v, l, lp);
    quickSort(v, lp + 1, r);
}

void quickSort(vector<int> &v) {
    quickSort(v, 0, v.size());
}

是否原地排序：是
是否稳定：否
时间复杂度：O(nlogn)

想找一个所有排序算法的动图来着的，结果发现一篇写的很好的博客，虽然没有参考，不过收藏了：https://www.cnblogs.com/onepixel/articles/7674659.html


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK