面试系列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;
}