首页 > 代码库 > 数据结构与算法系列研究九——排序算法的一些探讨

数据结构与算法系列研究九——排序算法的一些探讨

四种排序

一.实验内容
    
输入20个整数,分别用希尔排序、快速排序、堆排序和归并排序实现由小到大排序并输出排序结果。
二.关键数据结构与核心算法
   关键数据结构:
由于是排序为了简单起见,选用线性表中的数组作为存储结构。
   核心算法:
   1.希尔排序
   
希尔排序的核心还是直接插入法,但是插入的位置有所讲究。要把数组分为许多段,每一段的长度除了最后的有可能不同之外,其他的都相同。该段的长度即为增量,在最后一次必须为一,此时程序变成了直接插入。每次进行隔段插入,不断地调整是的数组变得隔段有序。这样做的目的是为了对直接插入的改进,减小时间复杂度。

  具体代码如下:

技术分享
/*shell sort 主要利用插入排序的思想*/
void ShellSort(int a[],int len)  
{  
    int i,j,temp,increment; //增量
    increment=len;          //初始化为总长度
    do  
    {  
        increment=increment/3+1;  //设置每次的增量值,最后一次必为1
        for (i=increment;i<len;i++)  
        {  //从增量开始递增,若满足后面的比前面的小,就要插入
            if(a[i]<a[i-increment])  
            {  
                temp=a[i];  //临时存储处
                for (j=i-increment;j>=0&&a[j]>temp;j-=increment)   
                {  //注意插入条件j>=0,a[j]>temp
                    a[j+increment]=a[j];  //找到插入位置进行插入
                }  
                a[j+increment]=temp;  //插入到要插的地方
            }  
        }  
    }while(increment>1); //注意当increment为1时仍在循环
}  
View Code

  2.快速排序
     快速排序在最好的情况下时间复杂度最低,但是若本来数组就是序排列的,就会退化为冒泡排序。快速排序关键的就是一次排序的操作。
    首先,选取数组的第一个元素作为支点,将此支点保存,此后该支点位置可以被覆盖。 每次排序时,选用两个指针,一个指向尾部,一个指向首部,如果首部小于尾部则进行循环,尾部指针一直向前移动直至首部等于尾部或者尾部所指节点小于支点,此时,若首部尾部相等循环结束,否则,将该尾部节点覆盖到首部节点位置(注意:开始时首节点即为支点,可以覆盖)。完成该操作后,首节点指针开始向后移动直至遇到1.首位节点相等或2.首节点所指节点大于支点,若为1,则循环结束,否则将该首指针所指节点覆盖到上次的为节点空出的位置上,继续进行尾部指针移动。重复上述过程有限此后,必将得到首指针等于尾指针的情况,此时将支点放到首尾指针所指节点位置。必然得到在支点左边的元素都小于等于支点,在支点右边的都大于等于该支点。然后返回该支点的位置,一次循环结束。
   然后主函数中采用递归的方法即可。
   具体代码如下:

技术分享
/**************快速排序*****************/
int Partiton(int a[],int low,int high)
{  
    int temp,pivotkey;  
    pivotkey=a[low]; //选取支点
    temp=pivotkey;  //暂存支点
    while (low<high)  //条件,相等则结束
    {  
        while (low<high &&a[high]>=pivotkey)  
        {
            high--;//左移  
        }
        a[low]=a[high];//覆盖  
        while (low<high && a[low]<=pivotkey)  
        {
            low++;  //右移
        }
        a[high]=a[low];//覆盖  
    }  
    a[low]=temp; //恢复
    return low;  //返回分界点位置
}  
void Qsort(int a[],int low,int high)  
{  
    int pivot;  
    if (low<high)  
    {  
        pivot=Partiton(a,low,high); //获得分界点位置
        Qsort(a,low,pivot-1); //排左边
        Qsort(a,pivot+1,high);//右边  
    }  
}  
/******************** end  qsort *******************/
View Code

3.堆排序
  
堆排序是一个比较有意思的排序,有虚拟二叉树的结构来进行排序,简称大根堆。要完成堆排序,首先要建立大根堆。首先要按照层次遍历的方法产生完全二叉树。然后,对该二叉树进行调整使得递归的来说,每个根节点都大于等于左右儿子节点。然后,首根节点即为最大元素,将该节点和最后的节点交换。交换之后,最后的节点成为了最大节点,该节点在以后的操作中认为不在大根堆中,然后调整剩余节点使之成为新的大根堆,再交换新的大根堆的最后元素和首根结点。剔除该大根堆最后节点。如此循环下去,直至大根堆只剩一个元素,此元素即为最小元素和自身交换仍为最小元素。至此数组就变成了升序排列的了。
   具体代码:

技术分享
/**********将从i开始的为头节点的子树调整为大根堆************/
void HAdjust(int R[], int i, int n)
{ //i为出发结点下标,n为堆的结点总数
    int  iL,iR,j;//左右子树
    while(i<=n/2-1) //叶子停止,非叶子继续
   {
       iL=2*i+1; //左儿子,下标从0开始
       iR=iL+1;  //右儿子
       j=iL; //j为R[i]要交换的结点下标
       if(iR<n&&R[iR]>R[iL])
       {
           j=iR;//若右子树存在,且该节点大于左儿子,选择右儿子

       }
       if(R[i]>R[j]) //头节点最大
       {
           break; //无需交换,则结束
       }
       swap(R[i], R[j]);//否则交换
       i=j;//标记新的待检核节点,看是否要交换
   }
}
void HeapSort(int R[], int n)
{ //初始建大根堆
    int i;
     for(i=n/2-1; i>=0; i--)
     {
         HAdjust(R, i, n);//建立大根堆,每次都调整使每个子树为大根堆
     }
     for(i=1; i<n; i++)
     {
         swap(R[0], R[n-i]);//将n-i的元素和头节点最大值交换
         HAdjust(R, 0, n-i);//去除交换后的n-i元素,将其他的节点调整为大根堆
     }//从而得到从小到大的序列
}
/***************************heap    end**************************************/
View Code

4.归并排序
   
归并排序的思想是借用一个辅助数组存储每次归并后的节点,每次循环中都从开始进行二路归并,将两个相邻的元素归为有序集合,每次都在缩小归并后的集合数直至最后只剩一个集合即为升序排列的数组。

  具体代码:

技术分享
/***************归并排序:将有序的SR归并到TR中********************/  
void Merge(int SR[],int TR[],int i,int m,int n)  
{  
    int j,k,l;  
    for (j=m+1,k=i;i<=m && j<=n;k++)  
    {  
        if (SR[i]<SR[j])
        {
            TR[k]=SR[i++];//若前半部分小则直接加入
        }
        else   
        {
            TR[k]=SR[j++]; //否则加入后半部分
        }
    }
    //结束时可能有两种情况
    if (i<=m)  
    {  /*将SR[1...m]中多余中的部分添加到TR中*/  
        for (l=0;l<=m-i;l++)  
        {
            TR[k+l]=SR[i+l]; //添加多余部分
        }
    }  
    if (j<=n)   
    { /*将SR[m+1...n]中多余中的部分添加到TR中*/    
        for (l=0;l<=n-j;l++)  
        {
            TR[k+l]=SR[j+l];   //添加多余部分
        }
    }  
}  
/*将SR归并排序为TR1*/  
void MSort(int SR[],int TR1[],int s,int t)  
{  //归并完成后t数组即为升序数组
    int m=0;  
    int TR2[100]={0};  
    if (s==t)  
    {
        TR1[s]=SR[s];//相等则复制
    }
    else  
    {  
        m=(s+t)/2;  //找到中心位置
        MSort(SR,TR2,s,m); //分别进行归并复制,左边
        MSort(SR,TR2,m+1,t); //右边
        Merge(TR2,TR1,s,m,t); //归并
    }  
}  
/******************end  merge********************/
View Code

四.理论与测试
  理论:选用相同的无序数组分别进行四种排序,将得到相同的结果。
  测试:无序数组为:
   a[20]={12,23,43,35,37,26,19,20,1,10,
              32,27,29,89,94,93,108,246,245,17};
  运行程序后结果为:
技术分享

五.附录(源代码)

  1 #include "stdio.h"
  2 #include "stdlib.h"
  3 #include "iostream"
  4 using namespace std;
  5 /*shell sort 主要利用插入排序的思想*/
  6 void ShellSort(int a[],int len)  
  7 {  
  8     int i,j,temp,increment; //增量
  9     increment=len;          //初始化为总长度
 10     do  
 11     {  
 12         increment=increment/3+1;  //设置每次的增量值,最后一次必为1
 13         for (i=increment;i<len;i++)  
 14         {  //从增量开始递增,若满足后面的比前面的小,就要插入
 15             if(a[i]<a[i-increment])  
 16             {  
 17                 temp=a[i];  //临时存储处
 18                 for (j=i-increment;j>=0&&a[j]>temp;j-=increment)   
 19                 {  //注意插入条件j>=0,a[j]>temp
 20                     a[j+increment]=a[j];  //找到插入位置进行插入
 21                 }  
 22                 a[j+increment]=temp;  //插入到要插的地方
 23             }  
 24         }  
 25     }while(increment>1); //注意当increment为1时仍在循环
 26 }  
 27 /****************heap  sort******************/
 28 void swap(int &a,int &b)
 29 {   //交换a与b的值
 30     int temp;
 31     temp =  a;
 32     a = b;
 33     b = temp;
 34 }
 35 /**********将从i开始的为头节点的子树调整为大根堆************/
 36 void HAdjust(int R[], int i, int n)
 37 { //i为出发结点下标,n为堆的结点总数
 38     int  iL,iR,j;//左右子树
 39     while(i<=n/2-1) //叶子停止,非叶子继续
 40    {
 41        iL=2*i+1; //左儿子,下标从0开始
 42        iR=iL+1;  //右儿子
 43        j=iL; //j为R[i]要交换的结点下标
 44        if(iR<n&&R[iR]>R[iL])
 45        {
 46            j=iR;//若右子树存在,且该节点大于左儿子,选择右儿子
 47 
 48        }
 49        if(R[i]>R[j]) //头节点最大
 50        {
 51            break; //无需交换,则结束
 52        }
 53        swap(R[i], R[j]);//否则交换
 54        i=j;//标记新的待检核节点,看是否要交换
 55    }
 56 }
 57 void HeapSort(int R[], int n)
 58 { //初始建大根堆
 59     int i;
 60      for(i=n/2-1; i>=0; i--)
 61      {
 62          HAdjust(R, i, n);//建立大根堆,每次都调整使每个子树为大根堆
 63      }
 64      for(i=1; i<n; i++)
 65      {
 66          swap(R[0], R[n-i]);//将n-i的元素和头节点最大值交换
 67          HAdjust(R, 0, n-i);//去除交换后的n-i元素,将其他的节点调整为大根堆
 68      }//从而得到从小到大的序列
 69 }
 70 /***************************heap    end**************************************/
 71 
 72 
 73 /***************归并排序:将有序的SR归并到TR中********************/  
 74 void Merge(int SR[],int TR[],int i,int m,int n)  
 75 {  
 76     int j,k,l;  
 77     for (j=m+1,k=i;i<=m && j<=n;k++)  
 78     {  
 79         if (SR[i]<SR[j])
 80         {
 81             TR[k]=SR[i++];//若前半部分小则直接加入
 82         }
 83         else   
 84         {
 85             TR[k]=SR[j++]; //否则加入后半部分
 86         }
 87     }
 88     //结束时可能有两种情况
 89     if (i<=m)  
 90     {  /*将SR[1...m]中多余中的部分添加到TR中*/  
 91         for (l=0;l<=m-i;l++)  
 92         {
 93             TR[k+l]=SR[i+l]; //添加多余部分
 94         }
 95     }  
 96     if (j<=n)   
 97     { /*将SR[m+1...n]中多余中的部分添加到TR中*/    
 98         for (l=0;l<=n-j;l++)  
 99         {
100             TR[k+l]=SR[j+l];   //添加多余部分
101         }
102     }  
103 }  
104 /*将SR归并排序为TR1*/  
105 void MSort(int SR[],int TR1[],int s,int t)  
106 {  //归并完成后t数组即为升序数组
107     int m=0;  
108     int TR2[100]={0};  
109     if (s==t)  
110     {
111         TR1[s]=SR[s];//相等则复制
112     }
113     else  
114     {  
115         m=(s+t)/2;  //找到中心位置
116         MSort(SR,TR2,s,m); //分别进行归并复制,左边
117         MSort(SR,TR2,m+1,t); //右边
118         Merge(TR2,TR1,s,m,t); //归并
119     }  
120 }  
121 /******************end  merge********************/
122 
123 /**************快速排序*****************/
124 int Partiton(int a[],int low,int high)
125 {  
126     int temp,pivotkey;  
127     pivotkey=a[low]; //选取支点
128     temp=pivotkey;  //暂存支点
129     while (low<high)  //条件,相等则结束
130     {  
131         while (low<high &&a[high]>=pivotkey)  
132         {
133             high--;//左移  
134         }
135         a[low]=a[high];//覆盖  
136         while (low<high && a[low]<=pivotkey)  
137         {
138             low++;  //右移
139         }
140         a[high]=a[low];//覆盖  
141     }  
142     a[low]=temp; //恢复
143     return low;  //返回分界点位置
144 }  
145 void Qsort(int a[],int low,int high)  
146 {  
147     int pivot;  
148     if (low<high)  
149     {  
150         pivot=Partiton(a,low,high); //获得分界点位置
151         Qsort(a,low,pivot-1); //排左边
152         Qsort(a,pivot+1,high);//右边  
153     }  
154 }  
155 /******************** end  qsort *******************/
156 void MainMenu()
157 {//四个相同的数组,四种不同的排序
158     int a[20]={12,23,43,35,37,26,19,20,1,10,
159                32,27,29,89,94,93,108,246,245,17};
160     int b[20]={12,23,43,35,37,26,19,20,1,10,
161                 32,27,29,89,94,93,108,246,245,17};
162     int c[20]={12,23,43,35,37,26,19,20,1,10,
163                32,27,29,89,94,93,108,246,245,17};
164     int d[20]={12,23,43,35,37,26,19,20,1,10,
165                32,27,29,89,94,93,108,246,245,17};
166     int t[100],n=20,i;//t数组为归并排序服务
167     printf("shell sort:\n");
168     ShellSort(a,n);
169     for(i=0;i<n;i++)
170     {
171         printf("%d  ", a[i]);
172         if((i+1)%10==0)
173         {
174             printf("\n");
175         }
176     }
177     printf("\nheap  sort:\n");
178     HeapSort(b,n);
179     for(i=0;i<n;i++)
180     {
181         printf("%d  ", b[i]);
182         if((i+1)%10==0)
183         {
184             printf("\n");
185         }
186     }
187     printf("\nmerge sort:\n");
188     MSort(c,t,0,n-1);
189     for(i=0;i<n;i++)
190     {
191         printf("%d  ", t[i]);
192         if((i+1)%10==0)
193         {
194             printf("\n");
195         }
196     }
197     printf("\nquick  sort:\n");
198     Qsort(d,0,n-1);  
199     for(i=0;i<n;i++)
200     {
201         printf("%d  ", d[i]);
202         if((i+1)%10==0)
203         {
204             printf("\n");
205         }
206     }
207     printf("\n");
208 }
209 
210 int main()
211 {
212     MainMenu();
213     return 0;
214 }

数据结构与算法系列研究九——排序算法的一些探讨