改进的排序算法

之前写到几个排序的算法,例如:

//冒泡排序
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).

 

相关:观 数据与结构有感

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。