赞
踩
1、(1)冒泡排序:沉石排序,每一趟循环两两比较,大的向后挪动,最终最大值放在最后,假设有n个书数据,则需要跑n-1趟。
代码:
- void BubbleSort(int* arr, int len)
- {
- for (int i = 0; i < len - 1l; i++)
- {
- for (int j = 0; j + 1 < len-i; j++)//比较的下一位j+1<每一趟的最后一位数(len-i)
- {
- if (arr[j] > arr[j + 1])
- {
- int tmp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = tmp;
- }
- }
- }
- }
-
- void Show(int arr[], int len)
- {
- for (int i = 0; i < len; i++)
- {
- printf("%d ", arr[i]);
- }
- printf("\n");
- }
-
-
- int main()
- {
- int arr[] = { 12,2,39,88,4,6,25,232,62,221 };
- BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
- Show(arr, sizeof(arr) / sizeof(arr[0]));
- return 0;
- }
结果:
对冒泡排序的优化:
上述冒泡排序,但在第四趟处理完成时,就已经完全有序,理应直接退出,第五趟完全可以优化。
问题:怎么判断数据已经完全有序?
答:从前到后遍历一遍,没有交换操作,此时就可判定数据完全有序
(2)优化后代码:
- //对冒泡排序的优化
- void BubbleSort2(int* arr, int len)
- {
- int count = 0;//记录需要跑几趟
- int flag = 0;//首先令标志等于0
- //从头到尾遍历,看是否有交换操作,没有则完全有序
- for (int i = 0; i < len - 1l; i++)//需要多少趟
- {
- flag = 0;//每一趟都需要重置为0
- for (int j = 0; j + 1 < len-i; j++)//比较的下一位j+1<每一趟的最后一位数(len-i)
- {
- if (arr[j] > arr[j + 1])
- {
- int tmp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = tmp;
-
- flag = 1;//存在交换,标志修改
- }
- }
- count++;
- if (flag == 0)//标志不变,说明已完全有序,跳出循环
- {
- break;
- }
- }
- }
(3)冒泡排序的时间复杂度:O(n^2),
空间复杂度:O(1) ,
稳定性:稳定
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。