冒泡是一个经典算法。
本段代码增加了一些优化：
增加 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 <stdio.h>
#include <stdlib.h>
/*
* 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;
}
下一篇：面试系列2约瑟夫环问题-Josephus-
原题：
用户输入m,n值，从1至n开始顺序循环数数，每数到m输出该数值，直至全部输出。写出c程序。（约瑟夫环问题 josephus）
提示：
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆...[
查看详情]
