冒牌排序及其优化(鸡尾酒排序)

冒牌排序及其优化(鸡尾酒排序)"/>

冒牌排序及其优化(鸡尾酒排序)

关于冒牌排序及其几种优化:

初学c语言我们就知道冒泡排序这种东西,虽然冒泡排序的运行效率并不高,但是并不妨碍我们写这种排序的热情,因为好写鸭!
首先是我们的主程序部分,用time函数获取随机数并赋值.不同的童鞋可以去看看rand()与time()的介绍.
 

#include<stdio.h>
#include<time.h>
#include<stdlib.h> 
#define max 100000 //10000int main () {int arr[max];srand((unsigned)time(NULL));for(int i = 0;i < max;i++) {int temp = rand() % 100000;arr[i] = temp;} return 0;
} 

我们本次研究的主要是10000与30000数目的数组排序的时间比较.

第一种是最经典的冒泡排序:

for(int i = 0;i < max - 1 ;i++) { //N = 30000 s=4 N = 10000 s = 0.69for(int j = 0;j < max - 1;j++) {if(arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}

多次试验,在N=10000时,平均排序时间为0.98s,在N=30000时,排序时间为40s.

第二种是简单对排序次数进行的优化
利用flag进行标记,在某次不需排序的循环中退出

    for(int i = 0;i < max - 1;i++) { //N = 30000 s = 4 N = 10000 s = 0.69int flag = 1;for(int j = 0;j < max - 1;j++) {if(arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = 0;}}if(flag) {break;}}

多次试验,这种优化效果并不明显,在N=10000时甚至效果不如普通冒泡排序,不建议使用.

第三种,鸡尾酒排序!!(敲黑板,划重点)
第三种鸡尾酒排序又称为来回排序,保持冒泡排序的特性不变,在每次循环进行两次移位:

 int left = 0;int right = max - 1;while(left < right) { //N = 10000 s = 0.26 N = 30000 s = 2.2for(int j = left;j < right;j++) {if(arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}right--;for(int j = right;j > left;j--) {if(arr[j] < arr[j - 1]) {int temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}left++;}

多次试验,在N=30000时,优化效果显著提升,在N=10000时也有效果.