嵌入式学习笔记七——C语言数组排序和一维字符型数组

选择排序

思想：给合适的位置选择合适的数

    首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

如何理解这个过程?

以降序为例：

          设数组int a[]={3,1,2,4,6,9,7}

        第1次，我们首先要找到未排序序列中的最小值，按顺序来，先假设a[0]为最小值，将a[0]与后面的数据进行比较，如果a[j]<a[0]成立,则交换a[j]与a[0]的值，如果a[j]<a[0]不成立，则a[0]是最小值。a[1]=1，a[0]=3,则a[1]与 a[0]交换值，现在a[0]=1,a[1]=3,再将a[0]与a[2] a[3]...a[6]比较，这里1已经是最小值，所以a[0]=1。

        第2次，继续找未排序序列中的最小值，a[0]已经确定，所以现在从a[1]开始比较，a[1]=3,a[2]=2,a[2]<a[3],交换值，此时a[1]=2,a[2]=3。重复比较与交换值的过程，得到a[0]=2。

        重复上面的步骤，进行到第6次时，a[5]确定后a[6]也确定了，此时我们用选择排序完成了对数组a的排序。

总结：

1.选择要确定数据的位置。按顺序来，从下标为0开始，到倒数第二个len-1数结束。

2.选择要比较的数，从选择的位置的下一个数开始，直到与最后一个数比完才结束。

3.与该位置的前一个数比较，如果前一个数更小，交换值。

4.比完一趟后会确定一个位置的值，比完len-1趟后排序完成。

选择排序的代码如下：

 //选择排序（升序）
	for(i=0;i<len-1;i++)	    //选择要确定的位置,i=0：从a[0]开始
                                //i<len-1：到倒数第二个数的位置
                                //因为倒数第二个数确定了最后一个数也就确定了
	{
		for (j=i+1;j<len;j++)   //选择要比较的数，j=i+1：从a[i]后面的数开始比较
                                //j=len：到最后一个数
		{
			if (a[j]<a[i])      //如果该位置的前一个数比要放入这个位置的数小
			{
				temp = a[i];    //交换数据保证最小的数在前面
				a[i] = a[j];
				a[j] = temp;
			}
		}
    }

流程图

应用

#include <stdio.h>
 
int main(void)
{
	int a[10]={5,7,9,6,4,2,3,1,4,0}
	int i,j,temp;
    int len;
	len  = sizeof(a)/sizeof(a[0]);	//取数组长度（元素个数）
    //选择排序（升序）
	for(i=0;i<len-1;i++)	    //选择要确定的位置,i=0 从a[0]开始
                                //i<len-1确定到倒数第二个数
	{
		for (j=i+1;j<len;j++)   //选择要比较的数，j=i+1 选择a[i]后面的数开始比较
                                // j=len比较到最后一个数
		{
			if (a[j]<a[i])      
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
	for (i=0;i<len;i++)            //输出数组
		printf("%d "a[i]);
	return 0;
}
 

冒泡排序

思想:
       一次冒出一个数 
       相邻两个元素，两两比较，小的放前，大的放后 

如何理解这个过程？

设数组int a[7]={3,1,7,2,5,4,6}

第一趟，相邻两元素，两两比较，小的放前，大的放后a[0]>a[1]成立，交换值，a[0]=1  a[1]=3

a[1]>a[2]不成立，a[2]与a[3]比较，以此类推直到最后两数比较完，得到最后一个数为最大值。

重复上面的步骤，第n-1趟时，完成排序。

总结：

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，2从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

3.针对所有的元素重复以上的步骤，除了最后一个；

4.重复步骤1~3，直到排序完成。

冒泡排序代码如下：

//冒泡排序
	for (i = 0;i<n-1;i++)//控制趟数，共n-1趟
	{
		for(j = 0;j < n-1-i; j++)//一趟的比较过程，比较的次数与i有关
		{
			if(a[j] > a[j+1])// 交换值
			{ 
				temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}

流程图

流程与选择排序很类似但却不相同，需要分清楚。

应用

#include<stdio.h>
 
int main(void)
{
	int a[] = {4,5,7,8,9,6,1,2,3,5};
	int i,j,temp;
	int n;
	n = sizeof(a) / sizeof(a[0]);
	for (i = 0;i<n-1;i++)
	{
		for(j = 0;j < n-1-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]);
	printf("\n");
  
	return 0;
 
}
 

插入排序

思想:
        在有序序列中，找到合适的位置插入 。

如何理解这个过程？

设数组int a[]={3,5,2,4,6,9,7};

int b[7];

第1次，将第一个数a[0]给b[0]，a[0]=b[0];

第2次，我们想把a[1]给b[1], 但是要先判断这个数放在b[1]的位置是否合适，如果这个数比前面的数小，就应该放在更前面的位置。先将t=a[1]，b[1]前面的位置是b[0]，让t与b[0]比较，t<b[0],则b[1]=b[0]。b [0]前面没有其他数了，将t放入b[0]。

第3次，我们想把a[2]给b[2],让t=a[2],先判断t<b[1]，成立,则b [2]=b[1],再判断t<b[1] ，不成立，则b[1]=t,前面的值不变。

重复上面的步骤，到第6次（n次），可以完成数据从小到大排列。

        插入排序有两种方式，包括原地插入排序和非原地插入排序，上面分析的是非原地插入排序的过程。原地插入排序只用到了一个数组，没有另外开辟空间，分析时将b[i]换成a[i]，过程与上述过程类似。

总结：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素（已排序）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后；

6.重复步骤2~5

插入排序代码如下

 
//非原地插入
	for(i=0;i<n;++i)
	{
		int t = a[i];
		j = i;
		while(j>0 && t<b[j-1])
		{
			b[j] = b[j-1];
			--j;
		}
		b[j]=t;
 
	}
//原地插入
 
	for(i=1;i<n;++i)
	{
		int t = a[i];
		j = i;
		while(j>0 && t<a[j-1])
		{
			a[j] = a[j-1];
			--j;
		}
		a[j]=t;
 
	}

非原地插入排序流程图

应用：

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

二分查找

     二分查找(折半查找) 
     大前提:
        数据得是有序的
    思想:
        1. 找到中间位置的数， //下标 
        2. 拿这个数 和 要找的数比较 
        
        mid //下标  
        a[mid] > m 
        a[mid] < m
        
        3. 每次折一半，直到找到对应数组，或者 结束 

总结

1.找到中间位置：mid = (begin + end)/2;

2.比较大小：

if (a[mid]>num)
        {
            end = mid -1;
        }
        else if (a[mid]<num)
            begin=mid+1;
        else break;

3.循环条件：begin<=end

4判断找到的条件：begin<=end

二分法查找代码如下

	while(begin<=end)
	{
     	mid = (begin + end)/2;
		if (a[mid]>num)
		{
			end = mid -1;
		}
		else if (a[mid]<num)
			begin=mid+1;
		else break;
	}
	if (begin<=end)
		printf("found!\n");
	else 
		printf("not found!\n");

一维字符数组

数据类型 数组名[数组长度]

从数组角度:
   char s[20] = {'a','b','c','d'};部分初始化，剩下的都是0。
  赋值为字符串：
  1.字符串 是 当做字符数组来处理的。
  2.字符串 有一个专门的结束标志 '\0'
  3.处理的是字符串，操作的时候，往往以 结束标志 为 操作依据 
  4.处理的是数组，操作的时候，往往以 数组长度 作为操作依据 
  5.字符数组可以用来存储字符串 
    而字符串在内存中存储的方式 也是以 字符数组形式存储的     
 如 "hello" --- 'h''e''l''l''o''\0'
               实际占用的内存空间，是包含了'\0'   
  

  int puts(const char *s);
     功能:
           输出一个字符串 
     参数:
         s   //表示字符串 -- 指针类型 
             //字符数组名 s
             //字符串常量 "hello"
    返回值:
          成功 非负数 
          失败 -1 
    注意:
       puts输出时 自动会加 换行 
     
     gets 
     char *gets(char *s);
     功能:
         从键盘获得一个字符串 
     参数:
         s  //代表就是一块存储空间 --- 需要的是一个一维字符型数组的数组名
     返回值:
        成功 s 
        失败 NULL