快速排序的递归与非递归算法实现

自己简单测试是通过的，欢迎大家测试，并指正，谢谢

//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();

}

}

}

}

阅读(1722) | 评论(0) | 转发(0) |

0

上一篇：二叉树前序中序恢复

下一篇：C++中虚函数工作原理和(虚)继承类的内存占用大小计算

给主人留下些什么吧！~~

评论热议

请登录后评论。

登录 注册