面试系列3--冒泡算法（优化）

冒泡是一个经典算法。

本段代码增加了一些优化：

增加 b_exchange ，若本轮冒泡没有交换数据，则表示排序成功，退出
增加 n_exchange, n_head ，记录最近的交换位置，下轮冒泡只要冒到该位置即可

 /********************************************************************
    created:    2006/06/15
    filename:   C:\Documents and Settings\Administrator\桌面\tmmp\poposort.c
    file path:  C:\Documents and Settings\Administrator\桌面\tmmp
    file base:  poposort
    file ext:   c
    author:     A.TNG
    version:    0.0.1
   
    purpose:    冒泡排序的实现(优化)
                增加 b_exchange ，若本轮冒泡没有交换数据，则表示排序成功，退出
                增加 n_exchange, n_head ，记录最近的交换位置，下轮冒泡只要冒到该位置即可
*********************************************************************/
#include
#include

/*
 *  name: poposort
 *  params:
 *    polist            [in/out]        待排序的 int 数组
 *    n                 [in]            int 数组的长度
 *  return:
 *    1-成功 0-失败
 *  notes:
 *    对 polist 进行冒泡排序
 * 
 *  author: A.TNG 2006/06/15 9:00
 */
int poposort(int *polist, int n)
{
    int i, j;
    int n_exchange;

    if (NULL == polist)
        return 0;

    n_exchange = 0;
    for (i = 0; i < n - 1; i++)
    {
        /* 最外层循环，冒泡排序需要比较 n-1 轮 */
        int b_exchange;
        int n_head;

        b_exchange = 0;
        n_head = n_exchange;
        for (j = n - 1; j >= n_head + 1; j--)
        {
            /* 第 i 轮比较，把最轻的泡冒置第 i 个位置 */
            if (polist[j] < polist[j - 1])
            {
                int n_tmp_num;

                n_tmp_num = polist[j];
                polist[j] = polist[j - 1];
                polist[j - 1] = n_tmp_num;

                b_exchange = 1;
                n_exchange = j;
            } /* end-if */
        } /* end-for */

        /* 若第 i 轮冒泡结束，并没有交换数据，则表示已经排序完成 */
        if (0 == b_exchange)
            return 1;
    } /* end-for */
    return 1;
}

/*
 *  name: main
 *  params:
 *    none
 *  return:
 *    none
 *  notes:
 *    none
 * 
 *  author: A.TNG 2006/06/15 9:05
 */
int main()
{
    // int polist[10] = {45,12,43,11,32,34,91,58,20,82};
    int polist[10]  =
    {
        0, 1, 2, 3, 4, 5, 6, 7, 9, 8
    };

    (void) poposort(polist, 10);

    system("PAUSE");
    return 0;
}