Code666 (代码贴、代码片段)

[C++] 数据结构与算法----3.5 非递归的快速排序方法 →→→→→进入此内容的聊天室

来自 , 2020-11-27, 写在 C++, 查看 129 次.
URL http://www.code666.cn/view/52dbb068
  1. #include <iostream>
  2. using namespace std;
  3. #include <iostream>
  4. using namespace std;
  5. typedef int KeyType;
  6. struct LElemType              
  7. {
  8.         KeyType key;
  9. };
  10. struct SElemType
  11. {          
  12.         int a;
  13.         int b;
  14. };
  15. struct SList
  16. {
  17.     LElemType *r;
  18.         int length;
  19. };
  20.  
  21. const int StackInitSize=10;
  22. const int StackInc=15;
  23.  
  24. struct SStack
  25. {
  26.     SElemType *base,*top;
  27.         int stacksize;
  28. };
  29.  
  30. bool StackInit (SStack &S);//构造栈
  31. bool Push(SStack &S,SElemType &e);//入栈
  32. bool Pop(SStack &S,SElemType &e);//出栈
  33. bool StackEmpty(SStack &S);//空栈
  34. bool ListCreate(SList &L,int n,LElemType a[]);//创建顺序表
  35. void Listshow(SList &L);//显示表
  36. void quicksort(SList &L);//非递归的快速排序
  37. void InsertSort(SList &L) ;
  38. int Partition(SList &L, int a, int b);
  39. int main()
  40. {
  41.         const int i=13;
  42.         LElemType a[i]={3,7,1,5,9,6,4,10,15,12,14,19,16};
  43.         SList L;
  44.         ListCreate(L,i,a);
  45.         cout<<"待排序的元素序列为"<<endl;
  46.         Listshow(L);
  47.         quicksort(L);
  48.     cout<<endl<<"非递归的快速排序后元素序列为"<<endl;
  49.         Listshow(L);
  50.     cout<<endl;
  51.         return 0;
  52. }
  53. bool ListCreate(SList &L,int n,LElemType a[])
  54. {
  55.         int i;
  56.         L.r=new LElemType[n];
  57.         if(!L.r)                        return false;  
  58.         L.length=n;
  59.         for(i=0;i<n;i++)
  60.         {
  61.                 L.r[i]=a[i];
  62.         }
  63.         return true;
  64. }
  65. void Listshow(SList &L)
  66. {
  67.         int i=L.length;
  68.         for(int j=0;j<i;j++)
  69.         {
  70.                 cout<<L.r[j].key<<"  ";
  71.         }
  72. }
  73. bool StackInit (SStack &S)
  74. {
  75.         S.base=new SElemType[StackInitSize];
  76.         if(!S.base) return false;
  77.         S.top=S.base;
  78.         S.stacksize=StackInc;
  79.         return true;
  80. }
  81. bool StackEmpty(SStack &S)
  82. {
  83.         return S.top==S.base;
  84. }
  85. bool Push(SStack &S,SElemType &e)
  86. {
  87.         SElemType *base;
  88.         if(S.top-S.base==S.stacksize)
  89.         {
  90.                 base=(SElemType*)realloc(S.base,(S.stacksize+StackInc)*sizeof(SElemType));
  91.                 if(!base) return false;
  92.                 S.base=base;
  93.                 S.top=S.base+S.stacksize;
  94.                 S.stacksize+=StackInc;
  95.         }
  96.         *S.top=e;
  97.         S.top++;
  98.         return true;
  99. }
  100. bool Pop(SStack &S,SElemType &e)
  101. {
  102.         if(S.top==S.base) return false;
  103.         S.top--;
  104.         e=*S.top;
  105.         return true;
  106. }
  107. int Partition(SList &L, int a, int b)
  108. {
  109.         LElemType x = L.r[a];
  110.         while (a < b) {
  111.                 while (a < b && L.r[b].key >= x.key) {
  112.                         b--;
  113.                 }
  114.                 L.r[a] = L.r[b];
  115.                 while (a < b && L.r[a].key <= x.key) {
  116.                         a++;
  117.                 }
  118.                 L.r[b] = L.r[a];
  119.         }
  120.         L.r[a] = x; return a;
  121. }
  122. void quicksort(SList &L)
  123. {
  124.                 SStack S; StackInit(S);
  125.         SElemType e, p;
  126.         e.a = 0; e.b = L.length-1;
  127.         Push(S, e); int t;
  128.         while (Pop(S, e)) {
  129.                 if (e.b-e.a<7) {
  130.                         continue;
  131.                 }
  132.                 t = Partition(L, e.a, e.b);
  133.                 p.a = e.a; p.b = t - 1;
  134.                 Push(S, p);
  135.                 p.a = t + 1; p.b = e.b;
  136.                 Push(S, p);
  137.         }
  138.         InsertSort(L);
  139.  
  140. }
  141. void InsertSort(SList &L)
  142. {            
  143.         int i, j; LElemType x;
  144.         for (i = 1; i < L.length; i++) {
  145.                 for (x = L.r[i], j = i - 1; j >= 0 && x.key < L.r[j].key; j--) {
  146.                         L.r[j + 1] = L.r[j];
  147.                 }
  148.                 L.r[j + 1] = x;
  149.         }
  150. }

回复 "数据结构与算法----3.5 非递归的快速排序方法"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666