冒泡排序的思想是遍历数组,依次计算相邻元素,按照规则进行交换位置。一般的代码实现如下:
void pop(int nums[], int length) {
for (int i = 0; i < length; i++) {
for (int j = 0; j < length - i - 1; j++) {
if (nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
printf("第%d次冒泡后\n", i);
print(nums, length);
}
}
对一个数组{6,3,2,4,5,1}
,用冒泡排序并将每一趟的排序结果打印出来:
分析第一趟排序,程序会将元素6和后面的每一个元素比较,如果大于后面的元素就将6和这个元素互换。依此类推,这个算法实际经过了6*6趟遍历,时间复杂度为O(n^2)。
但是观察一下就会发现,第4趟排序后实际已经有序了,第5趟排序纯属浪费时间。那么加一个flag标记,如果没有数据交换,就提前退出:
void pop(int nums[], int length) {
for (int i = 0; i < length; i++) {
bool flag = 0;
for (int j = 0; j < length - i - 1; j++) {
if (nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
flag = 1;
}
}
if (flag == 0) {
printf("跳过第%d次冒泡\n", i);
break;
}
printf("第%d次冒泡后\n", i);
print(nums, length);
}
}
这样的结果就变了:
不过是否能说加了优化的冒泡就不再是O(n^2)了?也不能,因为算法的时间复杂度实际是一种平均的度量。比如排序{1,2,3,4,5,6},这个总不能说冒泡的复杂度是O(n)。另外的一个有效度量方法是使用有序度和逆序度来计算。
最好的情况,数组就是有序的,此时交换次数是0;最差的情况,数组是逆序的,就需要进行n(n-1)/2次交换。这样的话去个平均值:n(n-1)/4。所以得出结论冒泡排序的平均时间复杂度就是O(n^2)。
不过以现在计算机的速度,在一些小规模的排序场景下,冒泡也是一种不错的选择,毕竟算法实现起来很简单。
就是将数组分成了已排序和未排序两部分,去遍历未排序数组,将第一个元素拿来去已排序数组里寻找位置插入。
wiki的这个打扑克的例子说的非常好:
那么用代码实现就是:
void insertSort(int a[], int length) {
for (int i = 1; i < length; i++) {
int value = a[i];
int j = i - 1;
for (; j >=0; j--) {
if (a[j] > value) {
a[j+1] = a[j];
} else {
break;
}
}
a[j+1] = value;
printf("第%d次排序后:", i);
print(a, length);
}
}
插入排序的时间复杂度肉眼可见的又是O(n^2)。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。