C++数据结构与算法--常见排序算法(冒泡、快速、归并、插入、选择、希尔排序、堆...)
本文由博主经过查阅网上资料整理总结后编写，如存在错误或不恰当之处请留言以便更正，内容仅供大家参考学习。
冒泡排序
主要思想：反复调用单趟扫描交换算法，直至逆序现象完全消除(依次比较两个数大小，较大的数下沉，较小的数冒起来，获得单趟扫描最大值放到数组尾部，继续循环)
过程理解：
比较相邻的两个数据，如果第一个数大，就交换位置。
从前向后两两比较，一直到比较最后两个数据。最终最大数被交换到末尾的位置。
继续重复上述过程，依次将第2.3...n-1个最大数排好位置。
性能分析：
N个数总共进行N-1趟排序，第i趟的排序次数为(N-i)次，用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
(1) 时间复杂度
当原始序列杂乱无序时，冒泡排序的平均时间复杂度为O(n^2)。
当原始序列“正序”排列时，冒泡排序总的比较次数为n-1，移动次数为0，在最好情况下的时间复杂度为O(n)；
当原始序列“逆序”排序时，冒泡排序总的比较次数为n(n-1)/2，移动次数为3n(n-1)/2次，最坏情况下的时间复杂度为O(n^2)；
(2) 空间复杂度
冒泡排序排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。
(3) 稳定性
冒泡排序在排序过程中，元素两两交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
C++实现代码：
/*-----------------------数组实现-----------------------------------*/
template<typename T>
void bubble_sort(T arr[], int len) {
int i, j;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
/*-----------------------vector实现-----------------------------------*/
template<typename T>
void bubble_sort(vector<T> &arr, int len) {
int i, j;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
} 改进版本：添加每次循环进行一次是否已经有序判断，如果有序了就直接返回
//改进版本
template<typename T>
void bubble_sort(T arr[], int len) {
int i, j;
for (i = 0; i < len - 1; i++) { //控制循环的次数
bool sorted = true; //整体有序标志
for (j = 0; j < len - 1 - i; j++) //内循环，找出最大数
if (arr[j] > arr[j + 1]) {
sorted = false; //记录存在逆序
swap(arr[j], arr[j + 1]);
}
if (sorted) break; //如果都有序则直接结束
}
} 选择排序
主要思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
过程理解：
比较未排序区域的元素，选出最大或最小的元素放到排序区域。
一趟比较完成之后，再从剩下未排序的元素开始比较。
反复执行以上步骤，n-1趟结束，数组实现有序化。
性能分析
时间复杂度：最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)，用到它的时候，数据规模越小越好
空间复杂度：不占用额外的内存空间O(1)
稳定性：最稳定的排序算法之一
C++代码实现
template<typename T>
void selectSort(vector<T> &arr) {
if (arr.size() <= 1) return;
//进行n-1趟循环
for (int i = 0; i < arr.size() - 1; i++) {
//每趟循环找出无序序列中最小的元素放到有序序列后面
for (int j = i + 1; j < arr.size(); j++)
if (arr[i] > arr[j]) swap(arr[i], arr[j]);
}
}
template<typename T>
void selectSort(T arr[],int len) {
if (len <= 1) return;
//进行n-1趟循环
for (int i = 0; i < len - 1; i++) {
//每趟循环找出无序序列中最小的元素放到有序序列后面
int min = i; //记录本次选择目标最小元素的下标
for (int j = i + 1; j < len; j++)
if (arr[j] < arr[min]) min = j;
swap(arr[i], arr[min]);
}
} 插入排序
主要思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
过程理解：
第1趟插入：将第2个元素插入前面的有序子序列，此时前面只有一个元素，当然是有序的
第2趟比较：将第3个元素插入前面的有序子序列，前面的2个元素是有序的
......
第n-1趟比较：将第n个元素插入前面的有序子序列，前面n-1个元素是有序的
性能分析：
(1) 时间复杂度：最好O(n), 最坏 O(n2), 平均O(n2)
(2) 空间复杂度：O(1)
(3) 稳定性：稳定
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；比较适合于数据量较小的序列排序
C++实现代码：
template<typename T>
void insertSort(vector<T> &arr) {
//从第二个数开始判断插入到有序序列中，直到最后一个数
for (int i = 1; i < arr.size(); i++) {
int temp = arr[i];
int j;
//为a[i]在前面的arr[0...i-1]有序区间中找一个合适的位置
for (j = i - 1; j >= 0; j--) {
//将大于temp的数向后移动一位
if (temp<arr[j]) {
arr[j + 1] = arr[j];//记录j的值也就是temp要插入的位置
}
else break;
}
arr[j+1] = temp; //将值插入序列特定位置
}
}
template<typename T>
void insertSort(vector<T> &arr) {
//从第二个数开始判断插入到有序序列中，直到最后一个数
for (int i = 1; i < arr.size(); i++) {
//为a[i]在前面的arr[0...i-1]有序区间中找一个合适的位置
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr[j], arr[j+1]);
}
}
} 优化：在0~i-1个有序元素给第i个元素寻找插入的位置时，使用二分查找法可以有效提高查找插入位置的时间效率，经过优化的插入排序称为折半插入排序
template<typename T>
void binaryInserSort(vector<T> &arr) {
//从第二个数开始判断插入到有序序列中，直到最后一个数
for (int i = 1; i < arr.size(); i++) {
int tmp = arr[i];
int left = 0;
int right = i - 1;
// 通过二分查找找到插入的位置
while (left <= right) {
int mid = (left + right) / 2;
//如果中间元素大于tmp，则目标位置在中间位置的右侧
if (tmp > arr[mid]) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
// 插入位置之后的元素依次向后移动
for (int j = i; j > left; j--) {
arr[j] = arr[j - 1];
}
// 更新插入位置的值
arr[left] = tmp;
}
} 希尔排序
主要思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。（插入排序改进）https://blog.csdn.net/qq_39207948/article/details/80006224
过程理解
选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
性能分析
时间复杂度：最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlog²n) 平均情况：T(n) = O(nlog²n)
稳定性：不稳定
C++代码实现
template<typename T>
void shell_sort(vector<T> &arr, int len) {
//拆分整个序列，元素间距为gap(也就是增量)
for (int gap = len / 2; gap >= 1; gap = gap / 2) {
//对子序列进行直接插入排序
for (int i = gap; i < len; i++) {
for (int j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j = j - gap) {
swap(arr[j], arr[j + gap]);
}
}
}
归并排序
主要思想：各层分治递归调用二路归并算法，直至逆序现象完全消除(将两个有序序列合并为一个有序序列)
注：二路归并属于迭代算法，每步迭代中，只需比较带归并序列的首元素，将小者取出并追加到输出序列的尾部，该元素在原序列中的后继称为新的首元素。如此往复，直至某一序列为空。最后，将另一非空的序列整体接在输出序列的末尾。
过程理解：
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用二路归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
性能分析：
(1) 时间复杂度
设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共均需要复杂度O(N*logN)
(2) 空间复杂度
空间复杂度：O(N)，归并排序需要一个与原数组相同长度的数组做辅助来排序
(3) 稳定性
归并排序是稳定的排序算法，temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];这行代码可以保证当左右两部分的
值相等的时候，先复制左边的值，故为稳定算法
C++实现代码：
template<typename T>
void merge(vector<T> &arr, int L, int mid, int R) { //有序向量的逐层归并
vector<int> temp; //临时变量用来存放本次合并后的数组
int p1 = L;
int p2 = mid + 1;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while (p1 <= mid && p2 <= R) {
temp.push_back(arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]);
}
// 上面的循环退出后，把剩余的元素依次填入到temp中，只有一个while会执行
while (p1 <= mid) {
temp.push_back(arr[p1++]);
}
while (p2 <= R) {
temp.push_back(arr[p2++]);
}
// 把最终的排序的结果复制给原数组
for (int i = 0; i < temp.size(); i++) {
arr[L + i] = temp[i];
}
}
template<typename T>
void mergeSort(vector<T> &arr , int L, int R) { //无序向量的逐层分解
if (L == R) { //只有一个元素的时候返回
return;
}
int mid = L + ((R - L) >> 1);
mergeSort(arr, L, mid);
mergeSort(arr, mid + 1, R);
merge(arr, L, mid, R);
} 快速排序
主要思想：采用双向查找的策略，每一趟选择当前子序列中的一个数作为key值，将子序列中比key值小数放在它的左边，大于或等于它的数全部放在它的右边；一趟排序完成后实现将要排序的数据按照key为分割点划分成独立的两个子序列。接着分别对这两部分记录继续进行排序，以达到整个序列有序。http://www.sohu.com/a/246785807_684445；https://blog.csdn.net/nrsc
过程理解(挖坑填数)：
定义临时变量tmp存储基准数据key；然后分别从数组的两端扫描数组，设两个指示标志:low指向起始位置，high指向末尾.。
从后半部分开始，如果扫描到的值大于基准数据就让high减1，若有元素比该基准数据的值小，就将high位置的值赋值给low位置
接着从前往后，如果扫描到的值小于基准数据就让low加1，若有元素大于基准数据的值，就再将low位置的值赋值给high位置
然后再从后向前，原理同上，直到low与high位置重合，此时low或high的下标即基准数据key在该数组中的正确索引位置
性能分析：
(1) 时间复杂度
快速排序的平均时间复杂度也是：O(nlogn)
最优时间复杂度：O(nlogn)
最差的情况就是每一次取到的元素就是数组中最小/最大的，该情况下时间复杂度为：O( n^2 )
(2) 空间复杂度
快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N次的分割处理，所以占用空间也是 Nlog2N 个。
(3) 稳定性
在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。
C++实现代码：
//寻找基准值
template<typename T>
int getBase(vector<T> &arr, int low, int hi) {
// 以最左边的数(left)为基准
int tmp = arr[low];
while (low < hi) {
// 从序列右端开始，向左遍历，直到找到小于base的数
while (low < hi&&arr[hi] >= tmp) {
hi--;
}
// 找到了比base小的元素，将这个元素放到最左边的位置
arr[low] = arr[hi];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (low < hi&&arr[low] <= tmp) {
low++;
}
// 找到了比base大的元素，将这个元素放到最右边的位置
arr[hi] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
arr[low] = tmp;
return low;
}
//快速排序
template<typename T>
void quickSort(vector<T> &arr, int low, int hi) {
// 左下标一定小于右下标，否则就越界了
if (low < hi) {
// 对数组进行分割，取出下次分割的基准标号
int base = getBase(arr, low, hi);
// 对“基准标号“左右侧的数值分别进行递归的切割，以至于将这些数值完整的排序
quickSort(arr, 0, base - 1);
quickSort(arr, base + 1, 0);
}
}
//简化版本
template<typename T>
void quickSort(T arr[], int low, int hi)
{
int s_low = low;
int s_hi = hi;
if (low < hi){
int temp = arr[low];
while (s_low < s_hi)
{
//从序列右端开始，向左遍历，直到找到小于base的数
while (s_hi > s_low && arr[s_hi] >= temp) s_hi--;
//找到比基准值小的元素，将这个元素放到最左边的位置
arr[s_low] = arr[s_hi];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (s_low < s_hi && arr[s_hi] < temp) s_low++;
//找到了比base大的元素，将这个元素放到最右边的位置
arr[s_hi] = arr[s_low];
}
arr[s_low] = temp;
// 对“基准标号“左右侧的数值分别进行递归的切割，以至于将这些数值完整的排序
quickSort(arr, low, s_low - 1);
quickSort(arr, s_low + 1, hi);
}
} 堆排序
未完.....
京公网安备 11010502036488号