前言：

本篇文章是在数组的框架之下，主要分享三种数组的排序方式（选择排序、冒泡排序、插入排序）以及一种查找方法（二分查找法）。

---------------------------------------------------------------------------------------------------------------------------------

在C语言的排序中，默认升序（即从小到大）。 

一、数组排序

（一）、选择排序

1、思想

给合适的地方，选择合适的数。

步骤： 

先假定数组中的第一个数是最小的，

拿剩下的数依次与第一个数比较，如果比第一个数小，则和第一个数交换位置，这样一趟下来，第一个位置的数就是最小的

同理，确定第二个位置的数，第三个位置的数……到第n-1位置的数。

这样数组中的数就成功以升序的方式排列了。

2、代码实现

既然我们已经理清楚了选择排序的思路，接下来我们用代码实现它。^_^

int a[n];                         //定义数组a,n代表数组长度即数组元素个数      
int min ;                    
int i=0；                       //初始化 i；

for(i=0;i<n-1;++i)             // 外层循环选位置
{                             

  int j=0;                       //初始化j 
  int  temp;                            

  for(j=i+1;j<n;++j)           //内层循环选合适的数                          
  if（a[i]>a[j])
  {
   temp=a[i];
   a[i]=a[j];
   a[j]=temp;                   //交换两个位置的数值
   }
 }
 for(i=0;i<n;++i)
   {
     printf("d% ",a[i]);          //输出数组
}

其中i<n-1的原因:

当比到倒数第二个位置时，最后一个位置的数也被确定，因此只需要遍历到倒数第二个数即可

j<n的原因 ：

选择第一个位置放什么数时，需要遍历到最后一个数，一共需要比较n-1次，所以j<n

（二）、冒泡排序

1、思想

一次冒出一个数，相邻两个数比较，小的放前面，大的放后面

分析第一趟的过程，其余趟数循环第一次的过程：

1. 比较：与前面的数（a[0]）相比较   ------------------ a[j]与a[j+1] 
2. 交换： 如果前面的数比后面的数大（a[0]>a[1]），把a[0]与 a[1]位置互换

注意：外层循环控制的是趟数，内层循环控制的是比较的次数（n-1）次

-----------------------------------------------------------------------------------------------------------------------

2、用代码实现

既然上面理清楚了冒泡排序的过程，接下来我们就用代码实现它

  	int i=0；
    for(i=n-1;i>0;--i)                       //外层循环控制趟数
	{
        int j=0;
        int temp=0;    
		for(j=0;j<i;++j)                         //内层循环控制次数
		{
			if(a[j]>a[j+1])                       //相邻两个数比较
			{
				temp=a[j];                        
				a[j]=a[j+1];                      
				a[j+1]=temp;                       //交换数
			}
		}
	}
	for(i=0;i<n;++i)
	{
		printf("%d ",a[i]);                       //输出数组
	}
	putchar('\n');                                   //输出换行符

注意：

趟数和交换的次数都是 n-1 ；

（三）、插入排序

1、思想

 在有序的数列中，找到合适的位置插入数

即先排序，然后把待插入的值放在最前面

一共有四个步骤： 拿   比   挪   放

定义两个数组，int a[n]; int b[n];(a数组是待排序数组；

b数组是空数组，被用来存储排序后的结果。虽然初始时b数组的元素都是0，但随着插入排序算法的执行，这些元素会逐步被替换为数组a中的元素，从而实现升序排序。

1. 拿 ： 先按顺序从a[]中拿出来一个数a[i]放入 变量t 中；
2. 比 ： 比较a[i] 与b[j-1]
3. 挪 ：如果a[i]>b[j-1]; b[j]=b[j-1] ; b[j-1]向后挪一个，同时--j; 
4. 放 ： 把a[i]放入b[j]中；         

注意：

1. j 的初始值是根据当前待插入的元素 a[i] 的位置来确定的，即 j = i。这样可以确保在每一轮插入排序中，j 都指向当前待插入元素的位置。

2. j>0;保证不超出数组下限；

3. 循环条件（j>0 && t<b[j-1]）-----插入的值比前一个数小；

------------------------------------------------------------------------------------------------------------------

2、代码实现

既然我们已经清楚了插入排序的过程及其细节，接下来我们就用代码实现它

//非原地插入（用两个数组）
#include<stdio.h>
int main(void)
{
   int a[10]={1,2,3,4,5,6,7,8,9,10};
   int b[10]={0};
for(i=0;i<10;++i)
{
   int t,i,j;
    j=i;
    t= a[i];
   while(j>0&&t<b[j-1])
  {
            b[j]=b[j-1];
             --j;
         }  
      b[j]=t;
  }
}
for(i>0;i<10;++i)
 {
  printf("%d",b[i]);
 }
 printf('\n');

}

// 原地插入（仅用一个数组）
//只写核心代码部分
for(i=0;i<n;++i)
{ 
  int i,j;
  int t=a[i];
    j=i;
while（j>0&&t<a[j-1]）
 {
            a[j]=a[j-1];
            --j;  
}
      
        a[j]=t;

}

(四)查找算法

1、思想

1. 找到中间位置的数；
2. 拿中间位置的数和要找到数比较；
3. 每次折一半，直到找到对应的数，查找结束；

2、前提

数组必须是有序数组

接下来让我们写代码吧~

 #include<stdio.h>                                                                                                                                                                
  2 int main(void)
  3 {
  4 
  5     int a[]={1,2,3,4,5,6,7,8,9};
  6     int mid;         //下标值
  7     int m;                 //要查找的数
  8     int len=sizeof(a)/sizeof(0);  //数组长度
  9     int begin=0;                  //开始下标
 10     int end=len-1;                 //结束下标
 11     scanf("%d",&m);               //输入要查找的数
 12 
 13     while(begin <= end)
 14     {
 15         mid=(begin+end)/2;
 16         if(m<a[mid])  
 17         {
 18             end=mid-1;
 19         }
 20         if(m>a[mid])
 21         {
 22             begin=mid+1;
 23         }else
 24         {
 25             break;                              //循环结束有两种条件
 26         } 
 27     }
 28     if(begin<=end)
 29     {
 30         printf("Found it!\n");                  //第一种mid=m此时begin<=end
 31     }else
 32     {
 33         printf("Can't found it!\n");      //第二种，begin>end 证明找遍整个数组都没找到

         return 0;
 34     }
 35 
 36 

总结

这几种算法在后面的一维数组、二维数组都会用到，主要是想清楚每种算法的特性，写出对应的循环体，要记清楚循环次数这些小细节。