冒泡排序跟选择排序是八大排序里最简单的两个，有时候简单意味着高效，但这种想法在这两种排序上行不通，恰恰这两种排序的时间复杂度都是O(n^2)级别的，相对于快排的平均时间复杂度O(nlog2n)来说，确实慢了不少。因此，在还不会使用别的排序方法之前，我们可以先对这两种排序方法进行优化，尽量减少运行时间。
一、冒泡排序
冒泡排序有两种比较好的优化方法：
1.在二级循环外进行优化：
这种方法即在两个for循环之间加入一个标志变量flag，先贴代码：（这是升序排序）
void BubbleSort_Optimization_1(int arr[],int size) { for (int i = 0;i < size-1;i++) { int flag = 1; for (int j = 0;j < size - 1 - i;j++) { int temp; if (arr[j] > arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; flag = 0; } } if (flag) break; } return;}
代码第三行处定义了一个标志变量flag，赋初值为1，进入二级循环，只要在二级循环里不会进入if（）语句，那么flag的值就会为1，如果执行完二级循环后flag的值仍为1就意味着整个数列从下标0开始到size-1-i为止都是有序的，那么接下来的外层循环就没必要再进行了，直接结束排序过程。
2.第二种优化即是对内层循环进行的优化：
void BubbleSort_Optimization_2(int arr[], int size) { int k = size - 1; int temp_k; //temp_k用来暂时存k应赋予的值 for (int i = 0;i < size;i++) { int flag = 1; for (int j = 0;j < k;j++) { //这里的循环的上界设置为k int temp; if (arr[j] > arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; temp_k = j; //这里将最后一次交换值时的下标j记录下来，等待赋予k flag = 0; } } k = temp_k; if (flag) //这里依旧是只要数列后边有序就结束排序 break; } return;}
其实上面的代码时两种优化的结合体，第二种优化的关键点在内层循环的上界设置为k,而k的值来自最后一次交换变量所对应的下标j，这样就可以更进一步把排序的范围缩小，减少时间。
二、选择排序的优化
本博文只列出一种选择排序的优化方法：
一般的选择排序每遍历一次数组，只找出最大或最小的那个值，那如果我们在一次遍历之后就把最大和最小值都找出来呢，时间在理论上会比原来少花一半左右。具体代码如下：
void SelectionSort_Optimization(int arr[], int size) { int left=0, right=size-1; //left跟right用于循环上下界的左右逼近 while(left<right){ int temp; int max=right, min=left; for (int i = left;i <= right;i++) { if (arr[i] > arr[max]) { max = i; } if (arr[i] < arr[min]) { min = i; } }
temp = arr[max]; // arr[max] = arr[right]; // 这块代码将遍历后的最大值交换到右边 arr[right] = temp; //
if (min == right) { // 这段代码存在的意义在于可能存在min==right min = max; // 的情况，在上面的arr[right]与arr[max]的 } // 值交换后，arr[left]就应该与arr[max]交换
temp = arr[min]; // arr[min] = arr[left]; // 交换最小值到左边 arr[left] = temp; //
left++; right--; } return;}
上面的优化相比于原来的选择排序来说在实现上复杂了一点，但在效率上却好了不少。
本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2017-09/147040.htm
以上就上有关冒泡排序与选择排序的优化的相关介绍，要了解更多冒泡排序,选择排序,冒泡排序与选择排序的优化,编程,Linux编程,Linux Shell,Android,Android教程,JAVA,C语言,Python,HTML5内容请登录学步园。