冒泡排序

伊海 · 发表于 2014-8-5 15:24:49

1.1 底层冒泡排序的头文件

为了增强代码的可移植性，健壮性。我们将冒泡排序的算法封装在库中，我们只需要调用库函数即可。冒泡排序头文件程序如程序清单1. 1所示。
程序清单1. 1 冒泡排序头文件

/*
* 声明比较函数，升序还是降序
*/
typedef int (*COMPAREFUN)(const void *pvData1, const void *pvData2);
/*******************************************************************************
**函数名称： bubbleSort
**函数功能：冒泡排序
**入口参数： *pvData：需要进行排序的数组
stAmount：数组中包含的元素个数
stSize：元素内存大小
CompareFun：需要排序的数据类型、升序还是降序
**出口参数：
*******************************************************************************/

复制代码

extern void bubbleSort (void *pvData, size_t stAmount, size_t stSize , COMPAREFUN CompareFun);
为了各种数据的兼容性，所有不确定情况的数据类型都使用void *。

1.2 底层数据交换函数实现
通过函数指针类型数据，向swap函数传入需要交换的两个数据的地址和数组元素内存大小，实现数据的交换。swap函数代码如程序清单1. 2所示。
程序清单1. 2 swap函数

/*******************************************************************************
**函数名称： __swap
**函数功能：数据交换
**入口参数： *pvData1：需要交换的数据一
*pvData2：需要交换的数据二
stDataSize：元素内存大小
**出口参数：
*******************************************************************************/
static void __swap (void *pvData1, void *pvData2, size_t stDataSize)
{
unsigned int *p1=(unsigned int)pvData1;
unsigned int *p2=(unsigned int)pvData2;
unsigned int uiTemp;
while ( stDataSize >= sizeof(unsigned int) ) //一次交换sizeof(unsigned int)个字节
{
(*p1) ^=(*p2);
(*p2) ^=(*p1);
(*p1++)^=(*p2++);
stDataSize -= sizeof(unsigned int);
}
if (stDataSize>0)
{
/*
* void *memmove( void *to, const void *from, size_t count );
* 函数从from中复制count 个字符到to中，并返回to指针。
*/
memmove( &uiTemp,p1,stDataSize);
memmove( p1,p2,stDataSize);
memmove( p2,&uiTemp,stDataSize);
}
}

复制代码

这里传进去的是三个参数分别是：pvData1，为需要交换的两个数据中的第一个数据的地址；pvData2，为需要交换的两个数据中的第二个数据的地址；stDataSize：数组中元素内存的大小。
传进去之后，先将两个数据的地址强制转化为(int*)型地址。数据的交换分成两个部分：如果元素内存大小大于一个sizeof(unsigned int)个字节大小，则一次性交换4位；当stDataSize大于0且小于一个sizeof(unsigned int)个字节大小时，再通过memmove交换剩下的部分。

1.3 冒泡排序算法实现
冒泡排序的基本思想是通过相邻元素之间的比较和交换使得排序码较小的元素上移或下移。冒泡排序代码如程序清单1. 3所示。
程序清单1. 3 冒泡排序

/*******************************************************************************
**函数名称： bubbleSort
**函数功能：冒泡排序
**入口参数： *pvData：需要进行排序的数组
stAmount：数组中包含的元素个数
stSize：元素内存大小
CompareFun：需要排序的数据类型、升序还是降序
**出口参数：
*******************************************************************************/
void bubbleSort (void *pvData, size_t stAmount, size_t stSize , COMPAREFUN CompareFun)
{
int i, j;
int iNoSwapFlg = 0;
void *pvThis = NULL;
void *pvNext = NULL;
/*
* 冒泡排序
*/
i = stAmount - 1;
do {
iNoSwapFlg = 0;
pvThis = pvData;
pvNext = (char *)pvData + stSize;
j = i;
do {
if (CompareFun(pvThis, pvNext) > 0) {
__swap(pvThis, pvNext, stSize);
iNoSwapFlg = 1;
}
pvThis = pvNext;
pvNext = (char *)pvNext + stSize;
} while (--j != 0);
if (iNoSwapFlg == 0) {
break;
}
} while ( --i != 0);
}

复制代码

bubbleSort函数传入的有四个参数：pvData：需要进行排序的数组的首元素地址，但是这个地址也就是需要进行排序的数组的地址。这个区别就好像是广东的省政府在广州，而广东省首号城市广州市的市政府也在广州，虽然地址相同，但是意义不同。为了证明这个观点，我定义了两个数组进行测试。

static int iArray[] = {39, 33, 18, 64, 73, 30, 49, 51, 81};
static char *strArray[] ={"forARM","mzdzkj","c language","shenzhen","china"};
printf("&iArray = %#x \n" , &iArray ) ;
printf("&iArray[0] = %#x \n" , &iArray[0] ) ;
printf("strArray = %#x \n" , strArray ) ;
printf("&strArray = %#x \n" , &strArray ) ;

复制代码

编译之后运行的结果为：
&iArray = 0x402000
&iArray[0] = 0x402000
strArray = 0x402024
&strArray = 0x402024
所以在这个函数中，无论传入的是数组的首元素地址，还是数组的地址，都是可以的，因为有这么一句程序：
pvNext = (char *)pvData + stSize;
所以无论如何，pvNext都是下一元素的地址。
测试程序：

printf("(char*)&iArray[0] + sizeof(iArray[0]) = %#x \n" , (char*)&iArray[0] + sizeof(iArray[0]) ) ;
printf("&iArray[1] = %#x \n\n" , &iArray[1] ) ;
printf("(char*)&strArray[0] + sizeof(strArray[0]) = %#x \n" , (char*)&strArray[0] + sizeof(strArray[0]) ) ;
printf("&strArray[1] = %#x \n" , &strArray[1] ) ;

复制代码

结果：
(char*)&iArray[0] + sizeof(iArray[0]) = 0x402004
&iArray[1] = 0x402004
(char*)&strArray[0] + sizeof(strArray[0]) = 0x402028
&strArray[1] = 0x402028
stAmount：数组中包含的元素个数，我们通常使用：sizeof(strArray) / sizeof(strArray[0]，即为数组总长度除以元素内存大小，这个结果就是数组元素的个数。
stSize：元素内存大小，sizeof(strArray[0]，因为数组内每一个元素的类型相同，所以每个元素的内存大小也就相同。
CompareFun：需要排序的数据类型、升序还是降序。这个函数的原型是：
typedef int (*COMPAREFUN)(const void *pvData1, const void *pvData2);
如果是整型数组需要升序排列，则函数为如程序清单1. 4所示：

程序清单1. 4 整型数组升序

/*******************************************************************************
**函数名称： int_Rise_cmp
**函数功能：对int进行升序排列
**入口参数： *x：
*y：
**出口参数： ( *(int *)x - *(int *)y )
确定升序
*******************************************************************************/
int int_Rise_cmp(void *x , void *y)
{
return ( *(int *)x - *(int *)y );
}

复制代码

我们就综合上述对其进行一个整体的分析。假设需排序的数组为：static int iArray[]    = {39, 33, 18, 64, 73, 30, 49, 51, 81};pvData是需排序数组的首元素地址，由：
  pvThis = pvData;
  pvNext = (char *)pvData + stSize;
那么pvThis即为数组首元素的地址，也就是&iArray[0]，pvNext为下一个元素的地址,也就是&iArray[1]。接着通过CompareFun(pvThis, pvNext)比较两个元素的大小，进入CompareFun，也就是int_Rise_cmp函数，x即为pvThis，y即为pvNext。这样x即为数组首元素的地址，这里还是void*，我们通过强制转化，将x指向整型，即为(int*)x，再去地址，也就是( *(int *)x,数组首元素，y以此类推。如果( *(int *)x - *(int *)y ) >0，也就是CompareFun(pvThis, pvNext)>0，则交换这两个数据，从而达到从小到大排列的目的。交换完成之后，
pvThis = pvNext;
pvNext = (char *)pvNext + stSize;
这样以此类推。
static int iArray[]    = {39, 33, 18, 64, 73, 30, 49, 51, 81};
   static char *strArray[] ={"forARM","mzdzkj","c language","shenzhen","china"};
第二个数组值得一提，这是一个指针数组，即为数组中存储的是指针变量。不相信的话可以测试一下。
printf("strArray[0] = %#x \n\n" , strArray[0] ) ;
结果是：
strArray[0] = 0x403000
很显然是指针。上述两个数组经过排序之后的测试结果如程序清单1. 5所示。

程序清单1. 5 测试结果
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
整型数组数据排序之前:
39 33 18 64 73 30 49 51 81
字符串数组排序之前:
'forARM' 'mzdzkj' 'c language' 'shenzhen' 'china'
整型数组数据升序之后:
18 30 33 39 49 51 64 73 81
整型数组数据降序之后:
81 73 64 51 49 39 33 30 18
字符串数组数据升序之后:
'c language' 'china' 'forARM' 'mzdzkj' 'shenzhen'
字符串数组数据降序之后:
'shenzhen' 'mzdzkj' 'forARM' 'china' 'c language'

lxe · 发表于 2014-8-5 15:39:19

{:soso_e130:}.....好好学习 day day up