|
排序算法
|
算法 |
最优复杂度 |
最差复杂度 |
平均复杂度 |
稳定性 |
|
选择排序 |
O(n2) |
O(n2) |
O(n2) |
不稳定 |
|
冒泡排序 |
O(n) |
O(n2) |
O(n2) |
稳定 |
|
插入排序 |
O(n) |
O(n2) |
O(n2) |
稳定 |
|
希尔排序 |
O(n) |
O(n2) |
O(n1.3) |
不稳定 |
|
归并排序 |
O(nlog n) |
O(nlog n) |
O(nlog n) |
稳定 |
|
快速排序 |
O(nlog n) |
O(n2) |
O(nlog n) |
不稳定 |
|
堆排序 |
O(nlog n) |
O(nlog n) |
O(nlog n) |
不稳定 |
|
基数排序 |
O(d(r+n)) |
O(d(n+rd)) |
O(d(r+n)) |
稳定 |
ps : 基数排序的复杂度中, r代表关键字的基数, d代表位数, n代表关键字的个数. 也就是说, 基数排序不受待排序列规模的影响.
冒泡排序
原理 : 每次对比相邻两项的元素的大小, 不符合顺序则交换
void bubblingSort(int array[], int count){
for (int i = 0; i < count; i++) {
// 交换相邻的元素
for (int j = 1; j < count - i; j++) | 