------------------------------------------
本文为本人原创，欢迎转载!
雪夜流星
------------------------------------------
快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。实现代码如下：
#include
#include
/*********************************************************************************
*功能描述：快速排序算法
*传入参数：num：需要排序的数组首地址， low:需要排序的数组起始下标 high：截止下标
*传出参数：num：排序后的数组首地址，传入参数和传出参数空间复用，降低空间复杂度
*返回值： 无
**********************************************************************************/
void quick_sort(int *num, int low, int high)
{
int tmp, i, j, t;
/*把low>=high作为递归结束的条件，所以这个判断是必须的；否则递归没完没了，最终 导致段错误*/
if(low < high)
{
tmp = num[low];//用子表的第一个记录做枢轴记录
i = low;
j = high+1;//保证后续的j=j-1的通式子的运用
while(i
{
for(i=i+1; i 的数时，直接跳出循环
{
if(num[i] >= tmp)
{
break;
}
}
for(j=j-1; j>low; j--)//从后往前扫描，当找到第一个比枢轴小的 数时，直接跳出循环
{
if(num[j] <= tmp)
{
break;
}
}
if(i
{
t = num[i];
num[i] = num[j];
num[j] = t;
}
}
/*当子表中除枢轴以外的数都划分之后，最后将枢轴记录与从后往前扫第一个比 枢轴小的数交换*/
t = num[low];
num[low] = num[j];
num[j] = t;
/*分别将枢轴前后两边的子表递归调用，完成这两个子表的*/
quick_sort(num, low, j-1);
quick_sort(num, i, high);
}
return;
}
int main(void)
{
int i;
int num[5] = {5, 4, 3, 2, 1};
printf("before:\n");
for(i=0; i<5; i++)
{
printf("num[%d]:%d\n", i, num[i]);
}
quick_sort(num, 0, 4);
printf("after:\n");
for(i=0; i<5; i++)
{
printf("num[%d]:%d\n", i, num[i]);
}
return 0;
}
阅读(1578) | 评论(1) | 转发(1) |
