VC冒泡排序、递归型冒泡排序和递归快速排序源代码

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

关于冒泡排序的源码如下：

迭代型冒泡排序
#include 

#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0

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(n2)，此时快排的效率降到最低，退化为冒泡，所以快排对于枢纽元素的选择上很关键，如果能选择出每趟平均划分数组的枢纽元素，那么快排的效率最高，如何选择枢纽元素将成为衡量快排的关键，我推荐使用三者取中法来选择，每趟快排前，先将数组开始位置，中间位置，以及结尾位置的三个元素进行比较，选择其中的中间大的数做为枢纽元素，这样可以降低退化成冒泡的风险，也可以使用任取一个数做为枢纽元素，这样也可以降低风险。

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

递归型冒泡排序
#include 

#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 0

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;
}

递归快速排序
#include 

#define length(array) sizeof(array)/sizeof(array[0])
#define true 1
#define false 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)
        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)，所以快排是对冒泡的一个巨大的改进。