白话经典算法系列(冒泡、直接插入、希尔排序、直接选择、归并排序、快速排序、堆与堆排序)-----标题

白话经典算法系列（转载）原文作者：MoreWindows目录白话经典算法系列（转载）...........................................................................................................1白话经典算法系列之一冒泡排序的三种实现.....................................................................2白话经典算法系列之二直接插入排序的三种实现.............................................................4白话经典算法系列之三希尔排序的实现.............................................................................6白话经典算法系列之四直接选择排序及交换二个数据的正确实现.................................9白话经典算法系列之五归并排序的实现...........................................................................11白话经典算法系列之六快速排序快速搞定.....................................................................15白话经典算法系列之七堆与堆排序...................................................................................19二叉堆的定义.................................................................................................................19堆的存储.........................................................................................................................19堆的操作——插入删除.................................................................................................20堆的插入.........................................................................................................................21堆的删除.........................................................................................................................21堆化数组.........................................................................................................................22堆排序.............................................................................................................................24转载请标明出处，原文地址：白话经典算法系列之一冒泡排序的三种实现冒泡排序是非常容易理解和实现，以从小到大排序举例：设数组长度为N。1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。3．N=N-1，如果N不为0就重复前面二步，否则排序完成。按照定义很容易写出代码：//冒泡排序1voidBubbleSort1(inta[],intn){inti,j;for(i=0;in;i++)for(j=1;jn-i;j++)if(a[j-1]a[j])Swap(a[j-1],a[j]);}下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。//冒泡排序2voidBubbleSort2(inta[],intn){intj,k;boolflag;k=n;flag=true;while(flag){flag=false;for(j=1;jk;j++)if(a[j-1]a[j]){Swap(a[j-1],a[j]);flag=true;}k--;}}再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。//冒泡排序3voidBubbleSort3(inta[],intn){intj,k;intflag;flag=n;while(flag0){k=flag;flag=0;for(j=1;jk;j++)if(a[j-1]a[j]){Swap(a[j-1],a[j]);flag=j;}}}冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。白话经典算法系列之二直接插入排序的三种实现直接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。设数组为a[0…n-1]。1.初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=12.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。3.i++并重复第二步直到i==n-1。排序完成。下面给出严格按照定义书写的代码（由小到大排序）：voidInsertsort1(inta[],intn){inti,j,k;for(i=1;in;i++){//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置for(j=i-1;j=0;j--)if(a[j]a[i])break;//如找到了一个合适的位置if(j!=i-1){//将比a[i]大的数据向后移inttemp=a[i];for(k=i-1;kj;k--)a[k+1]=a[k];//将a[i]放到正确位置上a[k+1]=temp;}}}这样的代码太长了，不够清晰。现在进行一下改写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i]a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]a[i]时停止并将temp放到a[j+1]处。voidInsertsort2(inta[],intn){inti,j;for(i=1;in;i++)if(a[i]a[i-1]){inttemp=a[i];for(j=i-1;j=0&&a[j]temp;j--)a[j+1]=a[j];a[j+1]=temp;}}再对将a[j]插入到前面a[0…j-1]的有序区间所用的方法进行改写，用数据交换代替数据后移。如果a[j]前一个数据a[j-1]a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1]=a[j]。这样也可以实现将一个新数据新并入到有序区间。voidInsertsort3(inta[],intn){inti,j;for(i=1;in;i++)for(j=i-1;j=0&&a[j]a[j+1];j--)Swap(a[j],a[j+1]);}白话经典算法系列之三希尔排序的实现希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。以n=10的一个数组49,38,65,97,26,13,27,49,55,4为例第一次gap=10/2=549386597261327495541A1B2A2B3A3B4A4B5A5B1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素，每次对同一组的数据进行直接插入排序。即分成了五组(49,13)(38,27)(65,49)(97,55)(26,4)这样每组排序后就变成了(13,49)(27,38)(49,65)(55,97)(4,26)，下同。第二次gap=5/2=2排序后13274955449386597261A1B1C1D1E2A2B2C2D2E第三次gap=2/2=142613273849495597651A1B1C1D1E1F1G1H1I1J第四次gap=1/2=0排序完成得到数组：4132627384949556597下面给出严格按照定义来写的希尔排序voidshellsort1(inta[],intn){inti,j,gap;for(gap=n/2;gap0;gap/=2)//步长for(i=0;igap;i++)//按组排序{for(j=i+gap;jn;j+=gap){if(a[j]a[j-gap]){inttemp=a[j];intk=j-gap;while(k=0&&a[k]temp){a[k+gap]=a[k];k-=gap;}a[k+gap]=temp;}}}}很明显，上面的shellsort1代码虽然对直观的理解希尔排序有帮助，但代码量太大了，不够简洁清晰。因此进行下改进和优化，以第二次排序为例，原来是每次从1A到1E，从2A到2E，可以改成从1B开始，先和1A比较，然后取2B与2A比较，再取1C与前面自己组内的数据比较…….。这种每次从数组第gap个元素开始，每个元素与自己组内的数据进行直接插入排序显然也是正确的。voidshellsort2(inta[],intn){intj,gap;for(gap=n/2;gap0;gap/=2)for(j=gap;jn;j++)//从数组第gap个元素开始if(a[j]a[j-gap])//每个元素与自己组内的数据进行直接插入排序{inttemp=a[j];intk=j-gap;while(k=0&&a[k]temp){a[k+gap]=a[k];k-=gap;}a[k+gap]=temp;}}再将直接插入排序部分用白话经典算法系列之二直接插入排序的三种实现中直接插入排序的第三种方法来改写下：voidshellsort3(inta[],intn){inti,j,gap;for(gap=n/2;gap0;gap/=2)for(i=gap;in;i++)for(j=i-gap;j=0&&