排序算法之交换排序和选择排序

前言：王道2025将交换排序分为冒泡排序和快速排序，选择排序分为简单选择排序和堆排序。

一、交换排序

1.冒泡排序

平均时间复杂度：O(N^2)
最佳时间复杂度：O(N)
最差时间复杂度：O(N^2)
空间复杂度：O(1)
排序方式：In-place
稳定性：稳定

cppCopy Code// 冒泡排序算法，将数组a中的n个元素按照升序排序
    
void bubble_sort(int *a, int n) {
  bool flag = true; // 用于标记本轮是否发生交换
  while (flag) {
    flag = false; // 每轮开始前将标记置为false
    for (int i = 0; i < n - 1; ++i) { // 遍历数组中的元素
      if (a[i] > a[i + 1]) { // 如果相邻两个元素逆序
        flag = true; // 标记本轮发生了交换
        int t = a[i]; // 交换两个元素的位置
        a[i] = a[i + 1];
        a[i + 1] = t;
      }
    }
  }
}

2.快速排序

快速排序，又称划分交换排序,通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

① 从数列中挑出一个元素，称为 “基准”（pivot），
② 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③ 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

平均时间复杂度：O(NlogN)
最佳时间复杂度：O(NlogN)
最差时间复杂度：O(N^2)
空间复杂度：根据实现方式的不同而不同

二、选择排序

1.简单选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。

代码实现：

// 选择排序算法，对传入的整型数组进行排序
void selection_sort(int arr[], int len) {
    int i, j, min, temp; // 定义循环变量和临时变量

    // 外层循环，控制需要进行排序的次数
    for (i = 0; i < len - 1; i++) {
        min = i; // 假设当前位置为最小值的索引

        // 内层循环，在未排序部分找到最小的元素
        for (j = i + 1; j < len; j++)
            // 如果当前元素比假设的最小值还要小，则更新最小值的索引
            if (arr[min] > arr[j])
                min = j;

        // 将找到的最小值与当前位置的元素进行交换
        temp = arr[min]; // 临时存储最小值
        arr[min] = arr[i]; // 将最小值放到已排序部分的末尾
        arr[i] = temp; // 将当前位置的元素放到未排序部分的开头
    }
}