排序算法分析和比较

一、设计思想排序是数据处理中使用频率很高的一种操作，是数据查询之前需要进行的一项基础操作。它是将任意序列的数据元素（或记录）按关键字有序（升序或降序）重新排列的过程。排序的过程中有两种基本操作:一是比较两个关键字的值;二是根据比较结果移动记录位置。排序的算法有很多种，这里仅对插入排序、选择排序、希尔排序、归并排序和快速排序作了比较。直接插入排序算法基本思路：直接插入排序时将一个元素插入已排好的有序数组中，从而得到一个元素个数增加1的新的有序数组。其具体实现过程是，将第i个元素与已经排好序的i-1个元素依次进行比较，再将所有大于第i个元素的元素后移一个位置，直到遇到小于或等于第i个元素，此时该元素的后面一个位置为空，将i元素插入此空位即可。选择排序算法基本思路：定义两个数组sela[]和temp[]，sela[]用来存放待排序数组，temp[]用来存放排好序的数组。第一趟，将sela口数组中n个元素进行比较，找出其中最小的元素放入temp[]的第一个位置，同时将sela口中将该元素位置设置为无穷大。第二趟，将sela口数组中n个元素进行比较，找出其中最小的元素放入temp口的第二个位置，同时将sela[]中将该元素位置设置为无穷大。以此类推，n趟后将sela口中所有元素都已排好序放入temp[]数组中。希尔排序算法基本思路：希尔排序又称为变长步径排序，它也是一种基于插入排序的思想。其基本思路是，定义一个步长数组gaps[1,5,13,43……]，先选取合适的大步长gap将整个待排序的元素按步长gap分成若干子序列，第一个子序列的元素为a[0]、a[0+gap]、a[0+2gap]a[0+k*gap];第二列为a[1]、a[1+gap]、a[1+2gap]a[1+k*gap]；。然后，对这些子序列分别进行插入排序，然后将gap按gaps口数组中的步长缩小，按缩小后的步长再进行子序列划分排序，再减小步长直到步长为1为止。归并排序算法基本思路：归并排序是将两个或两个以上的有序表合并成为一个新的有序表。其基本思路是，将n个待排元素从top到bottom中间分成两部分left[top]~left[mid]和right[mid+1]~right[bottom]。再将left和right每部分分别从中间分成两部分，这样一直分下去，直到分成的两部分数组长度为1。然后，将相邻的两个子数组比较大小后两两依次合并，直到最后变成一个长度为n的有序数组，这就是所需数组。快速排序算法基本思路：快速排序算法是一种特殊是归并排序，它是在切分的时候按大小分开，最后再合并。其基本思路是，将n个待排数的第一个数作为支点pivot，将比pivot小的数存入small[]数组中，比pivot大的数存入big口数组中。再分别以small[]数组和big[]数组中的第一个数作为pivot对small[]数组和big[]数组进行切分。最后直到按支点pivot划分后small口和big口中为空或只有一个元素时停止切分。按照small：],pivot、big[]的顺序将切分后的元素进行合并就得到长度为n的有序数组，即为所需。

二、算法流程图将当前元素s[curr]与已经排好序的curr-1个元素依次进行比较，再将所有大于s[curr]的元素后移一个位置。再将当前元素插入空位。图2选择排序流程图遍历数组找出数组中最小值存入temp[]中，并将原数组最小值位置元素赋予无穷大，继续遍历。直到将原数组所有数都存入temp[]。temp口数组即为所得。图3希尔排序流程图大步长gap将整个待排序的元素按步长gap分成若干子序列然后，对这些子序列分别进行插入排序，然后将gap按gaps[]数组中的步长缩小，按缩小后的步长再进行子序列划分排序，再减小步长直到步长为1为止。将待排元素中间分成两部分left和right。再将left和right每部分分别从中间分成两部分，这样一直分下去，直到分成的两部分数组长度为1。然后，将相邻的两个子数组比较大小后两两依次合并。图5快速排序流程图将待排元素的第一个数作为支点pivot，将比pivot小的数存入small[]数组中，比pivot大的数存入big[]数组中。再分别以small[]数组和big口数组中的第一个数作为pivot对small[]数组和big口数组进行切分。最后直到分出的数组中为空或只有一个元素为止。按照small：],pivot、big[]的顺序将元素进行合并就得到长度为n的有序数组。三、源代码#defineN100#include<stdio.h>#include<math.h>intcount=0,step=0;/*定义全局变量作为比较次数和移动次数计数器*/main(){intinsa[N],sela[N],shea[N],mera[N],quia[N];/*为了防止数组排好序后，有些排序方法偷懒，所以定义五个数组*/inti,j;for(j=1;j<5;j++)/*循环变量，使程序进行四组数据结果的输出*/{

for(i=0;i<N;i++)/*循环变量，为数组赋值*/insa[i]=sela[i]=shea[i]=mera[i]=quia[i]=rand()%100;/*五组数组相同，且每个数为0~100的随机数*//*输出这是第几次数据排序*/printf("*****************%d***********************\n",j);count=0,step=0;/*初始化全局变量*/inssort(insa);/*调用插入排序函数体，并将数组insa传入*/printf("\n====================Insertsort================\n");printf("Thetimesofcomparementis:%d”,count);/*比较次数输出*/printf("Thetimesofmovementis:%d\n",step);/*移动次数输出*/count=0,step=0;/*初始化全局变量*/selsort(sela);/*调用选择排序函数体，并将数组sela传入*/printf("======================Selectsort===============\n");printf("Thetimesofcomparementis:%d”,count);/*比较次数输出*/printf("Thetimesofmovementis:%d\n",step);/*移动次数输出*/count=0,step=0;/*初始化全局变量*/shesort(shea);/*调用希尔排序函数体，并将数组shea传入*/printf("======================Shellsort================\n");printf("Thetimesofcomparementis:%d”,count);/*比较次数输出*/printf("Thetimesofmovementis:%d\n",step);/*移动次数输出*/count=0,step=0;/*初始化全局变量*/mergesort(mera,0,99);/*调用归并排序函数体，并将数组mera传入*/printf("======================Mergesort================\n");printf("Thetimesofcomparementis:%d”,count);/*比较次数输出*/printf("Thetimesofmovementis:%d\n",step);/*移动次数输出*/count=0,step=0;/*初始化全局变量*/quickSort(quia,0,99);/*调用快速排序函数体，并将数组quia传入*/printf("=====================Quicksort================\n");printf("Thetimesofcomparementis:%d”,count);/*比较次数输出*/printf("Thetimesofmovementis:%d\n”,step);}/*/*输出这是第几次数据排序*/getch();}inssort(ints[])/*插入排序函数体*/{intcurr,i,index,temp;/*定义函数所需变量*/index=-1;for(curr=1;curr<N;curr++){index=-1;/*主索引用于标识插入位置*/for(i=0;i<curr;i++){count++;/*比较过程计数*/if(s[i]>s[curr])/*数值比较过程*/{index=i;/*插入位置确定*/break;}}if(index==-1)continue;/*当前元素没有插入位置时，循环继续，查看下一个数*/else(temp=s[curr];for(i=curr;i>index;i--)/*元素移动过程*/(step++;/*移动过程计数*/s[i]=s[i-1];}/*需移动的元素依次向后移动一个位置*/s[index]=temp;/*将要插入的数值插入*/}}}selsort(ints[])/*选择排序函数体*/{inttemp[N],x,i,j,k=0,min=9999;/*定义函数所需变量和数组*/for(x=0;x<N;x++)/*数组循环进行每个数值的比较*/{j=0;for(i=0;i<N;i++){if(s[i]<min)/*比较过程，找出当前数组中最小值*/{min=s[i];/*将最小值选出赋给min*/j=i;/*标记最小值*/}count++;/*比较次数计数器*/}s[j]=9999;/*数组中之前最小值位置设为无穷大*/temp[k++]=min;/*将当前数组中最小值存入temp数组*/step++;}/*移动过程计数器*/}shesort(ints[])/*希尔排序函数体*/{intgaps[4]={1,5,13,43};/*定义步长数组，存放变长步径时所需步长*/inti=0,j=0;intgap,k=0,temp=0;/*定义步长变量，步长在步长数组位置，临时变量*/for(k=0;gaps[k]<N;k++);/*寻找适合数组的最大步径*/while(--k>=0)/*大步径变为小步径过程*/{gap=gaps[k];/*取得当前步长值*/for(i=gap;i<N;i++)/*比较过程*/{count++;/*比较过程计数*/temp=s[i];j=i;while(j>=gap&&s[j-gap]>temp)/*将当前比较的子序列最小值移到前面位置*/{s[j]=s[j-gap];j=j-gap；step++;/*移动过程计数*/}s[j]=temp;}}}mergesort(ints[],inttop,intbottom)/*归并排序函数体*/{intmid;/*切割位置中点*/if(top<bottom)(/*循环切割*/mid=(top+bottom)/2;/*初始化切割位置*/mergesort(s,top,mid);/*分割第一部分继续切割*/mergesort(s,mid+1,bottom);/*分割第二部分继续切割*/merge(s,top,mid,bottom);/*归并操作*/}}merge(ints[],inttop,intmid,intbottom)/*归并函数*/{inti,j,left=top,right=mid+1,index=0;/*定义函数所需变量*/intbegin=0,end=0;inttemp[1000];/*定义临时数组*/while(left<=mid&&right<=bottom)/*比较的条件*/{count++;/*比较过程计数*/if(s[left]<=s[right])(step++;/*移动过程计数*/temp[index]=s[left];/*将比较后较小数存入临时数组*/left++;}else(step++;/*移动过程计数*/temp[index]=s[right];/*将比较后较小数存入临时数组*/right++;}index++;/*主索引递增*/}if(left<=mid)(count++;/*比较过程计数*/begin=left;end=mid;}else(count++;/*比较过程计数*/begin=right;end=bottom;}for(i=begin;i<=end;i++){step++;/*移动过程计数*/temp[index]=s[i];/*将未移动的数存入临时数组*/index++;}for(i=top,j=0;i<=bottom;i++,j++)/*将此过程中排好序的数组存入临时数组中*/{s[i]=temp[j];}}quickSort(ints[],inttop,intbottom)/*快速排序函数体*/{inti=0;intbig[N],small[N];/*定义临时数组分别存储比支点大的和小的元素*/intsmallindex=0,bigindex=0,index;/*定义数组指针*/intpivot=0;/*初始化支点*/if(top<bottom){pivot=s[top];/*定义支点为数组的第一个元素*/for(i=top+1;i<=bottom;i++){if(s[i]>=pivot){count++;/*比较过程计数*/big[bigindex]=s[i];/*将比支点大的数存入big数组*/bigindex++;}else{count++;/*比较过程计数*/small[smallindex]=s[i];/*将比支点小的数存入small数组*/smallindex++;}}index=0;/*初始化主索引*/for(i=0;i<smallindex;i++){step++;/*移动过程计数*/s[index+top]=small[i];/*将small内数据在指定位置还原到原数组*/index++;}s[index+top]=pivot;/*将支点还原到原数组指定位置*/index++;step++;for(i=0;i<bigindex;i++){step++;/*移动过程计数*/s[index+top]=big[i];/*将big内数据在指定位置还原到原数组*/index++;}quickSort(s,top,top+smallindex);/*递归排列small数组数据*/quickSort(s,top+smallindex+1,bottom);/*递归排列big数组数据*/}}四、运行结果程序运行结果如下图:应G:\#序算"2\SORT(1"1.eze====================Insertsort================Thetimesofcomparementis:2548Thetimesofmouementis:2494======================Selectsort===============Thetimesofcomparementis:10000Thetimesofmouementis:100======================8he1Isort================Thetimesofcomparementis:338Thetimesofmouementis:367======================Me凹已？oM================Thetimesofcomparementis:640Thetimesofmouementis:672=====================Quicksort================Thetimesofcomparementis:661Thetimesofmouementis:760====================Insertsort================Thetimesofcomparementis:2485Thetimesofmouementis:2559======================Selectsort===============Thetimesofcomparementis:10000Thetimesofmouementis:100======================8heIlsort================Thetimesofcomparementis:338Thetimesofmouementis:481======================Mergesort================Thetimesofcomparementis:640Thetimesofmouementis:672=====================Quicksort================Thetimesofcomparementis:782Thetimesofmouementis:881I====================Insertsort================Thetimesofcomparementis:2464Thetimesofmouementis:2584======================Selectsort===============Thetimesofcomparementis:10000Thetimesofmouementis:100======================ShEIls================Thetimesofcomparementis:338Thetimesofmouementis:492======================Mergesort================Thetimesofcomparementis:638Thetimesofmouementis:672=====================Quicksort================Thetimesofcomparementis:768Thetimesofmouementis:868====================Insertsort================Thetimesofcomparementis:2932Thetimesofmouementis:2111======================Selectsort===============Thetimesofcomparementis:10000Thetimesofmouementis:100======================8heIlsort================Thetimesofcomparementis:338Thetimesofmouementis:431======================Mergesort================Thetimesofcomparementis:642Thetimesofmouementis:672=====================Quicksort================Thetimesofcomparementis:696Thetimesofmouementis:795图6数组排序移动和比较次数结果直接插入排序算法当记录的数量n很小时，是一种很好的排序方法。希尔排序方法是改进的插入排序方法，在时间效率上较直接插入排序有较大的提高。从分析可知，希尔排序和插入排序时间复杂度为O(m)，但是当待排序记录处于〃基本有序〃状态或当n值较小时，直接插入排序的效率可大大提高。但是通常待排序的记录数量n很大时，希尔排序则优于插入排序。选择排序均为比较10000次，移动100次，属于移动最优的排序算法，但是它的缺点就是进行判断比较的次数比较多。进行归并排序时，其时间复杂度为O(nlogn)，它是一种2比较稳定的算法。快速排序相比归并排序速度快但稳定性不高，其最坏情况：O(n*n)；最好情况：O(nlogn)。2五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：希尔排序中选取合适步长以及实现问题在希尔排序函数体中定义好步长gaps口数组后，通过使用for循环for(k=0;gaps［k］＜N;k++)让k循环自加找到小于数组长度N的最大步长gaps［k］。