【推荐阅读】微服务还能火多久?>>> 基础排序(冒泡、选择、插入)学习笔记-LMLPHP

排序:计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

最简单的排序算法是:冒泡排序、选择排序和插入排序。

冒泡排序

基本思想:两个数比较大小,较大的数下沉,较小的数冒起来。

  • 比较相邻的两个数据,如果第二个数小,就交换位置。
  • 从后向前两两比较,一直到比较最前两个数据。最终最小的数被交换到最前面的位置,这样我们就将最小的数放在了最前面的那个位置。
  • 继续重复上述过程,我们能够在第二轮实现将第 \(2\) 小的数放在第 \(2\) 个位置,在第三轮实现将第 \(3\) 小的数放在第 \(3\) 个位置,……,执行 \(n-1\) 轮之后,我们便能保证 \(n\) 个数按照从小到大的顺序排列好了。

基础排序(冒泡、选择、插入)学习笔记-LMLPHP

实现代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, a[1000];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i < n; i ++) {  // 需要执行n-1轮
        for (int j = n-1; j >= i; j --) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]); // swap函数用于交换两个数
            }
        }
    }
    for (int i = 1; i <= n; i ++) cout << a[i] << " ";
    return 0;
}

选择排序

基本思想:

  • 在长度为 \(n\) 的无序数组中,第一次遍历后 \(n-1\) 个数,找到最小的数值与第一个元素交换;
  • 第二次遍历后 \(n-2\) 个数,找到最小的数值与第二个元素交换;
  • ……
  • \(n-1\) 次遍历最后一个数,找到最小的数值与第 \(n-1\) 个元素交换,排序完成。

基础排序(冒泡、选择、插入)学习笔记-LMLPHP

实现代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, a[1000];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i < n; i ++) {  // 执行n-1轮
        for (int j = i+1; j <= n; j ++) {   // j从i+1到n遍历
            if (a[i] > a[j]) {  // 如果a[i]比a[j]大,交换他俩的值
                swap(a[i], a[j]);   // 这样能够该轮循环结束时保证a[i]比它后面的所有数都要小
            }
        }
    }
    for (int i = 1; i <= n; i ++) cout << a[i] << " ";
    return 0;
}

插入排序

基本思想:

在要排序的一组数中,假定前n-1个数已经排好序,现在将第n个数插到前面的有序数列中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

基础排序(冒泡、选择、插入)学习笔记-LMLPHP

我们可以按照理扑克牌的例子来形象地记忆插入排序:

基础排序(冒泡、选择、插入)学习笔记-LMLPHP

实现代码如下:

#include <bits/stdc++.h>
using namespace std;
int n, a[1000];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) {
        int j = i, tmp = a[i];
        while (j>1 && a[j-1]>tmp) {
            a[j] = a[j-1];
            j --;
        }
        a[j] = tmp;
    }
    for (int i = 1; i <= n; i ++) cout << a[i] << " ";
    return 0;
}
04-17 09:26