C语言算法——排序算法

1、冒泡排序

#include <stdio.h>int main ( ){//冒泡排序int a[]={3,2,6,4,8,9,1,0,3,5,7,1};int len=sizeof(a)/sizeof(int);//求出数组中元素的个数// printf("%d\n",len);int i=0,j;for (; i<len-1; i++) {//n个元素进行冒泡排序需要进行n-1次循环for (j=0; j<len-1-i; j++) {//每次循环完一次，最大的数就在最后，所以每进行一次循环后面的那几个数就不需要参与循环，所以i<len-i-1if (a[j]>a[j+1]) {//实现元素的交换int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}for (i=0; i<len; i++) {printf("%d ",a[i]);}printf("\n");}

2、插入排序

默认数组中的第一个数是原本数组中排好序的第一个数，然后每次将排好序的数组的后面的第一个数作为哨兵。每次哨兵都和前面的排好序的数组中的数从后往前进行比较，然后将哨兵插入到已经排好序的数组中。然后哨兵逐渐往后移动，逐步将哨兵插入到数组中，这就是插入排序的整体思路和步骤。

#include <stdio.h>int main(){int arr[6]={4,6,1,2,8,7};int n = sizeof(arr)/sizeof(int); //求出数组的长度int i,j,k;for (i=1; i<n; i++) {k = arr[i]; //哨兵,从数组中的第二个元素开始进行存储，每一次往后移动一位进行储存，将这个数插入到前面已经排好序的数组中。j=i-1; //已经排好序的数组的最后一个元素的下标。while(j>=0 && k<arr[j]){//每次哨兵和前面排好序的数组中的元素从后往前进行比较，找到哨兵要插入的位置。arr[j+1]=arr[j]; //为哨兵腾出位置，以便于将哨兵插入数组中合适的位置。j--; //用j记录最终哨兵要插入的位置。}arr[j+1] = k; //将哨兵插入到数组合适的位置（形成一个新的排好序的数组）}for (i=0; i<n; i++) {printf("%d ",arr[i]);}printf("\n");}

3、选择排序

说明：动图来自与此链接，点击我直接进入，感谢博主的分享

说明：动图来自与此链接，点击我直接进入，感谢博主的分享

思路：

每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。

实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。

方案一：只找最小的值，将最小的值往前移

#include <stdio.h>int main(){int a[]={2,9,5,0,1,3,6,8};int n = sizeof(a)/sizeof(int);//求出数组a的长度// printf("%d\n",n);int begin=0,end=n-1;while (begin<end) {int min=a[begin];//min用于存储数组中元素的最小的值int t=begin;//t表示的是数组中最小数的下标for(int i=begin ; i<end;i++){if (min>a[i]) {min=a[i];t = i;}}a[t]=a[begin];a[begin] = min;begin++;}int i = 0;for (; i<n; i++) {printf("%d ",a[i]);}printf("\n");}

方案二：找最小值和最大值，最小值往前移，最大值往后移

#include <stdio.h>int main(){// 思路：// 每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。// 实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。int a[]={2,9,5,0,1,3,6,8};int n = sizeof(a)/sizeof(int);//求出数组a的长度// printf("%d\n",n);int begin=0,end=n-1;//begin表示数组的第一个元素，end表示数组的最后一个元素。int x=0,y=0; //x,y分别记录数组中最大值、最小值的数的下标。while(begin<end){int min = a[begin],max = a[begin];//先将数组中的第一个元素作为最大值和最小值（因为我们也不知道最大值最小值在哪）//使用for循环遍历数组，每一找到数组中的最大值和最小值赋值给max和min。int i=begin;for (; i<=end; i++) {if (a[i]>max) {max=a[i];x=i; //记录所查找范围内最大数的下标}if (a[i]<min) {min=a[i];y=i; //记录所查找范围内最小数的下标}}//将数组中最大数的下标和end下标的数值进行交换a[x]=a[end];a[end] = max;//将数组中最小数的下标和begin下标的数值进行交换a[y]=a[begin];a[begin] = min;//此时最左边和最右边已经存储了最小值和最大值，所以begin要往后移动，end要往前移动，在这个新的begin和end的范围内再进行选择排序++begin;end--;}int i=0;for (i=0; i<n; i++) {printf("%d ",a[i]);}printf("\n");}