快速排序迭代实现-白红宇

快速排序迭代实现

阅读量：2352 次

发布时间：2019-05-10

本文共 2334 字，大约阅读时间需要 7 分钟。

文章来源：http://blog.csdn.net/pkuyjxu/article/details/6918295

快速排序（QUICKSORT）是一个非常流行并且高效的排序算法，具有o(nlogn)的平均运行时间，

这个算法优于合并排序(MERGESORT)的一点就是它是在原位排序，即对于被排序的元素不需要辅助

的存储空间。在描述这个排序算法之前，需要一下的划分算法，它是(QUICKSORT)的基础。

划分算法

原理：如果元素A[j]既不大于A[low...j-1]中的元素，也不小于A[j+1...high]的元素，则称其处于一

个适当的位置或正确的位置。

观察结论：用x(x∈A)作为主元素划分数组A后，x将处于一个正确的位置。

我们感兴趣的是在没有辅助数组的情况下进行划分，有几种方法可以达到这个目的，这里选取两种来实现。

1.从左往右搜索

 int split(int data[],int low,int high)  
 {  
     int i=low;  
     int x=data[low];  
     int tmp;  
     for(int j=low+1;j<=high;j++)  
     {  
         if(data[j]>x)  
         {   i++;  
             if(i!=j)   
             {  
                 tmp=data[j];  
                 data[j]=data[i];  
                 data[i]=tmp;  
             }  
         }  
     }  
     tmp=data[low];  
     data[low]=data[i];  
     data[i]=tmp;  
     return i;  
 }  

2.从两边往中间搜索

       ·········10········20········30········40········50········60········70········80········90········100·······110·······120·······130·······140·······150 
 int quicksort(int data[],int s,int t)  
 {  
   int i=s,j=t;  
   int tmp;  
   if(s<t)  
   {  
     tmp=data[s];  
     while(i!=j)  
     {  
       while(j>i&&data[j]<=tmp) j--;  
       data[i]=data[j];  
       while(i<j&&data[i]>=tmp) i++;  
       data[j]=data[i];             
     }  
     data[i]=tmp;  
     return i;  
   }  
 }  

排序算法

1.递归形式

 void quicksort(int data[],int low,int high)  
 {  
     if(low<high)  
     {  
         int w=split(data,low,high);  
         quicksort(data,low,w-1);  
         quicksort(data,w+1,high);  
     }  
 }  

2.迭代形式

递归转化为迭代算法的关键是传递每次划分的low和high，所以定义一个结构体st来存储每次划分的low和high，

top初始为-1，用来记录长度。划分一次st长度++，进入划分一次st长度--，直到top=-1。

 struct node  
 { int low,high;  
 }st[10000];  
 void quicksort2(int data[],int s,int t)  
 {  
     int top=-1,low,high;  
     top++;  
     st[top].low=s;st[top].high=t;  
     while(top>-1)  
     {  
         low=st[top].low;high=st[top].high;  
         top--;  
         int w;  
         if(low<high)  
         {  
             w=split(data,low,high);//或者split2  
             st[++top].low=low;st[top].high=w-1;  
             st[++top].low=w+1;st[top].high=high;  
         }  
     }  
 }  

最后给出一段测试代码，很好用！

 #include<stdio.h>  
 #include<stdlib.h>  
 #define MAXSIZE 10000 //所有数组中元素的个数最多为MAXSIZE个  
 int isASCENDING(ELEMET_TYPE heap[],int n)  
 {  
      
     int i;  
     for(i=n-1;i>0;i--)  
         if(heap[i-1]<heap[i])  
             return 0;//只要有一个结点比其后的结点小，则该数组肯定不是降序序列   
     return 1;  
 }  
 void test()  
 {  
     ELEMET_TYPE test_elem[10000];  
     for(int test_Turn=0;test_Turn<100;test_Turn++)  
     {  
         printf("第%d轮：",test_Turn+1);   
         int test_num=rand()%5000+5000;  
         for(int i=0;i<test_num;i++)  
             test_elem[i]=rand();  
         QUICKSORT(test_elem,test_num);  
         if(!isASCENDING(test_elem,test_num))  
         {  
             printf("错误/n");  
             system("pause");  
             exit(0);   
         }  
         printf("正确/n");   
     }     
     printf("测试通过/n");   
     system("pause");  
 }  
 void QUICKSORT(ELEMET_TYPE data[],int n)  
 {      
     quicksort(data,0,n-1);     
 }  
 int main()//主函数   
 {  
           
     test();   
     return 0;  
       
 } 