几种排序算法的分析与比较--C语言
一、设计思想
插入排序：首先，我们定义我们需要排序的数组，得到数组的长度。如果数组只有一个数字，那么我们直接认为它已经是排好序的，就不需要再进行调整，直接就得到了我们的结果。否则，我们从数组中的第二个元素开始遍历。然后，启动主索引，我们用curr当做我们遍历的主索引，每次主索引的开始，我们都使得要插入的位置（insertIndex）等于-1，即我们认为主索引之前的元素没有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪动位置。然后，开始副索引，副索引遍历所有主索引之前的排好的元素，当发现主索引之前的某个元素比主索引指向的元素的值大时，我们就将要插入的位置（insertIndex）记为第一个比主索引指向元素的位置，跳出副索引；否则，等待副索引自然完成。副索引遍历结束后，我们判断当前要插入的位置（insertIndex）是否等于-1，如果等于-1，说明主索引之前元素的值没有一个比主索引指向的元素的值大，那么主索引位置的元素不要挪动位置，回到主索引，主索引向后走一位，进行下一次主索引的遍历；否则，说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大，那么，我们记录当前主索引指向的元素的值，然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位，这里注意，要从后向前一位一位挪，否则，会使得数组成为一串相同的数字。最后，将记录下的当前索引指向的元素的值放在要插入的位置（insertIndex）处，进行下一次主索引的遍历。继续上面的工作，最终我们就可以得到我们的排序结果。插入排序的特点在于，我们每次遍历，主索引之前的元素都是已经排好序的，我们找到比主索引指向元素的值大的第一个元素的位置，然后将主索引指向位置的元素插入到该位置，将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法，使得挪动的次数相对较多，如果对于排序数据量较大，挪动成本较高的情况时，这种排序算法显然成本较高，时间复杂度相对较差，是初等通用排序算法中的一种。
选择排序：选择排序相对插入排序，是插入排序的一个优化，优化的前提是我们认为数据是比较大的，挪动数据的代价比数据比较的代价大很多，所以我们选择排序是追求少挪动，以比较次数换取挪动次数。首先，我们定义我们需要排序的数组，得到数组的长度，定义一个结果数组，用来存放排好序的数组，定义一个最小值，定义一个最小值的位置。然后，进入我们的遍历，每次进入遍历的时候我们都使得当前的最小值为9999，即认为每次最小值都是最大的数，用来进行和其他元素比较得到最小值，每次认为最小值的位置都是0，用来重新记录最小值的位置。然后，进入第二层循环，进行数值的比较，如果数组中的某个元素的值比最小值小，那么将当前的最小值设为元素的值，然后记录下来元素的位置，这样，当跳出循环体的时候，我们会得到要排序数组中的最小值，然后将最小值位置的数值设置为9999，即我们得到了最小值之后，就让数组中的这个数成为最大值，然后将结果数组result[]第主索引值位置上的元素赋值为最小值，进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于，我们挪动元素的次数很少，只是每次对要排序的数组进行整体遍历，找到其中的最小的元素，然后将改元素的值放到一个新的结果数组中去，这样大大减少了挪动的次序，即我们要排序的数组有多少元素，我们就挪动多少次，而因为每次都要对数组的所有元素进行遍历，那么比较的次数就比较多，达到了n2次，所以，我们使用选择排序的前提是，认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序，他的比较次数大于插入排序的次数，而挪动次数就很少，元素有多少个，挪动次数就是多少个。
希尔排序：首先，我们定义一个要排序的数组，然后定义一个步长的数组，该步长数组是由一组特定的数字组成的，步长数组具体得到过程我们不去考虑，是由科学家经过很长时间计算得到的，已经根据时间复杂度的要求，得到了最适合希尔排序的一组步长值以及计算
步长值的公式，我们这里直接拿来使用。然后根据要排序的数组的长度，选择比长度小的最大的步长值，作为我们开始的步长。然后，进入循环遍历，外层循环由步长值决定，直到步长为1时，我们就可以精确比较每一个数值，所以外层循环最终当步长为1时，我们就将得到排序后的结果。然后，进入内层循环，内层循环从步长那个位置开始遍历，先记录下步长值位置的数值，启动副索引j，然后比较步长值位置的元素的值与减去步长值位置元素的值，如果减去步长值处元素的值大于步长值位置的元素的值，那么，我们将减去步长值处的元素挪到步长值位置处，将副索引指向前一个步长值处然后再判断前一步长值与再前一步长值之间的大小关系，重复上面的工作；如果前一步长值处元素的数值不比步长值处元素的数值大，那么将刚才记录下的数值，放在目前j索引位置处。重复上面的步骤，直到遍历到我们的最后一个元素，然后将步长值减小到下一级步长。最终，当我们的步长值为1的遍历全部结束后，我们就得到了最终排序好的数组。希尔排序算法是初等排序算法向高等排序算法过度的一个中间排序算法，他的时间复杂度相比初等排序有很大的提升，达到了O(n^1.3)。而且希尔排序的稳定性也很好，如果给一个排好序的数组，希尔排序将会只进行数据的比较，不需要进行挪动，直接将结果返回，所以希尔排序在我们实际的应用当中还是比较值得推荐的。而且，科学家也已经为我们计算出了非常合适的步长值以及计算步长值的公式，我们直接可以使用，使得我们的算法开发也非常容易。
归并排序：首先，我们定义一个要排序的数组，得到数组的头下标top，得到数组的末尾下标bottom。然后，通过top和bottom得到数组的中间元素的下标middle，将数组人为的分成两半，即前半部分和后半部分。然后，递归调用算法，重复上面的过程，直到top=bottom，即分到前半部分和后半部分只剩下一个元素的时候，调用Merge函数，进行真正意义上的排序算法。然后，进入Merge函数：首先定义一个tempa的数组，用来临时存放要排序的数组，然后进入一个循环，当左面索引的值小于等于中间索引值，即当前半部分的数字还没有遍历完成，且当右面索引的值小于等于末尾索引值，即当后半部分也有数字没有遍历完成时，进行遍历，遍历时，判断左面索引处的数字的值的大小是否小于或等于右面索引位置数字的值，如果小于，那么，将左面索引位置的元素放进tempa数组中，将左索引加1继续判断是否进行再次遍历；否则，将右面索引位置的元素放进tempa数组中，将右索引加1继续判断是否进行再次遍历。直到这个循环结束。这时，我们将两个元素中，小的元素放在了tempa数组中，但是这时我们的左索引或是右索引可能还没有到达中间处或是末尾处，即还没有遍历完成所有的这两个元素，但是有一面（或是前半部分或是后半部分）已经遍历完成。那么我们需要判断这时的左索引是否小于或等于了中间值，如果是，那么将begin 赋值为做索引，end赋值为中间值；否则，将begin赋值为右索引，将end赋值为末尾值。然后将所有begin和end之间的数字追加到tempa中，这时，tempa中的所有元素都排序成功。最后，将tempa中的所有元素重新放回array数组中的相应位置。这次Merge排序就结束了，然后返回递归的调用处，进行下次的递归调用和Merge函数。重复上面所有的工作，最终我们可以得到排序成功的array数组。归并排序相比与初等排序，其优势在于，我们使用了分而治之（Divide-and-Conquer）的思想，将复杂的问题细化，先小方面进行排序，然后将排好序的元素合并在一起，再进行大方面的排序，这样就使我们的整体算法挪动次数变小，使整体的时间复杂度降低，优化了排序的次数。比起低等排序，如果要排序的数据量很大的时候，会明显体现出归并排序的优势。
快速排序：相比于归并排序，快速排序是归并排序的一个优化。它可以有效减少挪动的次数，因为它每次递归调用的时候，都是将第一个数字当做pivot，然后根据这个pivot，将数组分成比pivot大和比pivot小的两个部分，然后进入排序阶段，最后递归调用快速排序的算法，最终便得到了我们的排序结果。排序算法阶段：首先判断这次递归传进来的top值和bottom值，如果top值比bottom值大，或是相等，那么说明我们的递归已经到了最底层，
已经将前、后两个部分的元素分成了只剩下各一个元素，则我们将退出本次递归调用，返回到上次调用的地方向下执行；否则，进入排序阶段。首先，开启主索引i=top+1开始，到bottom 结束，如果我们的第i个元素比pivot大，那么就将其追加放入big数组中，否则，将其追加放入small数组中。循环结束后，我们开始将分好的两个数组分别返回到要排序的数组array的相应位置处，进行拼接。这里注意：在拼接的过程中，不要忘记为pivot预留中间一个位置，然后将pivot的值放到array中间的位置处。然后递归调用下次的快速排序函数。而再一次的调用会将上次调用函数的时候，得到的比pivot小的部分进行排序，同样使得第一个元素成为新的pivot，再次将数组分成大、小两个部分。继续上面同样的工作，我们最终会分成每个部分只有一个元素，这时再次调用排序后，就得到了排序完成的两个元素，然后经过不断的返回到递归调用，将会不断的使小半部分的数组慢慢排序成功，然后进行第二部分的排序。同理，当最终所有的递归调用都结束之后，我们会得到最终排序的结果。快速排序算法的优势在于，他同样也是分而治之（Divide-and-Conquer）的思想，巧妙之处在于，他每次分的时候已经实际意义上的将数组大小两个部分分好了，在递归回归的时候，相对拼接数组就十分简单。而归并排序在拼接数组的时候还需要将两部分数组进行比较，进行排序，这样使得我们挪动的次数就少了很多。但是，它也有不好用的时候，如果给你一个已经排好序的数组，那么它每次递归调用的时候，分开的两部分中，比pivot小的部分元素的个数为0，而比pivot大的部分元素的个数为当次调用递归传进来的数组长度减1的长度。所以需要的时间复杂度反而会增加。所以快速排序用在一个很随即的数组中时，一般会发挥比较好的性能。
二、算法流程图
1．下面给出插入排序的算法流程图：
图1 插入排序算法流程图
说明：图1是插入排序算法的流程图，体现了插入排序的整体算法核心思想。其中，我们通过判断insertIndex的值，来决定我们主索引遍历位置的元素是否需要向前面插入，并且插入的到要插入的位置。
图2选择排序算法流程图
说明：图2是选择排序算法的流程图，体现了选择排序的整体算法核心思想。其中，每次副循环我们都可以得到当前数组中的最小的元素的数值和位置，然后将每次得到最小的元素值追加到结果数组中，然后将最小元素的值赋值为最大值。
图3希尔排序算法流程图
说明：图3是希尔排序算法的流程图，体现了希尔排序的整体算法核心思想。其中，没有指明回到由k控制的主循环，当副循环遍历到数组的最后一个元素时，执行完后面的大的判断之后，会回去主循环，得到新的比上次循环小的步长值。
图4归并排序算法流程图
说明：图4是归并排序算法的流程图，体现了归并排序的整体算法核心思想。其中，有前半部分和后半部分两次递归调用，本图只体现了一次调用的核心思想，另一次调用的思想
与本图思想基本相同，且调用Merge算法函数是一样的，就没有过多赘述。、
图5快速排序算法流程图
说明：图5是快速排序算法的流程图，体现了快速排序的整体算法核心思想。其中，当
进入函数体之后，主要的拆分数组的工作是由top和bottom值来控制的，每次递归调用都
根据当时的top和bottom值来取得pivot值和分开大小两部分数组。
三、源代码
下面给出的是整个程序的源代码，五种排序算法写在了一个程序里面。其中，包括一个PrintArray的函数，用来打印整个数组，然后，除了一个主函数之外，还有其他的6个函数，分别是那5种排序算法，都有注释标示着。主函数中，外层循环一共执行四次，分别是让5种排序算法执行排序4组不同的数据。4组数据分别是：第一组为随机数组，第二组为正序排好的数组，第三组为倒序排好的数组，最后一组为前半部分为正序排好的数组，后半部分为倒序排好的数组。这样的选择有利于将所有的情况都能基本覆盖到，可以充分观察出每种排序算法的性能和稳定性。运行结果中会有分析说明。
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
int compareCount=0,moveCount=0;/*compareCount-记录比较次数，moveCount-用来记录挪动次数*/
void PrintArray(int array[],int length)/*打印数组的函数*/
{
int i=0;/*用来控制打印的循环变量*/
for(i=0;i { if(array[i]==9999 || array[i]==0)/*如果数组中的元素的值为9999或0*/ { printf("NN ");/*输出一个NN 标记*/ continue;/*不再向下判断*/ } if(array[i]<10)/*如果数组中数字为个位数*/ { printf("%d ",array[i]);/*打印出数字之后再加3个空格*/ } else if(array[i]<100)/*如果数组中的数字为两位数*/ { printf("%d ",array[i]);/*打印出数字之后再加2个空格*/ } else /*如果数字为三位数*/ { printf("%d ",array[i]);/*打印出数字之后再加1个空格*/ } } } void InsertSort(int array[],int length)/*插入排序*/ { int j=0,curr,currData,insertIndex;/*j-循环变量，curr当前的数组下表，currData-当前数组元素的数 值，insertIndex-要插入新元素的位置*/ for(curr=1;curr { insertIndex=-1;/*每次遍历向后移动时，都认为当前要插入的位置为-1，即不变*/ for(j=0;j 元素数值小*/ { if(array[j]>array[curr])/*如果副索引遍历到的元素的值比主索引位置元素的值大*/ { insertIndex=j;/*将要插入的位置记录为当前副索引的位置*/ compareCount++;/*增加一次比较的次数*/ break;/*副索引不再向后判断，因为主索引前面的所有元素都是已经排好序的*/ } compareCount++;/*增加一次比较的次数*/ } if(insertIndex==-1)/*如果要插入的位置为-1，说明主索引前面的元素没有比主索引位置元素值大的元素*/ { continue;/*主索引向后移动*/ } else { currData=array[curr];/*如果要插入的位置不为-1，说明要将主索引位置的元素向前插，那么先记录主索引位置元素的值*/ for(j=curr;j>=insertIndex+1;j--)/*启动循环，开始从主索引位置向前一个一个元素向后挪*/ { array[j]=array[j-1];/*前一元素挪到后一元素位置*/ moveCount++;/*增加挪动次数*/ } array[insertIndex]=currData;/*最终将主索引位置的元素插入到要插入的位置处*/ } } } void SelectionSort(int array[],int length)/*选择排序*/ { int result[100]={0};/*定义结果数组，用来存放最终排序完成的结果*/ int i=0,j=0,min,minIndex;/*i-主循环控制变量，j-副循环控制变量，min-记录最小值，minIndex-记录最小值的位置*/ for(i=0;i { min=9999;/*初始化的最小值为9999，即为最大值*/ minIndex=0;/*初始化的最小值的*/ for(j=0;j { if(array[j] { min=array[j];/*将最小值重新定位为新的最小值*/ minIndex=j;/*记录下来最小值的位置*/ } compareCount++; } array[minIndex]=9999;/*将最小值位置处设置为最大值。*/ result[i]=min;/*将最小值追加到结果数组中*/ moveCount++; } } void ShellSort(int array[],int length)/*希尔排序*/ { int gaps[]={1,5,13,43,113,297,815,1989};/*定义步长数组，步长数组是科学家为我们计算好的*/ int i,j,k;/*定义循环控制变量*/ int gap;/*定义单个步长值*/ int temp;/*定义临时使用的数值*/ for(k=0;gaps[k] while(--k>=0)/*通过下标来控制循环*/ { gap=gaps[k];/*得到步长值*/ for(i=gap;i { temp=array[i];/*首先记录下i处的元素值*/ j=i;/*启动副循环*/ while(j>=gap&&array[j-gap]>temp)/*如果j的值大于等于步长值且j前一步长值处的值比 j处的值大*/ { array[j]=array[j-gap];/*将j前一步长值处元素放到j处*/ j=j-gap;/*重新定向j*/ moveCount++; } array[j]=temp;/*将记录下来的temp值放在j处*/ compareCount++; } } } void Merge(int array[],int top,int middle,int bottom,int length)/*归并排序的排序算法*/ { int tempa[100]={0};/*定义一个tempa的数组，用来记录单次调用本函数时得到排序好的数组*/ int left=top;/*left-左半部分索引的位置*/ int right=middle+1;/*right-右半部分的位置*/ int tempIndex=0;/*控制tempa数组的下标*/ int begin=0,end=0;/*用来记录没有遍历到的数据的开始和结束位置*/ int i,j; while(left<=middle&&right<=bottom)/*遍历前后两个半部分*/ { if(array[left]<=array[right])/*如果前半部分的left处的值小于后半部分right处的值*/ { tempa[tempIndex]=array[left];/*将left处的元素追加到tempa数组中*/ left++;/*重定向left*/ } else { tempa[tempIndex]=array[right];/*否则，将right处的元素追加到tempa数组中*/ right++;/*重定向right*/ } tempIndex++;/*完成追加工作，将tempa下标向后移动*/ compareCount++; } begin=0;/*单次调用Merge的时候，将begin赋值为0*/ end=0; if(left<=middle)/*如果上半部分还没有遍历完元素*/ { begin=left;/*得到当前上半部分遍历到的元素的下标*/ end=middle;/*将中间值赋值给end*/ } else { begin=right;/*否则，得到下半部分遍历到的元素的下标*/ end=bottom;/*将末尾值赋值费end*/ } for(i=begin;i<=end;i++)/*从begin处开始遍历到end处*/ { tempa[tempIndex]=array[i];/*将主循环没有遍历到的元素依次追加到tempa中*/ tempIndex++; moveCount++; } for(i=top,j=0;i<=bottom;i++,j++)/*上面的工作全部结束后，将排好序的数组返回给array*/ { array[i]=tempa[j];/*相应array位置赋值为排好序的tempa位置的值*/ moveCount++; } } void MergeSort(int array[],int top,int bottom,int level,int length)/*归并排序*/ { if(top { int middle = (top+bottom)/2;/*得到中间值的下标，“一刀切”*/ MergeSort(array,top,middle,level+1,length);/*递归调用上半部分*/ MergeSort(array,middle+1,bottom,level+1,length);/*递归调用下半部分*/ Merge(array,top,middle,bottom,length);/*当递归回归后，调用排序*/ } } void QuickSort(int array[],int top,int bottom,int level,int length)/*快速排序*/ { int big[100]={0};/*定义一个比pivot大的数组*/ int small[100]={0};/*定义一个比pivot小的数组*/ int smallIndex=0,bigIndex=0;/*smallIndex-小数组的索引，bigIndex-大数组索引*/ int pivot=array[top];/*每次调用函数时，都将重新得到array数组第一个数做pivot*/ int i=0,arrayIndex=0; if(top>=bottom){return;}/*如果当前的top值大于bottom值的话，那么退出函数返回递归调用处*/ for(i=top+1;i<=bottom;i++)/*主循环从top+1处开始*/ { if(array[i]>=pivot)/*如果第i个元素的值大于pivot*/ { big[bigIndex]=array[i];/*将该元素追加到大元素数组中*/ bigIndex++;/*重定向大数组索引*/ } else { small[smallIndex]=array[i];/*否则，将该元素追加到小元素数组中*/ smallIndex++;/*重定向小数组索引*/ } compareCount++; } arrayIndex=0;/*每单次调用函数时，重新定位arrayIndex索引*/ for(i=0;i { array[arrayIndex+top]=small[i];/*往top处开始一个个的追加较小的数*/ arrayIndex++; moveCount++; } array[arrayIndex+top]=pivot;/*空出一位放pivot*/ arrayIndex++; for(i=0;i { array[arrayIndex+top]=big[i];/*将大的数字主键到当前array+top处*/ arrayIndex++; moveCount++; } QuickSort(array,top,top+smallIndex-1,level+1,length);/*递归调用快速排序*/ QuickSort(array,top+smallIndex+1,bottom,level+1,length); } void main() { int array_A[100],array_B[100],array_C[100],array_D[100],array_E[100];/*定义五个数组，用来分别让五个算法排序*/ int i,j;/*循环控制变量*/ for(j=0;j<4;j++)/*一共产生4组数据*/ { if(j==0)/*第一次进入循环，设置第一组数据*/ { srand((int)time(NULL));/*设置随即种子为当前时间值*/ for(i=0;i<100;i++) { array_A[i]=array_B[i]=array_C[i]=array_D[i]=array_E[i]=rand()%500+1;/*产生5组相同的，从1到500之间的随机数*/ } } if(j==1)/*第二次进入循环，设置第二组数据*/ { for(i=0;i<100;i++) { array_A[i]=array_B[i]=array_C[i]=array_D[i]=array_E[i]=i+1;/*产生5组相同的，从1到100正序排好的数组*/ } } if(j==2)/*第三次进入循环，设置第三组数据*/ { for(i=0;i<100;i++) { array_A[i]=array_B[i]=array_C[i]=array_D[i]=array_E[i]=100-i;/*产生5组相同的，从 100到1倒序排好的数组*/ } } if(j==3)/*第四次进入循环，设置第四组数据*/ { for(i=0;i<50;i++) { array_A[i]=array_B[i]=array_C[i]=array_D[i]=array_E[i]=2*(i+1);/*数组下标0到49 的数为正序排好的2到100的偶数*/ } for(i=99;i>=50;i--) { array_A[i]=array_B[i]=array_C[i]=array_D[i]=array_E[i]=-(2*i-200+1);/*数组下标50 到99的数为倒序排好的99到1的奇数*/ } } PrintArray(array_A,100);/*排序前先打印出整个数组*/ compareCount=0,moveCount=0;/*重新定向比较次数和移动次数*/ InsertSort(array_A,100);/*调用插入排序，排序对象：array_A*/ printf("InsertSort :Compare Count:%d \t Move Count:%d \n",compareCount,moveCount);/*输出比较次数和移动次数*/ compareCount=0,moveCount=0;/*重新定向比较次数和移动次数*/ SelectionSort(array_B,100);/*调用选择排序，排序对象：array_B*/ printf("SelectSort :Compare Count:%d Move Count:%d \n",compareCount,moveCount); compareCount=0,moveCount=0;/*重新定向比较次数和移动次数*/ ShellSort(array_C,100);/*调用希尔排序，排序对象：array_C*/ printf("ShellSort :Compare Count:%d \t Move Count:%d \n",compareCount,moveCount); compareCount=0,moveCount=0;/*重新定向比较次数和移动次数*/ MergeSort(array_D,0,99,0,100);/*调用归并排序，排序对象：array_D*/ printf("MergeSort :Compare Count:%d \t Move Count:%d \n",compareCount,moveCount); compareCount=0,moveCount=0;/*重新定向比较次数和移动次数*/ QuickSort(array_E,0,99,0,100);/*调用快速排序，排序对象：array_E*/ printf("QuickSort :Compare Count:%d \t Move Count:%d \n",compareCount,moveCount); } getch(); } 四、运行结果 下面给出程序运行的结果图： 图6五种排序算法的运行结果图 说明：本运行图是整个程序运行的结果，其中并没有将排序好的数组输出出来，因为5种排序算法都将一个数组排序成一样的结果，所以打印结果相对不那么重要。而主要是打印出了每种算法对不同数组的排序所需要的比较次数和移动次数。 分析：插入排序：插入排序时初等排序的一种，所以其时间复杂度相对较大，随机100个数据的数组，用了2648次比较和2396次移动，总数达到了5044，因为其时间复杂度为O(n*(n-1)/2)，所以其结果大致如此；后面排正序排好的数组时，主要是一步一步的比较，相当于比较次数为(∑(1 to 99)n=4950)；排倒序排好的数组时，每次和最前面的数比较之后就可以将主索引处的元素插入到前面，所以比较次数为99次，而移动次数又是(∑(1 to 99)n=4950)。最后，一半正序一半倒序的数组时，就各取一半，各是2500次。 选择排序：因为选择排序每次都是双重循环完全遍历数组，所以其比较次数为(n^2=10000)，而如果我们将赋值到新的结果数组中算作挪动的话，那么就是只有(n=100)次挪动。 希尔排序：希尔排序相对就比较稳定，他每次排序使用的比较次数都是相同的，都为338而挪动次数相对不是固定的，其平均复杂度为(n^1.3=398)，排序正序排好的数组时，希尔排序只需要进行几次比较，不需要进行任何的挪动就原样将数组返回了。说明其稳定性还是比较不错的。 归并排序：归并排序这里，我将一次赋值看作是一次挪动。归并排序采用的是“一刀切”的办法，所以其比较次数相对固定，每次递归的时候，都将数组切成两半，直到切到不能再切得时候，进行比较，用的是分而治之（Divide-and-Conquer）的思想。而赋值次数就比较多了，因为采用了递归的方法，每次都将数组分为两部分的时候，都需要不断的追加到临时 数组tempa中，然后再返回到array数组的相应位置，所以需要来回赋值。 快速排序：快速排序相对就比较不稳定了，因为我们人为的将每次递归进来的top值处的元素设为我们的pivot，在完全随机的数组中，他的表现还是比较出色的，比较次数为615，快速排序这里，每次比较之后，得到了小的和大的数组之后，会返回到array里面，所以比较的次数和返回的次数是相同的。而当我们给快速排序一个已经排好序的数组，或是正序，或是倒序，他每次比较的时候都会将除了第一个元素之外的其余元素放在一个部分里面，所以需要不断的递归来拆分数组。所以执行的次数比较多，达到了4950次。 五、遇到的问题及解决 这部分我主要遇到了如下三个问题，其内容与解决方法如下所列： ●插入排序时，结果中出现了一串相同的数字 在编写插入排序的时候，在运行时遇到了错误的结果，结果数组当中，时常会出现一连串数字相同的结果，但是整体的结果又是从小到大排列的。分析问题，出现了逻辑错误，但是因为整体的运行结果是从小到大排列的，则说明我的程序的整体的判断环节没有出现问题，而可能是在循环的控制上出现了问题，然后通过仔细阅读代码，发现了错误的所在，在最后，判断出了要插入的位置（insertIndex）不为-1时，要进行元素的挪动，由主索引处的前一个元素开始，依次将元素向后挪动一位，应该是挪动到要插入的位置之后的那个元素时停止挪动，“for(j=curr;j>=insertIndex+1;j--)”，将记录下来的主索引的值插入到要插入的位置处。而我的循环控制是让元素挪动，从主索引处之前的元素开始，到了要插入的位置之前的那个元素位置，“for(j=curr;j>=insertIndex-1;j--)”，所以多挪动了两个元素，导致了错误的产生。产生错误的原因是，自己写循环的时候，大部分时间写的是增量为正值的循环，而本循环式增量为-1的情况，所以写的比较少，在写的时候没有判断正确循环的次数，导致了错误的产生。 ●快速排序中对pivot值的放置 在编写快速排序的时候，一开始自己并没有真正理解快速排序的算法思想，只凭着自己对归并算法的理解，认为快速排序与归并排序基本相似，就开始了编写代码，但是后来编写完成后，运行时，总是不能得到自己想要的结果，而且结果很乱，通过详细读自己的代码，发现到了问题的所在，主要是自己没有给pivot空出一位，而直接将大数组放在了小数组的后面，所以最后老是少一个pivot的值，而且最终的结果最后面出现了很乱的数字。通过修改，将pivot的位置预留出来，每次将小数组放回相应位置后，将pivot 值插入相应位置后，再将大数组追加到后面，这样就没有遗忘掉pivot值，可以得到正确的结果。 ●归并排序的设计 在设计归并排序的时候，因为用到了递归，在设计初期，并没有很好的掌握其排序的流程，按照老师给的例子，大致写了出来，并没有很好的理解，递归调用处总是分不太清。 介于自己C语言水平有限，对递归函数调用并不是太熟，所以我使用了VC++的编译软件，使用其调试的功能，一步一步的观察并分析了其递归调用的过程，然后才掌握了归并排序的整体排序过程。也为自己在后面设计快速排序的算法时，打下了很好的基础，也使自己对递归调用的思想有了进一步的体会。 六、心得体会 通过学习通用排序算法的内容，我得到了很多的体会。我体会到，排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，通过对多种排序算法的学习，不单单是学到了用代码来实现排序的功能，而且掌握了多种排序算法的原理。能够比较深刻得 理解算法复杂度对性能的影响。如果自己今后从事软件开发的话，那么这些理念对我来说是非常有用的，如果你写了一个应用程序，用户执行一下需要很长时间，那么你做出来的产品不会得到别人的认可，也不会有很好的市场。而通过分析和比较了多种排序算法的性能，得到了很多启发，对性能优化方面的概念也有了初步的建立，也让我养成了一个很好的习惯，在设计算法的时候，都会尽量寻求最为高效的解法，不仅对自己有了很好的锻炼，也为工程项目带来了很大的好处，可以处理更加复杂的情况。不仅提升了自己的认识水平，也增强了自己分析问题、解决问题的能力，使自己在学业生涯中有了更好的进步。 排序算法 一、插入排序(Insertion Sort) 1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】： [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想： 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 《几种排序算法的分析》 摘要: 排序算法是在C++中经常要用到的一种重要的算法。如何进行排序，特别是高效率的排序是是计算机应用中的一个重要课题。同一个问题可以构造不同的算法，最终选择哪一个好呢？这涉及如何评价一个算法好坏的问题，算法分析就是评估算法所消耗资源的方法。可以对同一问题的不同算法的代价加以比较，也可以由算法设计者根据算法分析判断一种算法在实现时是否会遇到资源限制的问题。排序的目的之一就是方便数据的查找。在实际生活中，应根据具体情况悬着适当的算法。一般的，对于反复使用的程序，应选取时间短的算法；对于涉及数据量较大，存储空间较小的情况则应选取节约存储空间的算法。本论文重点讨论时间复杂度。时间复杂度就是一个算法所消耗的时间。算法的效率指的是最坏情况下的算法效率。 排序分为内部排序和外部排序。本课程结业论文就内部排序算法（插入排序，选择排序，交换排序，归并排序和基数排序）的基本思想，排序步骤和实现算法等进行介绍。 本论文以较为详细的文字说明，表格对比，例子阐述等方面加以比较和总结，通过在参加数据的规模，记录说带的信息量大小，对排序稳定的要求，关键字的分布情况以及算法的时间复杂度和空间复杂度等方面进行比较，得出它们的优缺点和不足，从而加深了对它们的认识和了解，进而使自己在以后的学习和应用中能够更好的运用。 1.五种排序算法的实例： 1.1.插入排序 1.1.1.直接插入排序 思路：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。 要点：设立哨兵，作为临时存储和判断数组边界之用。 实现： Void InsertSort(Node L[],int length) { Int i,j;//分别为有序区和无序区指针 for(i=1;i C语言几种常见的排序方法 2009-04-2219:55 插入排序是这样实现的： 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。 从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。 重复2号步骤，直至原数列为空。 插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。 冒泡排序 冒泡排序是这样实现的： 首先将所有待排序的数字放入工作列表中。 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 重复2号步骤，直至再也不能交换。 冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。 选择排序 选择排序是这样实现的： 设数组内存放了n个待排数字，数组下标从1开始，到n结束。 i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。 将上一步找到的最小元素和第i位元素交换。 如果i=n－1算法结束，否则回到第3步 选择排序的平均时间复杂度也是O(n²)的。 快速排序 现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。 堆排序 堆排序与前面的算法都不同，它是这样的： 首先新建一个空列表，作用与插入排序中的"有序列表"相同。 找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。 重复2号步骤，直至原数列为空。 堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。 各种排序算法的总结和比较 1 快速排序（QuickSort） 快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 （1）如果不多于1个数据，直接返回。 （2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 （4）对两边利用递归排序数列。 快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。 2 归并排序（MergeSort） 归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。 3 堆排序（HeapSort） 堆排序适合于数据量非常大的场合（百万数据）。 堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。 堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。 Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。 Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。 5 插入排序（InsertSort） 插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。 常见内部排序算法比较 排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作： InitList(n) 操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d,isInverseOrser) 操作结果：随机打乱 BubbleSort( ) 操作结果：进行起泡排序 InserSort( ) 操作结果：进行插入排序 SelectSort( ) 操作结果：进行选择排序 QuickSort( ) 操作结果：进行快速排序 HeapSort( ) 操作结果：进行堆排序 ListTraverse(visit( )) 操作结果：依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析. 详细设计 1、起泡排序 算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。 bubblesort(struct rec r[],int n) { int i,j; struct rec w; unsigned long int compare=0,move=0; for(i=1;i<=n-1;i++) for(j=n;j>=i+1;j--) { if(r[j].key 实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较（验证型实验） 实验目标： （1）几种排序算法在平均情况下哪一个更快。 （2）加深对时间复杂度概念的理解。 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。 （2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于围（0，105）的整数。 对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： (1)明确实验目标和具体任务； (2)理解实验所涉及的几个分类算法； (3)编写程序实现上述分类算法； (4)设计实验数据并运行程序、记录运行的结果； (5)根据实验数据及其结果得出结论； (6)实验后的心得体会。 问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）： 选择排序：令A[1…n]为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序， 即对啊[A…n]排序。对某个j,1<=j<=n,设A[j]是最小值。首先，如果就！=1，我们交换A[1] 和A[j]。然后由假设，已知如何对A[2..n]排序，因此可对在A[2…n]中的元素递归地排序。 可把递归改为迭代。算法程序实现如下： void SelectionSort(int *Array,int n,int &c) { int i,j,k; int aa; c=0; for(i=0;i C语言9种常用排序法 1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序 8.带哨兵的直接插入排序 9.基数排序 例子：乱序输入n个数，输出从小到大排序后的结果1.冒泡排序 #include for(i=0;i int i, j, n, a[100], t, temp; while(scanf("%d",&n)!=EOF) { for(i=0;i 五种排序算法的分析与比较 广东医学院医学信息专业郭慧玲 摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。 关键词：冒泡排序;选择排序;插入排序;归并排序;快速排序。 排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1]，排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2，3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中，存在前后相同的两个元素，排序前和排序后他们的相对位臵不发生变化。 1 算法与特性 1.1冒泡排序 1.1.1冒泡排序的基本思想 冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至ｎ-1个记录和第ｎ个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。 1.1.2冒泡排序的特性 容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过ｎ-1次比较,不需要移动关键字,即时间复杂度为Ｏ(ｎ)(即正序);在最坏情况下是初始序列为逆序,则需要进行ｎ-1次排序,需进行ｎ(ｎ-1)/2次比较,因此在最坏情况下时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。 1.2选择排序 1.2.1选择排序的基本思想 选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是ｎ个记录的文件的直接排序可经过ｎ-1次直接选择排序得到有序结果。 1.2.2选择排序的特性 容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(ｎ-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为ｎ(ｎ-1)/2,时间 一、设计思想 插入排序：首先，我们定义我们需要排序的数组，得到数组的长度。如果数组只有一个数字，那么我们直接认为它已经是排好序的，就不需要再进行调整，直接就得到了我们的结果。否则，我们从数组中的第二个元素开始遍历。然后，启动主索引，我们用curr当做我们遍历的主索引，每次主索引的开始，我们都使得要插入的位置（insertIndex）等于-1，即我们认为主索引之前的元素没有比主索引指向的元素值大的元素，那么自然主索引位置的元素不需要挪动位置。然后，开始副索引，副索引遍历所有主索引之前的排好的元素，当发现主索引之前的某个元素比主索引指向的元素的值大时，我们就将要插入的位置（insertIndex）记为第一个比主索引指向元素的位置，跳出副索引；否则，等待副索引自然完成。副索引遍历结束后，我们判断当前要插入的位置（insertIndex）是否等于-1，如果等于-1，说明主索引之前元素的值没有一个比主索引指向的元素的值大，那么主索引位置的元素不要挪动位置，回到主索引，主索引向后走一位，进行下一次主索引的遍历；否则，说明主索引之前insertIndex位置元素的值比主索引指向的元素的值大，那么，我们记录当前主索引指向的元素的值，然后将主索引之前从insertIndex位置开始的所有元素依次向后挪一位，这里注意，要从后向前一位一位挪，否则，会使得数组成为一串相同的数字。最后，将记录下的当前索引指向的元素的值放在要插入的位置（insertIndex）处，进行下一次主索引的遍历。继续上面的工作，最终我们就可以得到我们的排序结果。插入排序的特点在于，我们每次遍历，主索引之前的元素都是已经排好序的，我们找到比主索引指向元素的值大的第一个元素的位置，然后将主索引指向位置的元素插入到该位置，将该位置之后一直到主索引位置的元素依次向后挪动。这样的方法，使得挪动的次数相对较多，如果对于排序数据量较大，挪动成本较高的情况时，这种排序算法显然成本较高，时间复杂度相对较差，是初等通用排序算法中的一种。 选择排序：选择排序相对插入排序，是插入排序的一个优化，优化的前提是我们认为数据是比较大的，挪动数据的代价比数据比较的代价大很多，所以我们选择排序是追求少挪动，以比较次数换取挪动次数。首先，我们定义我们需要排序的数组，得到数组的长度，定义一个结果数组，用来存放排好序的数组，定义一个最小值，定义一个最小值的位置。然后，进入我们的遍历，每次进入遍历的时候我们都使得当前的最小值为9999，即认为每次最小值都是最大的数，用来进行和其他元素比较得到最小值，每次认为最小值的位置都是0，用来重新记录最小值的位置。然后，进入第二层循环，进行数值的比较，如果数组中的某个元素的值比最小值小，那么将当前的最小值设为元素的值，然后记录下来元素的位置，这样，当跳出循环体的时候，我们会得到要排序数组中的最小值，然后将最小值位置的数值设置为9999，即我们得到了最小值之后，就让数组中的这个数成为最大值，然后将结果数组result[]第主索引值位置上的元素赋值为最小值，进行下一次外层循环重复上面的工作。最终我们就得到了排好序的结果数组result[]。选择排序的优势在于，我们挪动元素的次数很少，只是每次对要排序的数组进行整体遍历，找到其中的最小的元素，然后将改元素的值放到一个新的结果数组中去，这样大大减少了挪动的次序，即我们要排序的数组有多少元素，我们就挪动多少次，而因为每次都要对数组的所有元素进行遍历，那么比较的次数就比较多，达到了n2次，所以，我们使用选择排序的前提是，认为挪动元素要比比较元素的成本高出很多的时候。他相对与插入排序，他的比较次数大于插入排序的次数，而挪动次数就很少，元素有多少个，挪动次数就是多少个。 希尔排序：首先，我们定义一个要排序的数组，然后定义一个步长的数组，该步长数组是由一组特定的数字组成的，步长数组具体得到过程我们不去考虑，是由科学家经过很长时间计算得到的，已经根据时间复杂度的要求，得到了最适合希尔排序的一组步长值以及计算 数据结构各种排序方法的综合比较 结论: 排序方法平均时间最坏时间辅助存储 简单排序O(n2) O(n2) O(1) 快速排序O(nlogn)O(n2)O(logn) 堆排序O(nlogn)O(nlogn)O(1) 归并排序O(nlogn)O(nlogn)O(n) 基数排序O(d(n+rd))O(d(n+rd))O(rd) PS:直接插入排序、冒泡排序为简单排序，希尔排序、堆排序、快速排序为不稳定排序 一、时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为 最好，特别是对那些对关键字近似有序的记录序列尤为如此； 时间复杂度为O(n)的排序方法只有，基数排序。 当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 二、空间性能 指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为栈所需的辅助空间; 3. 归并排序所需辅助空间最多，其空间复杂度为O(n ); 4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd)。 三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。 3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 4. 快速排序和堆排序是不稳定的排序方法 数据结构各种排序算法的时间性能. HUNAN UNIVERSITY 课程实习报告 题目：排序算法的时间性能 学生姓名 学生学号 专业班级 指导老师李晓鸿完成日期 设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象） 要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力，包括：数据要有一定的规模（如元素个数从100到10000）；数据的初始特性类型要多，因而需要具有随机性；实验数据的组数要多，即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清晰的形式给出，如图、表等。 (3)算法所用时间必须是机器时间，也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清晰的方式来描述，如数学公式或图表等。 (5)要给出实验的方案及其分析。 说明 本题重点在以下几个方面： 理解和掌握以实验方式比较算法性能的方法；掌握测试实验方案的设计；理解并实现测试数据的产生方法；掌握实验数据的分析和结论提炼；实验结果汇报等。 一、需求分析 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比 较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。 用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时间和 比较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机 数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据：略 //插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; i //堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j 常用排序算法比较与分析 一、常用排序算法简述 下面主要从排序算法的基本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性和速度等方面进行分析比较。依据待排序的问题大小(记录数量 n)的不同，排序过程中需要的存储器空间也不同，由此将排序算法分为两大类：【排序】、【外排序】。 排序：指排序时数据元素全部存放在计算机的随机存储器RAM中。 外排序：待排序记录的数量很大，以致存一次不能容纳全部记录，在排序过程中还需要对外存进行访问的排序过程。 先了解一下常见排序算法的分类关系(见图1-1) 图1-1 常见排序算法 二、排序相关算法 2.1 插入排序 核心思想：将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数据元素依然有序，直到待排序数据元素全部插入完为止。 2.1.1 直接插入排序 核心思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2 、i-3、… 数据元素的值进行顺序比较，通过这种线性搜索的方法找到第i个数据元素的插入位置，并且原来位置的数据元素顺序后移，直到全部排好顺序。 直接插入排序中，关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶O(n2)，空间复杂度为常数阶O(l)。 Python源代码： 1.#-------------------------直接插入排序-------------------------------- 2.def insert_sort(data_list): 3.#遍历数组中的所有元素，其中0号索引元素默认已排序，因此从1开始 4.for x in range(1, len(data_list)): 5.#将该元素与已排序好的前序数组依次比较，如果该元素小，则交换 6.#range(x-1,-1,-1):从x-1倒序循环到0 7.for i in range(x-1, -1, -1): 8.#判断：如果符合条件则交换 9.if data_list[i] > data_list[i+1]: 10.temp= data_list[i+1] 11.data_list[i+1] = data_list[i] 12.data_list[i] = temp 2.1.2 希尔排序 核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 希尔排序时间复杂度会比O(n2)好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。 Python源代码： 1.#-------------------------希尔排序------------------------------- 2.def insert_shell(data_list): 3.#初始化step值，此处利用序列长度的一半为其赋值 4.group= int(len(data_list)/2) 5.#第一层循环：依次改变group值对列表进行分组 6.while group> 0: 7.#下面：利用直接插入排序的思想对分组数据进行排序 8.#range(group,len(data_list)):从group开始 9.for i in range(group, len(data_list)): 10.#range(x-group,-1,-group):从x-group开始与选定元素开始倒序比较，每个比较元素之间间隔group 11.for j in range(i-group, -1, -group): 12.#如果该组当中两个元素满足交换条件，则进行交换 13.if data_list[j] > data_list[j+group]: 14.temp= data_list[j+group] 15.data_list[j+group] = data_list[j] 16.data_list[j] = temp 17.#while循环条件折半 18.group= int(group/ 2) 2.2 选择排序 基于C语言地多种排序方法地实现 1 引言 1.1 课题背景 排序问题源远流长，一直是数学地重要组成部分.随着各种信息地快速更新，排序问题也走进了其他领域以及我们地日常生活.如何高效地排序一直困扰着我们. 1.2 课程设计目地 排序是数学地重要组成部分，工作量大是其存在地问题.如何高效地排序？本程序就是解决这个问题而设计.程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题.本软件开发地平台为最新地微软公司出版地市面最新系统Windows 2000，而且可以作为自身地运行平台非常广泛，包括 Windows 98/2000/XP/Vista等等. 1.3课程设计内容 本程序把对数列地排序转化为对数组元素地排序，用户可以根据自己地实际问题选择系统提供地七种排序方法地任意一种进行排序.程序通过自身地判断以及处理实现排序.程序最后输出每趟排序及初始排序结果. 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能： 1) 显示需要输入地排序长度及其各个关键字 2) 初始化输入地排序序列 3) 显示可供选择地操作菜单 4) 显示输出操作后地移动次数和比较次数 5) 显示操作后地新序列 5) 可实现循环继续操 2.2 设计思路 通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入地元素进行相应地处理. [2] 2.3 设计方案 设计方案如图2.1所示 图2.1 设计方案 具体流程见图2.2 图 2.2 程序流程图 3功能设计 3.1 SqList顺序表 其中包括顺序表长度，以及顺序表.源代码如下：[1] typedef struct { KeyType key。 //关键字项 InfoType otherinfo。 //其他数据项 }RedType。 typedef struct { RedType r[MaxSize+1]。 //r[0]作为监视哨 int length。 //顺序表长度 }SqList。 3.2 直接插入排序 直接插入排序是将一个记录插入到已排好序地有序表中，从而得到一个新地、记录数增1地有序表 图3.1 直接插入排序示意图 将第i个记录地关键字r[i].key顺序地与前面记录地关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key地记录依次后移一位，直到关键字小于或者等于r[i].key地记录 各种排序法的比较 按平均时间将排序分为四类： （1）平方阶(O(n2))排序 一般称为简单排序，例如直接插入、直接选择和冒泡排序； （2）线性对数阶(O(nlgn))排序 如快速、堆和归并排序； （3）O(n1+￡)阶排序 ￡是介于0和1之间的常数，即0<￡<1，如希尔排序； （4）线性阶(O(n))排序 如桶、箱和基数排序。 各种排序方法比较： 简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。 影响排序效果的因素： 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法 应综合考虑下列因素： ①待排序的记录数目n； ②记录的大小(规模)； ③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构； ⑦时间和辅助空间复杂度等。 不同条件下，排序方法的选择 (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并排序。从单个记录起进行两两归并，排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。 几种常见的排序算法之比较 2010-06-20 14:04 数据结构课程 摘要： 排序的基本概念以及其算法的种类，介绍几种常见的排序算法的算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度，然后以表格的形式，清晰直观的表现出它们的复杂度的不同。在研究学习了之前几种排序算法的基础上，讨论发现一种新的排序算法，并通过了进一步的探索，找到了新的排序算法较之前几种算法的优势与不足。 关键词：排序算法复杂度创新算法 一、引言 排序算法，是计算机编程中的一个常见问题。在日常的数据处理中，面对纷繁的数据，我们也许有成百上千种要求，因此只有当数据经过恰当的排序后，才能更符合用户的要求。因此，在过去的数十载里，程序员们为我们留下了几种经典的排序算法，他们都是智慧的结晶。本文将带领读者探索这些有趣的排序算法，其中包括介绍排序算法的某些基本概念以及几种常见算法，分析这些算法的时间复杂度，同时在最后将介绍我们独创的一种排序方法，以供读者参考评判。 二、几种常见算法的介绍及复杂度分析 1.基本概念 1.1稳定排序(stable sort)和非稳定排序 稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 1.2内排序( internal sorting )和外排序( external sorting) 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 /* ===================================================================== ======== 相关知识介绍（所有定义只为帮助读者理解相关概念，并非严格定义）： 1、稳定排序和非稳定排序 简单地说就是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，我们就 说这种排序方法是稳定的。反之，就是非稳定的。 比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为 a1,a2,a4,a3,a5， 则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4, a2,a3,a5就不是稳定的了。 2、内排序和外排序 在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序； 在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 3、算法的时间复杂度和空间复杂度 所谓算法的时间复杂度，是指执行算法所需要的计算工作量。 一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 ===================================================================== =========== */ /* ================================================ 功能：选择排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述： c排序算法大全 排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。 对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。我将按照算法的复杂度，从简单到难来分析算法。第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。现在，让我们开始吧： 一、简单排序算法 由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。 1.冒泡法： 这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡： #include 各种排序算法比较
几种排序算法分析
C语言几种常见的排序方法
各种排序算法的总结和比较
几种常见内部排序算法比较
几种排序算法的平均性能比较(实验报告)
C语言9种常用排序法
五种排序算法的分析与比较
几种排序算法的分析与比较--C语言
数据结构各种排序方法的综合比较
数据结构各种排序算法的时
数据结构经典算法 C语言版
常用排序算法比较与分析报告
基于C语言的多种排序方法的实现
各种排序法比较
数据结构中几种常见的排序算法之比较
C语言常用排序算法
c排序算法大全
相关文档
- 排序算法效率分析及总结
- 几种常见内部排序算法比较
- 几种排序算法的平均性能比较(实验报告)
- 算法分析与复杂性理论 实验报告 几个排序的对比
- 算法分析作业1_简单排序算法分析讲述
- 数据结构中几种常见的排序算法之比较
- 常用排序算法比较与分析
- 各种常用排序算法的分析与比较
- 几种排序算法的平均性能比较(实验报告)
- 10.1几种基本排序算法的实现
- 各种算法的性能分析
- 几种排序算法的平均性能比较(实验报告)
- 几种排序算法的分析与比较--C语言
- C语言中三种常见排序算法分析
- 五种排序算法分析课件
- 几种排序算法分析
- 数据结构课程设计报告---几种排序算法的演示(附源代码)
- 算法分析与复杂性理论实验报告几个排序的对比课件
- 7种排序算法总结
- 五种排序算法的分析与比较