数据结构学习笔记 | 排序算法(1)
原创
1. 冒泡排序
冒泡排序的思想是遍历数组，依次计算相邻元素，按照规则进行交换位置。一般的代码实现如下：
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)。另外的一个有效度量方法是使用有序度和逆序度来计算。
- 满有序度：n(n-1)/2，在本例中是15
- 初始有序度：初始状态的有序数对的数量，本例中是(2,4)(4,5)，因此是2
- 每次交换都会让有序度+1，因此本例的数组要达到满有序，需要进行15-2次交换
最好的情况，数组就是有序的，此时交换次数是0；最差的情况，数组是逆序的，就需要进行n(n-1)/2次交换。这样的话去个平均值：n(n-1)/4。所以得出结论冒泡排序的平均时间复杂度就是O(n^2)。
不过以现在计算机的速度，在一些小规模的排序场景下，冒泡也是一种不错的选择，毕竟算法实现起来很简单。
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 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
