改进冒泡排序,使算法在序列达到有序状态时停止运行。
时间: 2024-03-14 16:32:28 浏览: 15
对于您的问题,我可以给出以下优化:
常规冒泡排序的时间复杂度是O(n^2),所以优化的方法有很多,比如设置一标志性变量pos,用来记录每趟排序中最后一次进行交换的位置,也就是排序的尾边界。在进行排序时,只需进行到这个位置即可。
代码示例:
void OptBubbleSort(int arr[], int n) {
int i = n - 1;
while(i > 0) {
int pos = 0;
for(int j = 0; j < i; j++) {
if(arr[j] > arr[j+1]) {
pos = j;
swap(arr[j], arr[j+1]);
}
}
i = pos;
}
}
当序列达到有序状态时,就不再进行交换操作,这样可以减少排序次数和比较次数,提高效率。希望我能帮到您,有什么问题可以再问我。
相关问题
用冒泡排序和选择排序算法对数字序列排序(写出排序全过程)
假设待排序的数字序列为:[5, 3, 8, 6, 4, 2]
首先是冒泡排序:
第一轮排序:
比较 5 和 3,发现 5 大于 3,交换它们的位置,序列变为:[3, 5, 8, 6, 4, 2]
比较 5 和 8,发现它们已经有序,不需要交换位置,序列不变:[3, 5, 8, 6, 4, 2]
比较 8 和 6,发现 8 大于 6,交换它们的位置,序列变为:[3, 5, 6, 8, 4, 2]
比较 8 和 4,发现 8 大于 4,交换它们的位置,序列变为:[3, 5, 6, 4, 8, 2]
比较 8 和 2,发现 8 大于 2,交换它们的位置,序列变为:[3, 5, 6, 4, 2, 8]
第一轮排序结束,最大的元素 8 已经被冒泡到最后面了。
第二轮排序:
比较 3 和 5,发现它们已经有序,不需要交换位置,序列不变:[3, 5, 6, 4, 2, 8]
比较 5 和 6,发现它们已经有序,不需要交换位置,序列不变:[3, 5, 6, 4, 2, 8]
比较 6 和 4,发现 6 大于 4,交换它们的位置,序列变为:[3, 5, 4, 6, 2, 8]
比较 6 和 2,发现 6 大于 2,交换它们的位置,序列变为:[3, 5, 4, 2, 6, 8]
第二轮排序结束,第二大的元素 6 已经被冒泡到倒数第二个位置了。
第三轮排序:
比较 3 和 5,发现它们已经有序,不需要交换位置,序列不变:[3, 5, 4, 2, 6, 8]
比较 5 和 4,发现 5 大于 4,交换它们的位置,序列变为:[3, 4, 5, 2, 6, 8]
比较 5 和 2,发现 5 大于 2,交换它们的位置,序列变为:[3, 4, 2, 5, 6, 8]
第三轮排序结束,第三大的元素 5 已经被冒泡到倒数第三个位置了。
第四轮排序:
比较 3 和 4,发现它们已经有序,不需要交换位置,序列不变:[3, 4, 2, 5, 6, 8]
比较 4 和 2,发现 4 大于 2,交换它们的位置,序列变为:[3, 2, 4, 5, 6, 8]
第四轮排序结束,第四大的元素 4 已经被冒泡到倒数第四个位置了。
第五轮排序:
比较 3 和 2,发现 3 大于 2,交换它们的位置,序列变为:[2, 3, 4, 5, 6, 8]
第五轮排序结束,第五大的元素 3 已经被冒泡到倒数第五个位置了。
第六轮排序:
比较 2 和 3,发现它们已经有序,不需要交换位置,序列不变:[2, 3, 4, 5, 6, 8]
第六轮排序结束,第六大的元素 2 已经被冒泡到倒数第六个位置了。
最终得到有序序列:[2, 3, 4, 5, 6, 8]
接下来是选择排序:
第一轮排序:
找到序列中最小的元素 2,将它与第一个元素 5 交换位置,序列变为:[2, 3, 8, 6, 4, 5]
第二轮排序:
在剩下的元素中找到最小的元素 3,将它与第二个元素 3 交换位置,序列不变:[2, 3, 8, 6, 4, 5]
第三轮排序:
在剩下的元素中找到最小的元素 4,将它与第三个元素 8 交换位置,序列变为:[2, 3, 4, 6, 8, 5]
第四轮排序:
在剩下的元素中找到最小的元素 5,将它与第四个元素 6 交换位置,序列变为:[2, 3, 4, 5, 8, 6]
第五轮排序:
在剩下的元素中找到最小的元素 6,将它与第五个元素 8 交换位置,序列变为:[2, 3, 4, 5, 6, 8]
第六轮排序:
剩下一个元素,序列已经有序,不需要排序。
最终得到有序序列:[2, 3, 4, 5, 6, 8]
2. 冒泡排序算法、折半插入排序算法简单选择排序算法基本思想
1. 冒泡排序算法的基本思想是:比较相邻的两个元素,如果前一个元素比后一个元素大,就交换这两个元素的位置,一轮下来,最大的元素就会被交换到序列的末尾。然后再从头开始进行相邻元素的比较和交换,直到整个序列有序为止。时间复杂度为O(n^2)。
2. 折半插入排序算法的基本思想是:将待排序的序列分为有序和无序两部分,每次从无序部分取出第一个元素,在有序部分中采用折半查找的方式找到插入位置,将该元素插入到有序部分中合适的位置,直到整个序列有序为止。时间复杂度为O(n^2)。
3. 简单选择排序算法的基本思想是:在待排序的序列中选择最小的元素,将其放置在序列的起始位置,然后再从剩余的元素中选择最小的元素,将其放置在已排序序列的末尾。重复这个过程,直到整个序列有序为止。时间复杂度为O(n^2)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)