C++实现常用八大排序算法—实现及其对比

C++中常用的八大排序算法包括：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、计数排序和基数排序。接下来，我们将逐一介绍它们的实现方式、时间复杂度以及优缺点。

1. 冒泡排序
   冒泡排序是一种简单的排序算法，它重复地遍历待排序的序列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历序列的工作是重复地进行直到没有再需要交换，也就是说该序列已经排序完成。

   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]) {
   swap(arr[j], arr[j+1]);
   }
   }
   }
   }

   时间复杂度：O(n^2)。
   优点：实现简单。
   缺点：效率低，当数据量大时不宜使用。
2. 选择排序
   选择排序的基本思想是在未排序的序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后再从剩余未排序的元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

   void selectionSort(int arr[], int n) {
   for (int i = 0; i < n-1; i++) {
   int minIndex = i;
   for (int j = i+1; j < n; j++) {
   if (arr[j] < arr[minIndex]) {
   minIndex = j;
   }
   }
   swap(arr[i], arr[minIndex]);
   }
   }

   时间复杂度：O(n^2)。
   优点：实现简单。
   缺点：效率低，当数据量大时不宜使用。
3. 插入排序
   插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

   void insertionSort(int arr[], int n) {
   for (int i = 1; i < n; i++) {
   int key = arr[i];
   int j = i - 1;
   while (j >= 0 && arr[j] > key) {
   arr[j+1] = arr[j];
   j--;
   }
   arr[j+1] = key;
   }
   }

   时间复杂度：O(n^2)。
   优点：稳定，但当数据量大时不宜使用。
   缺点：效率较低。
4. 快速排序