冒泡、快速排序 比较

对于冒泡排序，大家肯定都熟知，每一轮的冒泡都将最大的数排到最前面，每一轮的时间复杂度是O(n)，如果要排序的数组大小为n，要经过n轮才能将数组中所有元素排序，所以总共的时间复杂度为O(n²)。

迭代型冒泡排序

 

void BubbleSort(int *a, int len) //待排数组a以及它的长度len

{

    int ordered = false;

    int temp, i;

 

    while(len && !ordered)

    {

        ordered = true; //也许一趟排序过程中没有发生交换，说明数组已有序

        for(i = 1; i < len; i++) //此时i从1开始比从0开始更好

        {

            if(a[i-1] > a[i])

            {

                ordered = false;

                temp = a[i];

                a[i] = a[i-1];

                a[i-1] = temp;

            }

        }

        len--;

    }

}

 

int main()

{

    int a[5] = {5,1,2,3,4};

    int i = 0;

    int len = length(a);

    BubbleSort(a,len);

    for(i = 0; i < len; i++)

    {

        printf("%d ",a[i]);

    }

    return 0;

 

}

 

----------------------------------------------------------------

 

对 于快速排序，选出一个枢纽元素，然后将这个枢纽元素和数组所有元素进行比较，把彼枢纽元素大的元素放在枢纽元素右边，把比枢纽元素小的放在枢纽元素左边， 而对于一趟快速排序要比较n次，每一趟快排的时间复杂度是O(n)，接下来你要对快排划分出来的两个子数组进行递归快排，如果每一趟快排很平均的将数组划分为两个子数组，那么递归快排的深度就是O(lgn),所以总的时间复杂度就是O(nlgn)。但是快排可以退化成冒泡，如果一旦每一趟快排，不幸的选择出最大或最小元素作为枢纽元素，那么递归深度将变成n，则时间复杂度变成了O(n²)，此时快排的效率降到最低，退化为冒泡，所以快排对于枢纽元素的选择上很关键，如果能选择出每趟平均划分数组的枢纽元素，那么快排的效率最高，如何选择枢纽元素将成为衡量快排的关键，我推荐使用三者取中法来选择，每趟快排前，先将数组开始位置，中间位置，以及结尾位置的三个元素进行比较，选择其中的中间大的数做为枢纽元素，这样可以降低退化成冒泡的风险，也可以使用任取一个数做为枢纽元素，这样也可以降低风险。

 

----------------------------------------------------------------

递归型的冒泡排序和递归型的快速排序，你会发现两者的区别，以及为什么快排会比冒泡好的原因，以及如何将程序从冒泡写成快排。

 

递归型冒泡排序

int Sort(int *a, int len)

{

    int ordered = true; //也许一趟排序过程中没有发生交换，说明数组已有序

    int temp, i;

    for(i = 1; i < len; i++)  //由此可以看出Sort()的时间复杂度是O(n)，跟待排数组的长度有关。

    {

        if(a[i-1] > a[i])

        {

            ordered = false;

            temp = a[i];

            a[i] = a[i-1];

            a[i-1] = temp;

        }

    }

    return ordered;

}

 

void BubbleSort(int *a, int len) //冒泡排序的递归算法

{   

    if(len == 1) //如果只有一个元素，它就是最大的元素，无须在冒泡

        return;

    else

    {

        int ordered = Sort(a,len); //选出最大的元素，将所有比最大元素小的元素放在最大元素的左边，而快排是将使用一个枢纽元素，将比枢纽元素大的放在枢纽右边，小的放在左边

        if(ordered)  //如果一趟冒泡，没有交换元素，说明已有序

            return;

        BubbleSort(a,len-1); //递归冒泡出最大元素后面的所有元素，如果快排将作为快排的左递归

        //如果快排会有右递归

    }

}

 

int main()

{

    int a[10] = {10,1,5,2,4,3,6,7,9,8};

    int i = 0;

    int len = length(a);

    BubbleSort(a,len);

    for(i = 0; i < len; i++)

    {

        printf("%d ",a[i]);

    }

    return 0;

 

}

 

----------------------------------------------------------------

递归快速排序

 

int Sort(int *a, int low, int high)

{

    int pivot = a[low]; //这里每次的枢纽元素都取了待排数组的第一个元素，记住是a[low],而不是a[0]

    if(low < high)  //时间复杂度是O(n),n是数组长度

    {

        while(a[high] >= pivot && low < high)

            high --;

        a[low] = a[high];

 

        while(a[low] <= pivot && low <high)

            low ++;

        a[high] = a[low];

    }

    a[low] = pivot;

    return low;

}

 

void QuickSort(int *a, int low, int high)

{

    if(low >= high)

        return ;

    else

    {

        int mid = Sort(a,low,high); //划分子递归数组

        QuickSort(a,low,mid-1); //左递归

        QuickSort(a,mid+1,high); //右递归，一旦右递归mid+1=high，将退化成冒泡，递归深度将变成n，n为数组长度

    }

}

int main()

{

    int a[5] = {3,1,5,2,4};

    int i = 0;

    int len = length(a);

    QuickSort(a,0,len-1);

    for(i = 0; i < len; i++)

    {

        printf("%d ",a[i]);

    }

    return 0;

}

 

递归型的冒泡就是一个只有右子树的递归树，递归深度为O(n)，而好的快速排序，将产生一个平衡的二叉树，递归深度为O(lgn)，所以快排是对冒泡的一个巨大的改进。