排序算法（1）--交换排序(冒泡、快速）

开篇

   这是经典排序算法系列的讲解，从这里能够学到什么：
         1、排序算法的分类
         2、各种排序算法的实现原理及相应代码
         3、各种排序算法的性能分析及应用场景
   这里的代码将会在真实环境中，正确运行，请大家放心。

一、交换排序

       交换排序包括冒泡排序、快速排序，顾名思义此类排序方法的核心是“交换”。

 1.1 冒泡排序（bubble sort）

        原理：从字面理解，冒泡排序是一种类似于“冒泡”的自然现象，轻者“浮”到顶端；在程序中的具体实现是：从第一个元素开始与第二个元素比较，将较小的元素放到后面，在比较第二个元素与第三个元素，较小者放到后面，......依次类推，最后最小的元素放到数组的最后，完成一次“冒泡”；再根据上述比较将第二小的元素放到倒数第二的位置上，最终完成排序。
        代码实现：

/************************************************************************/
/* 交换两个变量的值 */
/************************************************************************/
void myswap(int *a, int *b)
{
    int c = *a;
    *a = *b;
    *b = c;
}

 以后对于myswap的调用同此处

/************************************************************************/
/*
 * 冒泡排序
 * 输入：arr： 待排序数组
 * num： 数组个数
*/
/************************************************************************/
void bubblesort(int *arr, int num)
{
    int i = 0, j = 0;    // i， j变量用于计数
    int changeflag = 0;  // 正序标志

    for(i = 0; i < num; i++)
    {
        changeflag = 0;

        for(j = 0; j < num - i - 1; j++)
        {
            if(arr[j] < arr[j + 1])
            {
                changeflag = 1;
                myswap(&arr[j], &arr[j + 1]);
            }
        }

        if(!changeflag) break; // 正序退出
    }
}

        性能分析：冒泡排序的时间复杂度为O(n^2),当数组时“正序”时，不需要进行值的交换，却需要进行比较，此时的时间复杂度为O(n)，当是“逆序”时比较次数没变，每次比较需要交换值，所以时间复杂度为最大时间O(n^2)。

  1.2 快速排序（quick sort）

        原理：快速排序是对冒泡排序的一种改进，是由C. A. R. Hoare提出的一种排序算法，基本思想是：选择一个元素作为因子，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比因子小，另外一部分的所有数据都比因子大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
        代码实现：

// 从小到大分隔
int partition(int a[], int s, int e)
{
    int key = a[s]; // 拿数组的第一个元素作为因子
    int key_location = s + 1; // 比因子大的数的第一个位置
    int j = 0;

    for(j = s + 1; j <= e; j++)
    {
        if(a[j] < key)
        {
            myswap(&a[j], &a[key_location]);
            key_location++;
        }
    }

    myswap(&a[s], &a[key_location - 1]);

    return key_location - 1;
}
// 另外一种分隔方法，从两端交替向中间扫描
int partition2(int a[], int s, int e)
{
    int key = a[s];
    int i = s, j = e;

    while(i < j)
    {
        while((i < j) && (a[j] >= key))
            j--;
        a[i] = a[j];

        while((i < j) && (a[i] <= key))
            i++;
        a[j] = a[i];
    }

    a[i] = key;

    return i;
}
/************************************************************************/
/* 快速排序 */
/************************************************************************/
void quicksort(int *a, int start, int end)
{
    int keyloc = 0;

    if(start <= end)
    {
        keyloc = partition2(a, start, end);
        quicksort(a, keyloc + 1, end);
        quicksort(a, 0, keyloc - 1);
    }
}

        性能分析：快速排序的时间复杂度与数据的对称性有关。最好的情况是我们每次都分割成两个几近相等的片段，也就是每次的递归调用都处理一半的数据；所以在调用结束时需要进行log N次的递归调用，这个意思就是调用树的深度是O(log n)。但是在同一阶层的两个程序调用中，不会处理到原来数列的相同部份；因此，程序调用的每一阶层总共全部仅需要O(n)的时间（每个调用有某些共同的额外耗费，但是因为在每一阶层仅仅只有O(n)个调用，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。最坏情况下（每次划分都不对称，如输入的序列有序或者逆序时）时间复杂度为o(n^2)，也就是冒泡排序的时间，所以在待排序序列有序或逆序时不宜选用快速排序。此外，快速排序是不稳定的。

二、参考书籍

      《数据结构》  严蔚敏版     《算法导论》