快排的非递归
这里我们需要借助数据结构的栈模拟快排的递归过程(栈先进后出)
实现思想:
1.先将需要排序的区间入到栈中
2.栈不为空时,将需要排序区间读取出来,进行单趟排序,获得了key位置,判断key左右区间是否存在,若存在,将左右下标数据入栈,若不存在(表示区间里只有一个数或者没有数),不做处理。
3.重复此过程,直到栈为空时,排序完成。
这里三数取中是优化快排,单趟排序推荐前后指针法,单趟排序详情可看冒泡与快排那篇文章。
int MidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[mid] < a[left])
{
if (a[mid] > a[right])
return mid;
else if (a[right] < a[left])
return right;
else
return left;
}
else
{
if (a[left] > a[right])
return left;
else if (a[mid] > a[right])
return right;
else
return mid;
}
}
void Swap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
int SingleSort(int* a, int begin, int end)
{
int mid = MidIndex(a, begin, end);
Swap(&a[mid], &a[begin]);
int key = begin;
int prev = begin;
int cur = begin + 1;
while (cur <= end)
{
if (a[cur] < a[key] && ++prev != cur)
{
Swap(&a[cur], &a[prev]);
}
cur++;
}
Swap(&a[prev], &a[key]);
return prev;
}
//入数据记得先入左边,再入右边,栈先进后出的性质
void QuickSortNonR(int* a, int left, int right)//借助栈结构模拟递归过程
{
stack<int> st;
st.push(left);
st.push(right);//先将需排序区间入栈
while (!st.empty())//判断栈中是否还有需排序区间
{
int end = st.top();
st.pop();
int begin = st.top();
st.pop();
int keyi = SingleSort(a, begin, end);
if (keyi + 1 < end)//表示keyi右边区间存在,入栈
{
st.push(keyi + 1);//先入左边下标
st.push(end);//在入右边下标
}
if (keyi - 1 > begin)//表示keyi左边区间存在,入栈
{
st.push(begin);//先入左边下标
st.push(keyi - 1);//在入右边下标
}
}
}
调用
int main()
{
int a[] = { 1,21,7,27,9,2,0,5,8,3,11,15,17,19};
int len = sizeof(a) / sizeof(int);
QuickSortNonR(a, 0, len - 1);
for (int i = 0; i < len; i++)
{
cout << a[i] << " ";
}
return 0;
}
程序结果