Chinaunix首页 | 论坛 | 博客
  • 博客访问: 429435
  • 博文数量: 83
  • 博客积分: 2622
  • 博客等级: 少校
  • 技术积分: 1345
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-17 08:59
个人简介

一直在努力

文章分类

全部博文(83)

文章存档

2014年(3)

2013年(9)

2012年(46)

2010年(25)

分类: C/C++

2012-10-22 10:55:33

自己简单测试是通过的,欢迎大家测试,并指正,谢谢
//partition,定位元素start的正确位置,范围start元素在序列中的索引;
int partition(int * collection, int start,int end)
{
int i=start;
int j=end;
int sel_elem = collection[start];
while(i< j)
{
while (collection[j] > sel_elem && i
{
j--;
}
if (i
{
/*swap(collection,i,j);*/
collection[i] = collection[j];
++i;
}
while(collection[i]
{
i++;
}
if (i
{
/* swap(collection,i,j);*/
collection[j] = collection[i];
--j;
}
}
collection[i] = sel_elem;
return i;
}
//递归调用方法
void QuickSort(int * collection, int start,int end)
{

if (start >= end)
{
return;
}
int index = partition(collection,start,end);
for (int i=start; i<=end; i++)
{
printf("%d ", collection[i]);
}
printf("\n");
QuickSort(collection,start,index-1);
QuickSort(collection,index+1,end);
}

//非递归快速排序
void QuickSort2(int * collection, int start, int end)
{
stack st;
int len = end - start +1;
if (start == end)
{
return;
}
int index;
for (int i=0; i
{
index = partition(collection,start,end);
if (index-1 > start)
{
//处理左半部分
st.push(index);
end = index -1;
}else
{
//处理右半部分
start = index +1;
if (st.empty())
{
end = len -1;
}else{
end = st.top()-1;
st.pop();

}

}
}

}
阅读(1717) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~