【C语言】十大排序之冒泡排序（三种优化） |
您所在的位置：网站首页 › 冒泡法排序C语言 › 【C语言】十大排序之冒泡排序（三种优化） |
【C语言】十大排序之冒泡排序（三种优化）
|
目录 冒泡排序概念 基础代码演示 第一种优化方式，加入flag判断最大数有多少已经排好 第二种优化方式，双向冒泡 第三种优化方式，设立flag加双向冒泡 冒泡排序概念(Bubble Sort)是一种简单排序，在最坏情况下时间复杂度为O(n^{2}）。原理为依次判断两个相邻的数，如果错误就将他们换位，并依次走访数列，直到每一个数都在正确的位置上。 动图演示：（图片来自网络，侵删） 在这里我们可以加入flag判断是否完成 ，如果已经完全排好序，就不用进行之后的步骤了： void bubble(int num[], int size) { int i, j, temp, flag; for(i = 0; i < size - 1; i++) { flag = 0; for(j = 0; j < size - 1 - i; j++) { if(num[j] > num[j+1]) { temp = num[j]; num [j] = num[j+1]; num[j+1] = temp; flag = 1; } } if(!flag)如果flag没有变化，则说明这一次没有进行排序，即所有数已经排好，执行退出 { break; } } } 第一种优化方式，加入flag判断最大数有多少已经排好前面加入flag的思想，是如果在过程中就排好所有的序就退出，但是在实际中，这种情况其实出现的很少，那么我们是否可以改变一下，记录每次已经排好的数的下标，下一次排序就只需要排序到记录的下标即可？ 实现代码： void bubble(int num[], int size) { int i, j, k, temp, flag; flag = size - 1; while(flag > 0) { k = flag;//初始化为size-1，以后每一次取出flag flag = 0;//每一次flag重置为0 for(i = 0; i < k; i++) { if(num[i] > num[i+1]) { temp = num[i]; num[i] = num[i+1]; num[i+1] = temp; flag = i;//i最终的值为最后被排序的下标 } } } } 第二种优化方式，双向冒泡第二种优化方式为同时进行上浮和下沉，思想和普通的冒泡没有本质区别。 实现代码： void bubble(int num[], int size) { int i, j, k, temp, flag; for(i = 0; i < size / 2; i++)//因为双向同时进行，所以只需要size/2次大循环 { flag = 0; for(j = 0; j < size - i - 1; j++)//从前往后排 { if(num[j] > num[j+1]) { temp = num[j]; num[j] = num[j+1]; num[j+1] = temp; flag = 1; } } for(k = size - 1 - i; k > 0; k--)//从后往前排 { if(num[k] < num[k-1]) { temp = num[k]; num[k] = num[k-1]; num[k-1] = temp; flag = 1; } } if(!flag) { break; } } } 第三种优化方式，设立flag加双向冒泡通过思考前面的两种优化，我们是否可以将记录下标和双向冒泡结合？ 如果从前往后排列到某一个数就没有再发生变化，那么该下标之后的数都已经排好序，那么从后往前就只用从改下标往前排序即可。同理，从后往前排列到某一个数就没有再发生变化，那么该下标之前的数都已经排好序，那么只需从该下标往后排序。 实现代码： void bubble(int num[], int size) { int i, j, k, up, down, temp, flag; up = size - 1; down = 0; for(i = size - 1; i > 0; i--)//从前往后排 { for(j = down; j < up; j++) { if(num[j] > num[j+1]) { temp = num[j]; num[j] = num[j+1]; num[j+1] = temp; flag = j;//取出从前往后的下标，在下标之后的数都已经排好序 } } if(flag == -1) { break; } up = flag;//取出flag的值 flag = -1;//重置flag for(k = up; k > down; k--) { if(num[k] < num[k-1]) { temp = num[k]; num[k] = num[k-1]; num[k-1] = temp; flag = k;//取出从后往前的下标，在下标之前的数都已经排好序 } } if(flag == -1) { break; } down = flag;//取出flag的值 flag = -1;//重置flag } }总结 冒泡排序可以通过加flag取下标来减少判断的次数，以及双向排序减少大循环的次数，这两种优化可以结合起来。 纯手打，水平有限，如有疏漏，欢迎指教讨论。 |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |