搜索
1、冒泡排序(BubbleSort)对于一个已经排序好的序列，它的任意两个相邻元素，都应该满足a[i-1]=a[i]的关系。冒泡排序相当暴力的实现了这一目标：不断扫描相邻元素，看它们是否违章。一旦违章，立即纠正。在冒泡排序时，计算机从右向左遍历数组，比较相邻的两个元素。如果两个元素的顺序是错的，那么sorry，请两位互换。如果两个元素的顺序是正确的，则不做交换。经过一次遍历，我们可以保证最小的元素(泡泡)处于最左边的位置。然而，经过这么一趟，冒泡排序不能保证所有的元素已经按照次序排列好。我们需要再次从右向左遍历数组元素，进行冒泡排序。这一次遍历，我们不用考虑最左端的元素，因为该元素已经是最小的。遍历结束后，继续重复扫描……总共可能进行n-1次的遍历。如果某次遍历过程中，没有发生交换，bingo，这个数组已经排序好，可以中止排序。如果起始时，最大的元素位于最左边，那么冒泡算法必须经过n-1次遍历才能将数组排列好，而不能提前完成排序。/*ByVamei*//*swaptheneighborsifoutoforder*/voidbubble_sort(inta[],intac){/*useswap*/inti,j;intsign;for(j=0;jac-1;j++){sign=0;for(i=ac-1;ij;i--){if(a[i-1]a[i]){sign=1;swap(a+i,a+i-1);}}if(sign==0)break;}}2、插入排序(InsertionSort)假设在新生报到的时候，我们将新生按照身高排好队(也就是排序)。如果这时有一名学生加入，我们将该名学生加入到队尾。如果这名学生比前面的学生低，那么就让该学生和前面的学生交换位置。这名学生最终会换到应在的位置。这就是插入排序的基本原理。对于起始数组来说，我们认为最初，有一名学生，也就是最左边的元素(i=0)，构成一个有序的队伍。随后有第二个学生(i=1)加入队伍，第二名学生交换到应在的位置；随后第三个学生加入队伍，第三名学生交换到应在的位置……当n个学生都加入队伍时，我们的排序就完成了。/*ByVamei*//*insertthenextelementintothesortedpart*/voidinsert_sort(inta[],intac){/*useswap*/inti,j;for(j=1;jac;j++){i=j-1;while((i=0)&&(a[i+1]a[i])){swap(a+i+1,a+i);i--;}}}3、选择排序(SelectionSort)排序的最终结果：任何一个元素都不大于位于它右边的元素(a[i]=a[j],ifi=j)。所以，在有序序列中，最小的元素排在最左的位置，第二小的元素排在i=1的位置……最大的元素排在最后。选择排序是先找到起始数组中最小的元素，将它交换到i=0；然后寻找剩下元素中最小的元素，将它交换到i=1的位置……直到找到第二大的元素，将它交换到n-2的位置。这时，整个数组的排序完成。/*ByVamei*//*findthesmallestoftherest,thenappendtothesortedpart*/voidselect_sort(inta[],intac){/*useswap*/inti,j;intmin_idx;for(j=0;jac-1;j++){min_idx=j;for(i=j+1;iac;i++){if(a[i]a[min_idx]){min_idx=i;}}swap(a+j,a+min_idx);}}4、希尔排序（ShellSort）我们在冒泡排序中提到，最坏的情况发生在大的元素位于数组的起始。这些位于数组起始的大元素需要多次遍历，才能交换到队尾。这样的元素被称为乌龟(turtle)。乌龟元素的原因在于，冒泡排序总是相邻的两个元素比较并交换。所以每次从右向左遍历，大元素只能向右移动一位。(小的元素位于队尾，被称为兔子(rabbit)元素，它们可以很快的交换到队首。)希尔排序是以更大的间隔来比较和交换元素，这样，大的元素在交换的时候，可以向右移动不止一个位置，从而更快的移动乌龟元素。比如，可以将数组分为4个子数组（i=4k,i=4k+1,i=4k+2,i=4k+3），对每个子数组进行冒泡排序。比如子数组i=0，4，8，12...。此时，每次交换的间隔为4。完成对四个子数组的排序后，数组的顺序并不一定能排列好。希尔排序会不断减小间隔，重新形成子数组，并对子数组冒泡排序……当间隔减小为1时，就相当于对整个数组进行了一次冒泡排序。随后，数组的顺序就排列好了。希尔排序不止可以配合冒泡排序，还可以配合其他的排序方法完成。/*ByVamei*//*quicklysorttheturtlesatthetailofthearray*/voidshell_sort(inta[],intac){intstep;inti,j;intnsub;int*sub;/*initializestep*/step=1;while(stepac)step=3*step+1;/*whenstepbecomes1,it'sequivalenttothebubblesort*/while(step1){/*stepwillgodownto1atmost*/step=step/3+1;for(i=0;istep;i++){/*pickanelementeverystep,andcombineintoasub-array*/nsub=(ac-i-1)/step+1;sub=(int*)malloc(sizeof(int)*nsub);for(j=0;jnsub;j++){sub[j]=a[i+j*step];}/*sortthesub-arraybybubblesorting.Itcouldbeothersortingmethods*/bubble_sort(sub,nsub);/*putbackthesub-array*/for(j=0;jnsub;j++){a[i+j*step]=sub[j];}/*freesub-array*/free(sub);}}}ShellSorting依赖于间隔(step)的选取。一个常见的选择是将本次间隔设置为上次间隔的1/1.3。见参考书籍。5、归并排序(MergeSort)如果我们要将一副扑克按照数字大小排序。此前已经有两个人分别将其中的一半排好顺序。那么我们可以将这两堆扑克向上放好，假设小的牌在上面。此时，我们将看到牌堆中最上的两张牌。我们取两张牌中小的那张取出放在手中。两个牌堆中又是两张牌暴露在最上面，继续取小的那张放在手中……直到所有的牌都放入手中，那么整副牌就排好顺序了。这就是归并排序。下面的实现中，使用递归：/*ByVamei*//*recursivelymergetwosortedarrays*/voidmerge_sort(int*a,intac){inti,j,k;intac1,ac2;int*ah1,*ah2;int*container;/*basecase*/if(ac=1)return;/*splitthearrayintotwo*/ac1=ac/2;ac2=ac-ac1;ah1=a+0;ah2=a+ac1;/*recursion*/merge_sort(ah1,ac1);merge_sort(ah2,ac2);/*merge*/i=0;j=0;k=0;container=(int*)malloc(sizeof(int)*ac);while(iac1&&jac2){if(ah1[i]=ah2[j]){container[k++]=ah1[i++];}else{container[k++]=ah2[j++];}}while(iac1){container[k++]=ah1[i++];}while(jac2){container[k++]=ah2[j++];}/*copybackthesortedarray*/for(i=0;iac;i++){a[i]=container[i];}/*freespace*/free(container);}6、快速排序(QuickSort)我们依然考虑按照身高给学生排序。在快速排序中，我们随便挑出一个学生，以该学生的身高为参考(pivot)。然后让比该学生低的站在该学生的右边，剩下的站在该学生的左边。很明显，所有的学生被分成了两组。该学生右边的学生的身高都大于该学生左边的学生的身高。我们继续，在低身高学生组随便挑出一个学生，将低身高组的学生分为两组(很低和不那么低)。同样，将高学生组也分为两组(不那么高和很高)。如此继续细分，直到分组中只有一个学生。当所有的分组中都只有一个学生时，则排序完成。在下面的实现中，使用递归:/*ByVamei*//*selectpivot,putelements(=pivot)totheleft*/voidquick_sort(inta[],intac){/*useswap*//*pivotisaposition,alltheelementsbeforepivotissmallerorequaltopvalue*/intpivot;/*thepositionoftheelementtobetestedagainstpivot*/intsample;/*selectapvalue.Medianissupposedtobeagoodchoice,butthatwillitselftaketime.here,thepvalueisselectedinaverysimplewayi:a[ac/2]*//*storepvalueata[0]*/swap(a+0,a+ac/2);pivot=1;/*testeachelement*/for(sample=1;sampleac;sample++){if(a[sample]a[0]){swap(a+pivot,a+sample);pivot++;}}/*swapanelement(which=pvalue)witha[0]*/swap(a+0,a+pivot-1);/*basecase,ifonlytwoelementsareinthearray,theabovepasshasalreadysortedthearray*/if(ac=2)return;else{/*recursion*/quick_sort(a,pivot);quick_sort(a+pivot,ac-pivot);}}理想的pivot是采用分组元素中的中位数。然而寻找中位数的算法需要另行实现。也可以随机选取元素作为pivot，随机选取也需要另行实现。为了简便，我每次都采用中间位置的元素作为pivot。7、堆排序(HeapSort)堆(heap)是常见的数据结构。它是一个有优先级的队列。最常见的堆的实现是一个有限定操作的CompleteBinaryTree。这个CompleteBinaryTree保持堆的特性，也就是父节点(parent)大于子节点(children)。因此，堆的根节点是所有堆元素中最小的。堆定义有插入节点和删除根节点操作，这两个操作都保持堆的特性。我们可以将无序数组构成一个堆，然后不断取出根节点，最终构成一个有序数组。堆的更详细描述请阅读参考书目。下面是堆的数据结构，以及插入节点和删除根节点操作。你可以很方便的构建堆，并取出根节点，构成有序数组。/*ByVameiUseanbigarraytoimplementheapDECLARE:intheap[MAXSIZE]incallingfunctionheap[0]:totalnodesintheheapforanodei,itschildrenarei*2andi*2+1(ifexists)itsparentisi/2*/voidinsert(intnew,intheap[]){int