初级版冒泡排序
冒泡排序算法为一种比较排序算法(还有快速排序),较小的数字如同气泡般慢慢浮到上面,所以称为冒泡排序。为就地排序,稳定。
算法思想:两两比较相邻记录的关键字,如果反序则交换,知道没有反序的记录为止。
C++实现
/**********冒泡排序1--升序************/ void swap(ElemType a[],int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } void BubbleSort1(ElemType a[],int n) { int i,j; for (i = 0;i < n;i++) for(j = n-1;j > i;j--) { if(a[j-1] > a[j]) swap(a,j-1,j); } } /**********冒泡排序3--降序************/ void BubbleSort3(ElemType a[],int n) { int i,j; for (i = 0;i < n;i++) for(j = 0;j <n-i;j++) { if(a[j] < a[j+1]) swap(a,j,j+1); } }
优化版冒泡排序1–添加标记位
算法思想:设置一个标志,如果这一趟发生了交换,则为true,否则为false。如果有一趟没有发生交换,说明排序已经完成。
/**********冒泡排序2--升序************/ void BubbleSort2(ElemType a[],int n) { int i,j; bool flag = true; while(flag) { flag = false; for (i = 0;i < n;i++) for(j = n-1;j > i;j--) { if(a[j-1] > a[j]) { swap(a,j-1,j); flag = true; } } } } /**********冒泡排序4--降序************/ void BubbleSort4(ElemType a[],int n) { int i,j; bool flag = true; while(flag) { flag = false; for (i = 0;i < n;i++) for(j = 0;j < n-i;j++) { if(a[j] < a[j+1]) { swap(a,j,j+1); flag = true; } } } }
优化版冒泡排序2–添加标记位并记录位置
算法思想:记录未排序最后位置的冒泡排序。在优化方法1的基础上再次进行改进,每次循环记录最后一次发生交换的元素的位置,这说明这之后的元素已经有序,下一次循环不用比较这些元素。
/**********冒泡排序5优化法二--升序************/ void BubbleSort5(ElemType a[],int n) { int i,j; int flag; flag = n; while(flag > 0) { for (j = i = 0;j < flag && j+1 < n;j++) { if(a[j] > a[j+1]) { swap(a,j,j+1); i = j; } } flag = i; } }
优化版冒泡排序3–双向冒泡
算法思想:在优化方法2的基础上继续改进,每次循环不仅从前向后扫描记录最后一次发生交换的元素的位置up,而且从后向前扫描记录再次扫描记录最前面发生交换的元素的位置low,这样两侧的元素已经有序,当low>=up的时候证明整个数组有序。
/**********冒泡排序6优化法三--升序************/ void BubbleSort6(ElemType a[],int n) { int low,high,i,index; low = index = 0; high = n; while(high > low) { for(i = low;i < high;i++) if(a[i] >a[i+1]) { swap(a,j,j+1); index = i; } high = index; for(i = high;i > low;i--) if(a[i]<a[i-1]) { swap(a,i,i-1); index = i; } low = index; } }
优化的冒泡排序算法的时间复杂度:
最好的情况下,时间复杂度为O(n)。
最坏的情况下,时间复杂度为O(n^2)。
python实现
#----------------# #--Bubble sort1--# #----------------# def swap(arr,i,j): tmp = arr[i] arr[i] = arr[j] arr[j] = tmp def bubble_sort1(arr): arrlen = len(arr) for i in range(arrlen): for j in range(arrlen-1): if arr[j] > arr[j+1]: swap(arr,j,j+1) #----------------# #--Bubble sort2--# #----------------# def bubble_sort2(arr): flag = True arrlen = len(arr) while flag: flag = False for i in range(arrlen): t = arrlen - i -1 if t >=0 and t-1 >=0 and arr[t]<arr[t-1]: swap(arr,t,t-1) flag = True