冒泡排序和插入排序
Wikipedia: 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。
插入排序和冒泡排序在平均和最坏情况下的时间复杂度都是 O(n^2),最好情况下都是 O(n),空间复杂度是 O(1)。 这两者思路非常简单就不给伪码了,下文为C++的实现。
插入排序
void insertion_sort(vector<int> v){
for(int i = 1; i < v.size(); ++i){
int tmp = v[i], j = i - 1;
for(; j >= 0 && v[j] > tmp; --j){
v[j+1] = v[j];
}
v[j+1] = tmp;
}
}
注意
v[j] > tmp
没有写作v[j] >= tmp
,因此提供了排序的稳定性。插入排序可以是稳定的排序算法。
实现思路是这样的:
- 认为第一个元素是排好序的,从第二个开始遍历。
- 拿出当前元素的值,从排好序的序列中从后往前找。
- 如果序列中的元素比当前元素大,就把它后移。直到找到一个小的。
- 把当前元素放在这个小的后面(后面的比当前大,它已经被后移了)。
插入排序的复杂度
最好和最好时间复杂度:
- 如果序列本来是排好序的,那么会触发最好情况。这时只需要
n-1
次比较即可,没有任何元素移动。所以最好情况下时间复杂度是 O(n)。 - 如果序列是逆序排列的,那么会触发最坏情况。这时每个元素都需要一步一步地挪到序列首部。所以最坏情况下的时间复杂度是 O(n^2)。
平均情况下的时间复杂度是 O(n^2),对于几百个元素仍然是很快速的算法,因为实现简单。所以STL中的qsort
都会以插入排序作为快速排序的补充来处理少量元素。
空间复杂度当然是 O(1) 的,插入排序是采用迭代策略实现的,只用了常数个变量而已。
冒泡排序
冒泡排序想必是平生见过最简单的排序算法:
void bubble_sort(vector<int> v){
for(int i=0; i<v.size()-1; i++){
for(int j=0; j<v.size()-1-i; j++){
if(v[j] > v[j+1]) swap(v[j], v[j+1]);
}
}
}
这里
v[j] > v[j+1]
没有用>=
,同样是为了提供稳定的排序。
- 从第一个元素开始,比较相邻的一对元素。
- 如果前面的比后面的大,交换它们。
- 一轮遍历之后最大的元素一定会位于序列结尾。
- 重复1-3,每次将剩下的元素中最大的放到剩下元素组成序列的结尾。
冒泡排序的复杂度
可以看到上述的冒泡排序实现中,任何输入的算法复杂度都是 O(n^2),空间复杂度是常数 O(1)。但可以记录一个不需要交换的位置,把最好情况的时间复杂度降到 O(n):
void bubble_sort(vector<int> v){
int end = v.size();
while(end > 1){
int new_end = 0;
for(int j=0; j<end-1; j++){
if(v[j] > v[j+1]){
swap(v[j], v[j+1]);
new_end = j+1;
}
}
end = new_end;
}
}
上述代码中维护了一个已排好序的序列:$[end, N)$(N是数组大小),每次冒泡会记录最大的那个泡泡的位置作为end
。
直到end == 1
时,说明整个序列已经排好。
因为冒泡排序中每次冒泡都相当于选最大值放到序列结尾,所以$[end, N)$不仅是有序的,而且位置是正确的。
所以end == 1
时,$[1, N)$已经获得了正确的位置,那么元素0的位置自然就确定了(它已经没得选了)。
转载自 Harttle.Land
本文采用 知识共享署名 4.0 国际许可协议(CC-BY 4.0)进行许可。转载请注明来源: https://snowfrs.com/2015/09/28/insertion-bubble-sort.html 欢迎对文中引用进行考证,欢迎指出任何不准确和模糊之处。