改进的排序算法
之前写到几个排序的算法,例如:
//冒泡排序 void bubbleSort(unsigned char *list, int length) { int i,j,temp; for(i = 0; i < length; i++) { for(j = 0; j < length - i - 1; j++) { if(list[j+1] < list[j]) { temp = list[j + 1]; list[j + 1] = list[j]; list[j] = temp; } } } }
原操作是数据的交换,算法时间复习度是O(n^2).
但假如我们需要排序的数据如: 一开始已经是排序好的如(1 2 3 5 6 9)或只需交换几次便能排序好的如(2 1 3 5 6 9),该算法后面的循环均在做无用功。
在这个时候我们只需要加入一个标志即可避免该情况。
//冒泡排序 void bubbleSort(unsigned char *list, int length) { int i,j,temp; int flag; for(i = 0, flag = 1; i < length && flag; i++) { flag = 0; for(j = 0; j < length - i - 1; j++) { if(list[j+1] < list[j]) { temp = list[j + 1]; list[j + 1] = list[j]; list[j] = temp; flag = 1; } } } }
当在序列本身是正确的情况下,最佳情况下:时间复习度是O(n).
相关:观 数据与结构有感
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。