C语言选择排序算法

选择排序是排序算法的一种，这里以从小到人排序为例进行讲解。基本思想及举例说明（了解）选择排序（从小到人）的基本思想是，首先，选出最小的数，放在第一个位置：然后，选出第二小的数，放在第二个位置；以此类推，直到所有的数从小到大排序。（不稳定的算法）在实现上，我们通常是先确定第i小的数所在的位置，然后，将其与第i个数进行交换。卜•面，以对3241进行选择排序说明排序过程，使用minjndex记录当前最小的数所在的位置。第1轮排序过程（寻找第1小的数所在的位置）3241(最初，min_index=1)3241(3>2,所以min_index=2)3241(2<4,所以min_index=2)3241(2>1,所以min_index=4,这时候确定了第1小的数在位置4）1243（第1轮结果，将3和1交换，也就是位置1和位置4交换）第2轮排序过程（寻找第2小的数所在的位置）1243（第4轮结果，minjndex=2,只需要从位置2开始寻找）243(4>2,所以min」ndex=2)243(3>2,所以minjndex=2)1243（第2轮结果，因为minjndex位置刚好在第2个位置，无需交换）第3轮排序过程（寻找第3小的数所在的位置）1243（第2轮结果，minjndex=3,只需要从位置2开始寻找）1243（4>3,所以minjndex=4）1234（第3轮结果，将3和4交换，也就是位置4和位置3交换）至此，排序完毕。总结及实现选择排序对大小为N的无序数组R[N]进行排序，进行N-1轮选择过程。第i轮选取第i小的数，并将其放在第i个位置上。当第N-1次完成时，第N小（也就是最人）的数自然在最后的位置上。卜面给出选择排序的C语言实现。#include<stdio.h>#include<stdlib.h>#defineN8voidselect_sort(inta[],intn);〃实现数组选择排序的子程序〃选择排序实现voidselect_sort(inta[],intn)//n为数组a的元素个数{〃进行N-1轮选择for(inti=0;i<n-l;i++){intmin_index=i;〃找出第i小的数所在的位置for(intj=i+l;j<n;j++){if(a[j]<a[minjndex]){minjndex=j;}}〃将第i小的数，放在第i个位置：如果刚好，就不用交换if(i!=minjndex){inttemp=a[i];a[i]=a[min_index];a[min」ndex]=temp;}}}intmain(){intnum[N]={89,3&11,78,96,44,19,25};select_sort(num,N);for(inti=0;i<N;i++)printf("%d",num[i]);printf(W);第一轮，逐个比较（第一轮，逐个比较（R[1],R[2]）, （R[2],R⑶），（R[3],R[4]）,....... （R[N-1],R[N]）;最systemCpause"）；return0;}注意：选择排序是一种不稳定的排序算法，可能会打乱两个相同数字的原有顺序。例如，序列58529,按照从小到大排序，第一轮会将第1个数字5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序是一种不稳定的排序算法冒泡排序是排序算法的一种，思路清晰，代码简洁，常被用在人学生计算机课程中。“冒泡”这个名字的由来是因为越人的元素会经由交换慢慢"浮"到数列的顶端，故名。这里以从小到大排序为例进行讲解。基本思想及举例说明冒泡排序的基本思想就是不断比较相邻的两个数，让较人的元素不断地往后移。经过一轮比较，就选出最人的数：经过第2轮比较，就选出次人的数，以此类推。（步骤较多，繁琐）下面以对3241进行冒泡排序说明。第一轮排序过程3241（最初）2342 （比较3和2,交换）2341 （比较3和4,不交换）2314（比较4和1,交换）第一轮结束，最人的数4已经在最后面，因此第二轮排序只需要对前面三个数进行再比较。第二轮排序过程2314（第一轮排序结果）2314（比较2和3,不交换）2134（比较3和1,交换第二轮结束，第二大的数已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。第三轮排序过程21341234（第二轮排序结果）（比较2和1,交换）至此，排序结束。算法总结及实现对于具有N个元素的数组R[n],进行最多N-1轮比较；人的元素会被移动到R[N]上。第二轮,逐个比较(R[1LR[2]), (R[2LR[3]), (R[3],R[4J) (R[N-2],R[N-1])：第二大元素会被移动到R[N-l]±o以此类推，直到整个数组从小到人排序。卜•面给出了冒泡排序的一般实现和优化实现。一般实现是教科书里常见的实现方法，无论数组是否排序好了，都会进行N-1轮比较：而优化实现，在数组已经排序好的情况下，会提前退出比较，减小了算法的时间复杂度。#include<stdio.h>#include<stdlib.h>#defineN8voidbubble_sort(inta[],intn);〃一般实现voidbubble_sort(inta[]Jntn)//n为数组a的元素个数{〃一定进行N-l轮比较for(inti=0;i<n-l;i++){〃每一轮比较前n-l-i个，即已排序好的最后i个不用比较for(intj=0;j<n-l-i;j++){if(a[j]>a[j+l]){inttemp=a[j];a[j]=a[j+l];a[j+l]=temp;}}}}〃优化实现voidbubble_sort_better(inta[],intn)//n为数组a的元素个数{〃最多进行N-l轮比较for(inti=0;i<n-l;i++)boolisSorted=true;〃每一轮比较前n-l-i个，即已排序好的最后i个不用比较for(intj=0;j<n-l-i;j++)if(a[j]>a[j+l]){isSorted=false;inttemp=a[j];a[j]=a[j+l];a[j+l]=temp;}}if(isSorted)break;//如果没有发生交换，说明数组已经排序好了}}intmain(){intnum[N]={89,3&11,78,96,44,19,25};bubble_sort(num,N);〃或者使用bubble_sort_better(num,N);for(inti=0;i<N;i++)printf("%d",num[i]);printfCV);systemCpause")；return0;}插入排序是排序算法的一种，它不改变原有的序列(数组)，而是创建一个新的序列，在新序列上进行操作。这里以从小到大排序为例进行讲解。基本思想及举例说明插入排序的基本思想是，将元素逐个添加到己经排序好的数组中去，同时要求，插入的元素必须在正确的位置，这样原来排序好的数组是仍然有序的。在实际使用中，通常是排序整个无序数组，所以把这个无序数组分为两部分排序好的子数组和待插入的元素。第一轮时，将第一个元素作为排序好的子数组，插入第二个元素：第二轮，将前两个元素作为排序好的数组，插入第三个元素。以此类推，第i轮排序时，在前i个元素的子数组中插入第i+1个元素。直到所有元素都加入排序好数组。卜面，以对3241进行选择排序说明插入过程，使用j记录元素需要插入的位置。排序目标是使数组从小到大排列。第1轮[3][241]（最初状态，将第1个元素分为排序好的子数组，其余为待插入元素）[3][241]（由于3>2,所以待插入位置j=1）[23][41]（将2插入到位置j）第2轮[23][41]（第4轮排序结果）[23][41]（由于2<4,所以先假定j=2）[23][41]（由于3<4,所以戸3）[234][1]（由于4刚好在位置3,无需插入）第3轮[234][1]（第2轮排序结果）[234][1]（由于1<2,所以jh）[1234]（将1插入位置j,待排序元素为空，排序结束）算法总结及实现选择排序对大小为N的无序数组R[N]进行排序，进行NJ轮选择过程。首先将第1个元素作为已经排序好的子数组，然后将剩余的N-1个元素，逐个插入到已经排序好子数组；。因此，在第i轮排序时，前i个元素总是有序的，将第i+1个元素插入到正确的位置。include<stdio.h>include<stdlib.h>#defineN8voidinsert_sort（inta[],intn）;〃插入排序实现,这里按从小到大排序voidinsert_sort（inta[],intn）//n为数组a的元素个数{〃进行N-1轮插入过程for（inti=l;i<n;i++）〃首先找到元素a[i]需要插入的位置intj=0;while((a[j]<a[i])&&(j<i)){j++；〃将元素插入到正确的位置if(i!=j)〃如果i==j，说明a[i]刚好在正确的位置{inttemp=a[i];for(intk=i;k>j;k・・){a[k]=a[k-l];}a[j]=temp;}}}intmain(){intnum[N]={89,3&11,78,96,44,19,25};insert_sort(num,N);for(inti=0;i<N;i++)printf("%d",num[i]);printf("\n")；systemCpause")；return0;}注意：插入排序是一种稳定的排序算法，不会改变原有序列中相同数字的顺序。插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它人则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。快速排序是对冒泡法排序的一种改进。快速排序算法的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直到所有要进行排序的数据变为有序为止。可能仅根据基本思想对快速排序的认识并不深，接卞来以对n个无序数列A[O],A[l]...zA[n-l]采用快速排序方法进行升序排列为例进行讲解。⑴定义两个变量low和high,将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1,接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。定义一个变量key,接下来以key的取值为基准将数组A划分为左右两个部分，通常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0],以后毎次取值由要划分序列的起始元素决定。从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不人于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。如果low依然小于high,那么由low所指向的数组元素开始向右扫描，扫描的同时将卞标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个人于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。重复步骤(3)(4),直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low......pos-1]和A[pos+1......high],其中，pos下标所对应的数组元素的值就是进行划分的基准值key,所以在划分结束时还要将下标为pos的数组元素赋值为key。将划分得到的左右两部分A[low......pos・l]和A[pos+1......high]继续采用以上操作步骤进行划分，直到得到有序序列为止。为了能够加深读者的理解，接卞来通过一段代码来了解快速排序的具体实现方法。//include<stdio.h>#include<stdlib.h>//defineN6intpartition(intarr[]zintlow,inthigh){intkey;key=arr[low];while(low<high){while(low<high&&arr[high]>=key)high-;if(low<high)arr[low++]=arr[high];while(low<high&&arr[low]<=key)low++;if(low<high)arr[high-]=arr[low];}arr[low]=key;returnlow;}voidquick_sort(intarr[],intstart,intend){intpos;if(start<end){pos=partition(arr;start,end);quick_sort(arGStart,pos-l);quick_sort(arGpos+l,end);}return;}intmain(void){inti;intair[N]二{32)277&23,45};printf(“排序前\n“);for(i=0;i<N;i++)printf("%d\t",arr[i]);quick_sort(arr,0,N-l);printf("\n排序后\nH)；for(i=0;i<N;i++)printf("%d\t",arr[i]);printf(”\n“)；systemCpause'1)；return0;}运行结果：排序前32 12 7 78 23 45排序后7 12 23 32 45 78在上面的代码中，根据前面介绍的步骤一步步实现了快速排序算法。接下来通过示意图来演示第一次划分操作。在第一次划分操作中，先进行初始设置，key的值是进行划分的基准，其值为要划分数组的第一个元素值，在上面的排序序列中为第一个元素值32,同时将low设置为要排序数组中第一个元素的下标，第一次排序操作时其值为0,将high设置为要排序序列最后一个元素的下标，在上面的排序序列中其第一次取值为5。先将下标为high的数组元素与key进行比较，由于该元素值人于key,因此high向左移动一个位置继续扫描。由于接下来的值为23,小于key的值，因此将23赋值给下标为low所指向的数组元素。接卞来将low右移一个位置，将low所指向的数组元素的值与key进行比较，由干接下来的12、7都小于key,因此low继续右移扫描，直至下标low所指向的数组元素的值为78即人于key为止，将78赋值给下标为high所指向的数组元素，同时将high左移一个位置。接下来由于low不再小于high,划分结束。需要注意的是，在进行划分的过程中，都是将扫描的值与key的值进行对比，如果小于key,那么将该值赋值给数组中的另外一个元素，而该元素的值并没有改变。从图中可以看出这一点，所以需要在划分的最后将作为划分基准的key值赋值给下标为pos的数组元素，这个元素不再参与接下来的划分操作。初始设置 key二32SH□HHHtlow初始设置 key二32SH□HHHtlowlow highlow highlow向右柯描 f|~23^pT|p~~|pzT||~23-|pT|t tlosv highlow向右柯描 f|~23^pT|p~~|pzT||~23-|pT|个tlowhigh第2次交换操作后f叵|叵|□叵|叵|叵|第一轮划分结束后，得到了左右两部分序列A[0]、A⑴、A[2]和A[4]、A[5],继续进行划分,即对毎轮划分后得到的两部分序列继续划分，直至得到有序序列为止。归并排序也称合并排序，其算法思想是将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并。仅从算法思想上了解归并排序会觉得很抽象，接下来就以对序列A[0],A[l]...,A[n-1]进行升序排列来进行讲解，在此采用自顶向下的实现方法，操作步骤如下。⑴将所要进行的排序序列分为左右两个部分，如果要进行排序的序列的起始元素下标为first,最后一个元素的卞标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first...mid]和A[mid+1...Iast]o⑵将上面所分得的两部分序列继续按照步骤⑴继续进行划分，直到划分的区间长度为lo(3)将划分结束后的序列进行归并排序，排序方法为对所分的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元素的子序列，再对得到的子序列进行合并，直至得到一个长度为n的有序序列为止。下面通过一段代码来看如何实现归并排序。#include<stdio.h>#include<stdlib.h>#defineN7voidmerge(intarr[]zintlow,intmid,inthigh){int\,k;int*tmp=(int*)malloc((high-low+l)*sizeof(int));〃申请空间，使其大小为两个intleft_low=low;intleft_high=mid;intrightjow=mid+1;intright_high=high;for(k=0;left_low<=left_high&&right_low<=right_high;k++){//比较两个指针所指向的元素if(arr[leftjow]<=arr[rightjow]){tmp[k]=arr[left_low++);}else{tmp[k]=arr[rightJow++];}}if(left_low<=left_high){〃若第一个序列有剩余，直接复制出来粘到合并序列尾//memcpy(tmp+k,arr+left」ow,(left_high-leftJow+l)*sizeof(int));for(i=left_low;i<=left_high;i++)tmp[k++]=arr[i];}if(right_low<=right_high){〃若第二个序列有剩余，直接复制出来粘到合并序列尾//memcpy(tmp+k,arr+rightjow,(right_high-right_low+l)*sizeof(int));for(i=rightjow;i<=right_high;i++)tmp[k++]=arr[i];}for(i=0;i<high-low+l;i++)arr[low+i]=tmp[i];free(tmp);return;}voidmerge_sort(intarr[],unsignedintfirst,unsignedintlast){intmid=0;if(first<last){mid=(first+last)/2;/*注意防止溢出*//*mid=first/2+last/2;*///mid=(first&last)+((firstAlast)»1);merge_sort(arr;first,mid);merge_sort(arr;mid+ljast);merge(arr/first/mid,last);}return;}intmain(){inti;inta[N卜{32)2,5678,76,45,36};printf(“排序前\n")；for(i=0;i<N;i++)printf(”％d\t",a[i]);merge_sort(a,OzN-l);//排序printf("\n排序后\n")；for(i=0;i<N;i++)printf(”％d\t",a[i]);printf("\n");system("pause")；return0;}运行结果：排序前32 12 56 78 76 45 36排序后12 32 36 45 56 76 78分析上面的运行结果，通过归并排序成功地实现了对给定序列的排序操作。接卞来通过图11-9来了解归并排序的具体操作流程。在图11-9中，先对所要进行排序的序列进行分解，直到分为单个元素为止，然后将其进行两两合并。由于最终分解成单个元素，因此在合并的时候•将小数放在前面，大数放在后面，得到一个有序序列。接下来对两个相连的有序序列进行排序，先比较有序序列中的第一个元素，将较小的元素放入临时数组中，接着将较小元素所在数组的卞一个元素与另一个数组中的较小元素比较，同样将较小元素放入临时数组中，依次进行，直到两个数组的所有元素都放入临时数组中，最后再将临时数组的元素放入原始数组中的对应位置。

最终分解形式第一轮合并第二轮合并第三轮合并最终分解形式第一轮合并第二轮合并第三轮合并顺序査找是一种简单的査找算法，其实现方法是从序列的起始元素开始，逐个将序列中的元素与所要查找的元素进行比较，如果序列中有元素与所要查找的元素相等，那么査找成功,如果査找到序列的最后一个元素都不存在一个元素与所要査找的元素值相等，那么表明査找失败。接下来通过一段代码来了解顺序査找的具体使用。#include<stdio.h>#include<stdlib.h>#inelude<memory.h>intordersearch(inta[]zintn,intdes){inti;for(i=0;i<n;i++)if(des==a[i])return1;return0;}intmain(){inti,val;inta[8]={32,12,56,78,76,45,43,98};intret;for(i=0;i<8;i++)printf(ll%d\t,,/a[i]);printffV请输入所要查找的元素：“);while(l){scanfC^d1；&val);fflush(stdin);ret=ordersearch(a,8,val);if(l==ret)printfC查找成功！”)；elseprintf(”查找失败!•')；printf(“\n请输入所要查找的元素：")；}return0;}运行结果：32 12 56 78 76 45 43 98请输出所要查找的元素：78查找成功！请输出所要查找的元素：5查找失败！分析上面的运行结果，首先输入所要查找的元素为7&该数在所要查找的序列中是存在的，所以打印输出