C++ 冒泡排序/选择排序/插入排序/快速排序/希尔排序_c++冒泡排序记录原序号

1.冒泡排序

冒泡排序是一种简单的排序算法。它通过比较相邻元素的值，来将数组排序。下面是一个使用 C++ 实现冒泡排序的简单例子：

#include <iostream>
 
using namespace std;
 
// 定义一个函数来实现冒泡排序
void bubbleSort(int arr[], int n) {
  // 外层循环，用于遍历整个数组
  for (int i = 0; i < n - 1; i++) {
    // 内层循环，用于比较相邻元素的值
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 如果 arr[j] 大于 arr[j+1]，则交换它们的值
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}
 
int main() {
  // 定义一个数组，并初始化
  int arr[] = {5, 3, 8, 6, 4};
  int n = sizeof(arr) / sizeof(arr[0]);
 
  // 调用冒泡排序函数
  bubbleSort(arr, n);
 
  // 输出排序后的数组
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
 
  return 0;
}

2.选择排序

选择排序是另一种简单的排序算法。它通过每次选择最小或最大的元素来将数组排序。

下面是一个使用 C++ 实现选择排序的简单例子：

#include <iostream>
 
using namespace std;
 
// 定义一个函数来实现选择排序
void selectionSort(int arr[], int n) {
  // 外层循环，用于遍历整个数组
  for (int i = 0; i < n - 1; i++) {
    // 定义变量 minIndex，用于记录最小元素的索引
    int minIndex = i;
    // 内层循环，用于查找最小元素的索引
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 将最小元素与第 i 个元素交换位置
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}
 
int main() {
  // 定义一个数组，并初始化
  int arr[] = {5, 3, 8, 6, 4};
  int n = sizeof(arr) / sizeof(arr[0]);
 
  // 调用选择排序函数
  selectionSort(arr, n);
 
  // 输出排序后的数组
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
 
  return 0;
}

3.插入排序

插入排序是另一种简单的排序算法。它通过将元素插入已经排序好的序列中来将数组排序。

下面是一个使用 C++ 实现插入排序的简单例子：

#include <iostream>
 
using namespace std;
 
// 定义一个函数来实现插入排序
void insertionSort(int arr[], int n) {
  // 从第二个元素开始，依次将每个元素插入已经排好序的序列中
  for (int i = 1; i < n; i++) {
    // 定义变量 j，用于记录当前元素的索引
    int j = i;
    // 如果当前元素小于前一个元素，则向前移动
    while (j > 0 && arr[j] < arr[j - 1]) {
      // 交换当前元素和前一个元素的位置
      int temp = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = temp;
      // 移动到下一个元素
      j--;
    }
  }
}
 
int main() {
  // 定义一个数组，并初始化
  int arr[] = {5, 3, 8, 6, 4};
  int n = sizeof(arr) / sizeof(arr[0]);
 
  // 调用插入排序函数
  insertionSort(arr, n);
 
  // 输出排序后的数组
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
 
  return 0;
}

4.快速排序

快速排序是一种基于分治算法的排序方法。它的基本思想是，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

下面是一个简单的C++实现：

#include <iostream>
#include <vector>
 
void quickSort(std::vector<int> &vec, int left, int right)
{
    if (left >= right) {
        return;
    }
 
    int pivot = vec[left];
    int i = left + 1;
    int j = right;
 
    while (i <= j) {
        while (i <= j && vec[i] < pivot) {
            i++;
        }
 
        while (i <= j && vec[j] >= pivot) {
            j--;
        }
 
        if (i < j) {
            std::swap(vec[i], vec[j]);
        }
    }
 
    std::swap(vec[left], vec[j]);
 
    quickSort(vec, left, j - 1);
    quickSort(vec, j + 1, right);
}
 
int main()
{
    std::vector<int> vec = {5, 4, 3, 2, 1};
    quickSort(vec, 0, vec.size() - 1);
 
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
 
    return 0;
}

在这个实现中，我们首先通过一个循环来划分数组，然后把基准值放到正确的位置。最后，我们递归地对划分出来的两个部分进行排序。

注意：快速排序的时间复杂度取决于划分数组的方式，如果数组已经有序，那么时间复杂度将会变为$O(n^2)$。因此，最好在排序前随机打乱数组的顺序。

5.希尔排序

希尔排序是一种改进的插入排序。它通过将数组按照一定间隔分成若干个子序列，然后对每个子序列进行插入排序，来将数组排序。

下面是一个使用 C++ 实现希尔排序的简单例子：

#include <iostream>
 
using namespace std;
 
// 定义一个函数来实现希尔排序
void shellSort(int arr[], int n) {
  // 定义一个间隔序列
  int gap = n / 2;
  // 循环进行希尔排序
  while (gap > 0) {
    // 对每个间隔序列进行插入排序
    for (int i = gap; i < n; i++) {
      int j = i;
      while (j >= gap && arr[j] < arr[j - gap]) {
        // 交换当前元素和前一个元素的位置
        int temp = arr[j];
        arr[j] = arr[j - gap];
        arr[j - gap] = temp;
        // 移动到下一个元素
        j -= gap;
      }
    }
    // 缩小间隔序列的大小
    gap /= 2;
  }
}
 
int main() {
  // 定义一个数组，并初始化
  int arr[] = {5, 3, 8, 6, 4};
  int n = sizeof(arr) / sizeof(arr[0]);
 
  // 调用希尔排序函数
  shellSort(arr, n);
 
  // 输出排序后的数组
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
 
  return 0;
}