C++番外篇-------排序算法总结

1.冒泡排序        

        冒泡排序是一种简单的排序算法，它通过重复遍历要排序的列表，依次比较每对相邻项，并在必要时交换它们，从而使较大的元素逐渐“浮”到列表的顶部，而较小的元素则“沉”到底部。

以下是冒泡排序的基本步骤：

1. 从列表的第一个元素开始，依次比较相邻的两个元素。
2. 如果顺序不正确（例如，前一个元素大于后一个元素），则交换它们。
3. 继续进行这样的遍历和比较，直到到达列表的末尾。
4. 重复以上步骤，直到整个列表都被排序。

下面是用C++实现的冒泡排序算法示例：

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

2.选择排序

        选择排序（Selection Sort）是一种简单直观的排序算法，它的基本思想是每次从待排序的元素中选择最小（或最大）的元素，然后放到已排序序列的末尾，直到全部元素都排序完成。

下面是选择排序的基本步骤：

1. 从待排序序列中找到最小（或最大）的元素。
2. 将找到的最小（或最大）元素与待排序序列的第一个元素交换位置。
3. 在剩余的待排序序列中继续执行上述步骤，直到所有元素都排序完成。

选择排序的时间复杂度为 O(n^2)，其中 n 是待排序序列的长度，因此它在大部分情况下不如快速排序、归并排序等高效。然而，选择排序有一个优点，即它的空间复杂度为 O(1)，是一种原地排序算法，不需要额外的存储空间。

以下是选择排序的 C++ 实现示例：

void selectionSort(vector<int>& v)
{int n=v.size();for(int i=0;i<n-1;i++){int min=i;for(int j=i+1;j<n;j++){if(v[j]<v[min]){min=j;}}int temp=v[i];v[i]=v[min];v[min]=temp;}
}

3.插入排序

        插入排序是一种简单的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。

基本步骤：

1. 从第一个元素开始，该元素可以认为已经排序。
2. 取出下一个元素，在已排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5。

C++实现：

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

4.快速排序

快速排序是一种非常高效的排序算法，它采用分治法（Divide and Conquer）的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序这两个子序列。

基本步骤：

1. 从数列中挑出一个元素，称为"基准"（pivot）。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
3. 递归地（分别对基准前后的子序列）重复这个过程。

C++实现：

void quickSort(vector<int>& v, int low, int high) {if (low < high) {int partitionIndex = partition(v, low, high);quickSort(v, low, partitionIndex - 1);quickSort(v, partitionIndex + 1, high);}
}int partition(vector<int>& v, int low, int high) {int pivot = v[high];int i = (low - 1);for (int j = low; j <= high - 1; j++) {if (v[j] <= pivot) {i++;swap(v[i], v[j]);}}swap(v[i + 1], v[high]);return (i + 1);
}

6.堆排序

堆排序是一种利用堆这种数据结构的排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

基本步骤：

1. 创建最大堆。
2. 将堆的根节点与最后一个节点交换，然后断开最后一个节点。
3. 调整剩下的节点，使其满足最大堆的性质。
4. 重复步骤2和3，直到所有节点都被断开。

C++实现：

void heapify(vector<int>& v, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && v[left] > v[largest])largest = left;if (right < n && v[right] > v[largest])largest = right;if (largest != i) {swap(v[i], v[largest]);heapify(v, n, largest);}
}void heapSort(vector<int>& v) {int n = v.size();for (int i = n / 2 - 1; i >= 0; i--)heapify(v, n, i);for (int i = n - 1; i > 0; i--) {swap(v[0], v[i]);heapify(v, i, 0);}
}

7.归并排序

        归并排序是采用分治法的一个非常典型的应用。其思想是将待排序的数组分成若干个小组，每个小组内部排序，然后将排序好的小组两两合并，最终合并为完全排序的数组。

基本步骤：

1. 将数组分成两半。
2. 递归地将这两半分别排序。
3. 合并两个已排序的半部分。

C++实现：

void merge(vector<int>& v, int left, int middle, int right) {int n1 = middle - left + 1;int n2 = right - middle;vector<int> L(n1), R(n2);// 拷贝数据到临时数组L[]和R[]for (int i = 0; i < n1; i++)L[i] = v[left + i];for (int j = 0; j < n2; j++)R[j] = v[middle + 1 + j];// 合并临时数组到v[left..right]int i = 0; // 初始索引第一个子数组int j = 0; // 初始索引第二个子数组int k = left; // 初始索引合并的数组while (i < n1 && j < n2) {if (L[i] <= R[j]) {v[k] = L[i];i++;} else {v[k] = R[j];j++;}k++;}// 拷贝L[]剩余的元素while (i < n1) {v[k] = L[i];i++;k++;}// 拷贝R[]剩余的元素while (j < n2) {v[k] = R[j];j++;k++;}
}void mergeSort(vector<int>& v, int left, int right) {if (left < right) {// 找到中间索引int middle = left + (right - left) / 2;// 分别对左右两半排序mergeSort(v, left, middle);mergeSort(v, middle + 1, right);// 合并两半merge(v, left, middle, right);}
}

8.桶排序

        桶排序是一种将待排序数据分到几个有序的桶里，每个桶里的数据再分别排序的排序算法。适用于数据分布均匀且范围不大的情况。

基本步骤：

1. 设置一个定量的数组当作空桶。
2. 遍历输入数据，并且把数据一个一个放到对应的桶里去。
3. 对每个非空的桶进行排序。
4. 从不是空的桶里把排好序的数据拼接起来。

C++实现：

void bucketSort(vector<int>& v) {int n = v.size();if (n <= 0) return;// 找到最大值和最小值int minValue = v[0];int maxValue = v[0];for (int i = 1; i < n; i++) {if (v[i] < minValue) minValue = v[i];else if (v[i] > maxValue) maxValue = v[i];}// 创建桶的数量int bucketCount = maxValue - minValue + 1;vector<vector<int>> buckets(bucketCount);// 将每个元素放入相应的桶for (int i = 0; i < n; i++) {buckets[v[i] - minValue].push_back(v[i]);}// 对每个桶进行排序int index = 0;for (int i = 0; i < bucketCount; i++) {int bucketSize = buckets[i].size();if (bucketSize > 0) {// 这里可以插入排序，也可以是其他排序算法sort(buckets[i].begin(), buckets[i].end());for (int j = 0; j < bucketSize; j++) {v[index++] = buckets[i][j];}}}
}