做网站有什么好的推荐,工作中最常用的45个excel技巧大全,wordpress手机中文版下载地址,做品牌文化的网站本文整理了常见的排序算法#xff0c;采用c编码#xff0c;并对其时间复杂度作以了分析。
1. 冒泡排序#xff08;Bubble Sort#xff09;
实现思路#xff1a;
从数组的第一个元素开始#xff0c;依次比较相邻的两个元素。如果当前元素大于下一个元素#xff0c;则交…本文整理了常见的排序算法采用c编码并对其时间复杂度作以了分析。
1. 冒泡排序Bubble Sort
实现思路
从数组的第一个元素开始依次比较相邻的两个元素。如果当前元素大于下一个元素则交换它们的位置。经过一轮比较最大的元素会“浮”到数组的末尾。重复这个过程每一轮都把未排序部分的最大元素移到正确位置总共需要进行 n - 1 轮n 为数组元素个数。
代码实现
#include iostream
#include vector
using namespace std;void bubbleSort(vectorint arr) {int n arr.size();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 ) O(n) O(n)。最坏情况数组完全逆序需要进行 n - 1 轮比较每轮比较 n - i - 1 次i 为当前轮数时间复杂度为 O ( n 2 ) O(n^2) O(n2)。平均情况时间复杂度也是 O ( n 2 ) O(n^2) O(n2)。
2. 选择排序Selection Sort
实现思路
首先在未排序的序列中找到最小大元素存放到排序序列的起始位置。然后再从剩余未排序元素中继续寻找最小大元素放到已排序序列的末尾。重复这个过程直到所有元素均排序完毕一共需要进行 n - 1 次选择操作n 为数组元素个数。
代码实现
#include iostream
#include vector
using namespace std;void selectionSort(vectorint arr) {int n arr.size();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]);}
}时间复杂度
无论数组初始状态如何都需要进行 n - 1 轮选择操作每轮都要遍历剩余未排序元素所以最好、最坏、平均情况的时间复杂度都是 O ( n 2 ) O(n^2) O(n2)。
3. 插入排序Insertion Sort
实现思路
将数组分为已排序和未排序两部分初始时已排序部分只有第一个元素。取未排序部分的第一个元素将其插入到已排序部分的合适位置使得已排序部分依然有序。重复这个过程直到未排序部分为空。
代码实现
#include iostream
#include vector
using namespace std;void insertionSort(vectorint arr) {int n arr.size();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 ) O(n) O(n)。最坏情况数组完全逆序每次插入都要和已排序部分的所有元素比较并移动时间复杂度为 O ( n 2 ) O(n^2) O(n2)。平均情况时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
4.希尔排序Shell Sort
实现思路
希尔排序是对插入排序的改进它的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。首先选择一个合适的间隔称为“步长”或“增量”通常初始化为数组长度的一半然后每次缩小一半直到步长为1。按照选定的步长对相隔该步长的元素组成的子序列进行插入排序例如步长为 gap 时会把数组分成多个子序列分别是 arr[0], arr[gap], arr[2 * gap],... 、arr[1], arr[1 gap], arr[1 2 * gap],... 等这些子序列对每个子序列进行插入排序操作。随着步长逐渐减小子序列的元素个数逐渐增多当步长最终减为1时整个数组就相当于进行了一次普通的插入排序但此时由于前面以较大步长进行了预排序元素已经相对更接近最终位置所以最后一次插入排序会比直接对原始数组进行插入排序效率更高。
代码实现
#include iostream
#include vector
using namespace std;void shellSort(vectorint arr) {int n arr.size();for (int gap n / 2; gap 0; gap / 2) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}时间复杂度
希尔排序的时间复杂度与所选取的步长序列有关它的时间复杂度分析比较复杂。最好情况当数组已经有序时时间复杂度接近 O ( n ) O(n) O(n)因为每个子序列在插入排序时几乎不需要移动元素。最坏情况时间复杂度依赖于步长序列不同的步长序列会导致不同的最坏情况时间复杂度不过通常认为其最坏情况时间复杂度在 O ( n 2 ) O(n^2) O(n2) 左右例如使用 Hibbard 序列作为步长时最坏情况为 O ( n 3 / 2 ) O(n^{3/2}) O(n3/2) 等。平均情况平均时间复杂度介于 O ( n ) O(n) O(n) 和 O ( n 2 ) O(n^2) O(n2) 之间常见的分析结果大约是 O ( n 1.3 ) O(n^{1.3}) O(n1.3) 左右。
5. 快速排序Quick Sort
实现思路
选择一个基准元素通常是数组的最后一个元素。通过一趟排序将数组分为两部分左边部分的元素都小于等于基准元素右边部分的元素都大于基准元素。对左右两部分分别递归地进行快速排序直到子数组的长度为1或者0。
代码实现
#include iostream
#include vector
using namespace std;int partition(vectorint arr, int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return i 1;
}void quickSort(vectorint arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}时间复杂度
最好情况每次划分都能把数组均匀地分成两部分时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。最坏情况数组已经有序或者逆序每次划分只得到一个元素和剩余元素的子数组时间复杂度为 O ( n 2 ) O(n^2) O(n2)。平均情况时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
6. 归并排序Merge Sort
实现思路
采用分治思想先将数组不断地分成两半直到每个子数组只有一个元素这是递归分解的过程。然后将相邻的子数组合并成有序的数组合并时比较两个子数组的元素依次放入新的临时数组中再将临时数组的元素复制回原数组对应位置这是合并的过程。重复合并过程直到整个数组有序。
代码实现
#include iostream
#include vector
using namespace std;void merge(vectorint arr, int l, int m, int r) {int n1 m - l 1;int n2 r - m;vectorint L(n1), R(n2);for (int i 0; i n1; i) {L[i] arr[l i];}for (int j 0; j n2; j) {R[j] arr[m 1 j];}int i 0, j 0, k l;while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];} else {arr[k] R[j];}}while (i n1) {arr[k] L[i];}while (j n2) {arr[k] R[j];}
}void mergeSort(vectorint arr, int l, int r) {if (l r) {int m l (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}时间复杂度
无论数组初始状态如何每次划分都是 O ( 1 ) O(1) O(1) 的时间复杂度合并操作总的时间复杂度为 O ( n ) O(n) O(n)一共要进行 log n \log n logn 层划分与合并所以时间复杂度始终为 O ( n log n ) O(n \log n) O(nlogn)。
7. 堆排序Heap Sort
实现思路
首先将数组构建成一个最大堆从最后一个非叶子节点开始对每个节点进行堆化操作保证父节点大于等于子节点。然后把堆顶元素最大值与堆的最后一个元素交换此时最大值就在正确的排序位置了接着对剩下的元素重新进行堆化使其再次成为最大堆。重复这个过程直到整个数组有序。
代码实现
#include iostream
#include vector
using namespace std;void heapify(vectorint arr, int n, int i) {int largest i;int l 2 * i 1;int r 2 * i 2;if (l n arr[l] arr[largest]) {largest l;}if (r n arr[r] arr[largest]) {largest r;}if (largest! i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(vectorint arr) {int n arr.size();for (int i n / 2 - 1; i 0; --i) {heapify(arr, n, i);}for (int i n - 1; i 0; --i) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}时间复杂度
建堆过程时间复杂度为 O ( n ) O(n) O(n)每次调整堆的时间复杂度为 O ( log n ) O(\log n) O(logn)总共需要进行 n - 1 次调整堆操作所以时间复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
8.基数排序
实现思路
基数计数与分配 基数排序的核心思想是根据数字的每一位来进行排序。对于一个整数数组首先确定数字的最大位数(d)例如对于十进制数最大位数可能是数组中最大数的位数。从最低位个位开始依次对每一位进行排序。对于每一位创建(r)个桶对于十进制数(r 10)即0 - 9号桶。遍历数组中的每个元素根据当前位的数字值将元素放入相应的桶中。例如如果当前位是个位数字(123)的个位是(3)则将(123)放入(3)号桶中。 收集与重复 按照桶的顺序从(0)号桶到(r - 1)号桶依次收集元素将桶中的元素放回原数组此时原数组就按照当前位进行了排序。然后处理下一位重复上述分配和收集的过程直到处理完最高位。这样经过(d)轮处理后数组就完成了排序。
时间复杂度
平均情况 时间复杂度为(O(d(r n)))其中(d)是数字的最大位数(r)是基数例如十进制数(r 10)(n)是待排序元素的个数。分析如下对于每一位共(d)位需要遍历(n)个元素来分配到®个桶中这一步的时间复杂度是(O(n))。然后需要遍历®个桶来收集元素时间复杂度是(O®)。所以每一位的处理时间复杂度是(O(n r))总共(d)位所以平均时间复杂度是(O(d(n r)))。 最好情况 当所有元素的位数都相同时时间复杂度为(O(d(n r)))这与平均情况相同。因为即使元素已经有序基数排序仍然需要按照每一位进行处理。 最坏情况 时间复杂度为(O(d(n rd)))。这种情况可能发生在所有元素的最高位都不同并且每一位的取值范围很大接近(r)。在这种情况下对于每一位都需要处理所有的桶而桶的数量最多可以达到(rd)例如当所有元素的每一位都不同时。
代码实现对十进制整数数组进行排序
#include iostream
#include vector
#include algorithm// 基数排序函数
void radixSort(std::vectorint arr) {// 找到数组中的最大值确定最大位数int maxVal *std::max_element(arr.begin(), arr.end());for (int exp 1; maxVal / exp 0; exp * 10) {// 创建计数数组用于统计每个桶中的元素个数std::vectorint count(10, 0);// 计算每个元素在当前位上的数字统计每个桶中的元素个数for (int i 0; i arr.size(); i) {count[(arr[i] / exp) % 10];}// 计算计数数组的前缀和确定每个桶中元素在输出数组中的位置for (int i 1; i 10; i) {count[i] count[i - 1];}// 创建输出数组用于存储排序后的结果std::vectorint output(arr.size());// 将元素放入相应的桶中并按照顺序放入输出数组for (int i arr.size() - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}// 将排序后的结果复制回原数组for (int i 0; i arr.size(); i) {arr[i] output[i];}}
}
测试程序
可用以下代码测试这些排序算法将所要测试的代码取消注释即可此时为测试堆排序
int main() {vectorint arr { 5, 4, 3, 2, 1 };// bubbleSort(arr);// selectionSort(arr);//shellSort(arr);// insertionSort(arr);// quickSort(arr, 0, arr.size() - 1);// mergeSort(arr, 0, arr.size() - 1);// radixSort(arr);heapSort(arr);for (int num : arr) {cout num ;}cout endl;return 0;
}各排序算法总结与比较
类别排序方法时间复杂度空间复杂度稳定性备注平均情况最好情况最坏情况辅助存储插入排序直接插入 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定数据量小时较好Shell排序 O ( n 1.3 ) O(n^{1.3}) O(n1.3) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定选择排序直接选择 O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)不稳定数据量小时较好堆排序 O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( 1 ) O(1) O(1)不稳定数据量大时较好交换排序冒泡排序 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^2) O(n2) O ( 1 ) O(1) O(1)稳定数据量小时较好快速排序 O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n 2 ) O(n^2) O(n2) O ( log 2 n ) O(\log_2 n) O(log2n)不稳定数据量大时较好归并排序 O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n log 2 n ) O(n\log_2 n) O(nlog2n) O ( n ) O(n) O(n)稳定数据量大时较好基数排序 O ( d ( r n ) ) O(d(r n)) O(d(rn)) O ( d ( n r d ) ) O(d(n r^d)) O(d(nrd)) O ( d ( r n ) ) O(d(r n)) O(d(rn)) O ( r d n ) O(r^d n) O(rdn)稳定
注基数排序的复杂度中 r r r代表关键字的基数 d d d代表长度 n n n代表关键字的个数
总结
不同的排序算法在不同场景下有不同的性能表现。插入排序在数据量小且基本有序时效率较高选择排序简单但效率相对较低交换排序中的冒泡排序适用于数据量小的情况快速排序在平均情况下性能很好但最坏情况较差堆排序适用于数据量大且不需要稳定排序的情况归并排序性能稳定但需要额外空间基数排序适用于对整数等有特定结构数据的排序且在数据范围有限时效率较高。在实际使用时根据数据特点和需求选择合适的排序算法。
