DexterChen

大梦谁先觉?凭生我自知,草堂春睡足,窗外日迟迟

 

非递归的方式实现快速排序

     前段看到过一个问题(忘记在哪里了),用非递归的方式实现快速排序,今天又翻了出来,把代码贴上,给自己以后留个参考,代码中包括自己当时对程序改进的过程,请大家多提意见。

#include "stdafx.h"

#include <iostream>

#include <stack>

 

#define MAX_SIZE      10

using namespace std;

 

typedef int elem;

typedef std::stack<int> Stack;

 

int partition(elem *pData, int low, int high);

void swap(elem& a, elem& b);

void qsort(elem* pData, int low, int high);

void qsort2(elem* pData, int low, int high);

void qsort3(elem* pData, int low, int high);

 

int partition(elem *pData, int low, int high)

{

       elem key = pData[low];

 

       while(low < high)

       {

              while(low < high && pData[high] >= key)

                     high--;

 

              swap(pData[low], pData[high]);

 

              while(low < high && pData[low] <= key)

                     low++;

 

              swap(pData[low], pData[high]);

       }

 

       return low;

}

 

void swap(elem& a, elem& b)

{

       if(&a != &b)

       {

              a ^= b;

              b ^= a;

              a ^= b;

       }

 

}


//这个是原始的算法 

void qsort(elem* pData, int low, int high)

{

       if(low < high)

       {

              int pivot = partition(pData, low, high);

              qsort(pData, low, pivot - 1);

              qsort(pData, pivot + 1, high);

       }

}


//这个是第一次转化成递归以后的算法

void qsort2(elem* pData, int low, int high)

{

       Stack st;

 

       if(low < high)

       {

              int pivot = partition(pData, low, high);

              st.push(low);

              st.push(pivot - 1);

 

              st.push(pivot + 1);

              st.push(high);

             

              while(!st.empty())

              {

                     high = st.top();

                     st.pop();

                     low = st.top();

                     st.pop();

                    

                     pivot = partition(pData, low, high);

                    

                     if(low < high)

                     {

                            st.push(low);

                            st.push(pivot - 1);

 

                            st.push(pivot + 1);

                            st.push(high);

                     }

              }

       }

}


//这个是转化成递归以后改进的算法
void qsort3(elem* pData, int low, int high)

{

       Stack st;

       int tmp;

 

       if(low < high)

       {

              int pivot = partition(pData, low, high);

              st.push(low);

              st.push(pivot - 1);

 

              st.push(pivot + 1);

              st.push(high);

             

              while(!st.empty())

              {

                     high = st.top();

                     st.pop();

                     low = st.top();

                     st.pop();

                    

                     if(low < high)

                     {

                            pivot = partition(pData, low, high);

                           

                            tmp = pivot - 1;

                            if(low < tmp)

                            {

                                   st.push(low);

                                   st.push(tmp);

                            }

 

                            tmp = pivot + 1;

                            if(tmp < high)

                            {

                                   st.push(tmp);

                                   st.push(high);

                            }

                     }

              }

       }

}

 

//测试代码
int _tmain(int argc, _TCHAR* argv[])

{

      

       elem data[MAX_SIZE] = {12, 1, 13, 14, 67, 23, 12, 3, 90, 76};

       //qsort(data, 0, MAX_SIZE - 1);

       //qsort2(data, 0, MAX_SIZE - 1);

       qsort3(data, 0, MAX_SIZE - 1);

      

       for(int i=0; i< MAX_SIZE; i++)

       {

              cout << data[i] << " ";

       }

 

       cout << endl;

      

       cin.get();

       return 0;

}

posted on 2007-02-14 09:42 DexterChen 阅读(4779) 评论(4)  编辑 收藏 引用 所属分类: C++Algorithms

评论

# 我来了 2007-02-14 10:06 gm

留个脚印  回复  更多评论   

# 鼓掌 2007-02-14 10:17 gm

写的好啊,虽然我还没看了  回复  更多评论   

# re: 非递归的方式实现快速排序 2007-10-25 23:27 leizhao

非递归算法中怎么样先把大的区段先入栈,先排序短的子序列?请大虾们指教!  回复  更多评论   

# re: 非递归的方式实现快速排序 2009-06-25 01:25 ant

更快了吗  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

搜索

最新评论

阅读排行榜

评论排行榜