C语言——数组和排序

C语言——数组和排序

• 数组
• • 数组的概念
  • 数组的初始化
  • 数组的特点
• 排序
• • 选择排序
  • 冒泡排序
  • 插入排序
• 二分查找

数组

数组的概念

数组是一组数据 ；
数组是一组相同类型的数据或变量的集合 ；
应用场景：
用于批量的处理多个数据 ；
语法：
类型说明符 数组名 [常量表达式]
类型说明符也就是数组中元素的数据类型，元素的数据类型可以是整型（int/short/long/long long）、字符型（char）、浮点型（float / double /long double ）；

数组名代表的是整个数组也表示的是数组首元素的地址，数组名的命名规则和普通变量的命名规则一致；

**[常量表达式]**其中的常量表达式代表的是数组的长度，数组长度可以省略，但是必须要有初始化编译器要根据初始化的值，来推算实际的长度。需要注意的是：c99标准之后,数组长度可以是变量但是不能初始化。

数组的初始化

数组的初始化可以分为三种：
1、全部初始化：int a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
2、部分初始化：int a[10] = { 1, 2, 3, 4, 5 };
特点：没有被初始化的部分会被初始化为0；
3、不初始化：int a[10];
特点：不初始化数组中的值全部是随机值；

数组的特点

1、连续性， 即数组空间是一片连续内存空间 ；
2、有序性，即数组的元素挨个存放 ；
3、单一性，即数组元素类型是同一类型 ；

数组下标的含义:
a[0]，下标表示的是相对于数组名也就是数组首元素偏移了几个元素。

排序

选择排序

选择排序的主要思想就是给数选择合适的位置；
实现代码如下：

#include <stdio.h>

int main(void)
{
	int i = 0, j = 0, size = 0, temp = 0;
	scanf("%d", &size);
	int a[size];

	for (i = 0; i < size; ++i)
	{
		scanf("%d", &a[i]);
	}

	for (i = 0; i < size-1; ++i)
	{
		for (j = i+1; j < size; ++j)
		{
			if(a[j] < a[i])
			{
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}

	for(i = 0; i < size; ++i)
	{
		printf("%d ", a[i]);
	}

	printf("\n");

	return 0;
}

按照我的理解选择排序按照顺序选择一个数然后一次与数组后面的数进行比较假设要排升序，如果被选择的数在比较的过程中小于其他的数就交换这两个数，举个例子来说假设有一个数组a[5] = { 5, 2, 0, 9, 8 };第一次也就是i = 0时，拿5和2（a[j]其中j==1）比较，2 < 5，交换2和5的在数组中的位置，此时a[i]就为2，然后2再和0进行比较（也就是让j++），0 < 2,交换这两个元素，此时a[i] == 0,再拿0和9（j++）比较，9 > 0不交换，再拿8和0比较（j++），8 > 0不交换此时到达数组末尾数组中首元素就是最小值然后让i++也就是拿第二个元素和它后面的元素进行比较，以此类推直到倒数第二个元素和倒数第一个元素比较一次后结束循环，此时数组中的元素就是升序的了。

冒泡排序

冒泡排序的主要思想是:一次冒出一个数相邻两个元素进行两两比较，小的放前，大的放后。

实现冒泡排序的核心代码：

for (i = 0; i < n-1; ++i)
{
	for (j = i + 1; j < n; ++j)
	{
		if (a[j] < a[i])
		{
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
}

我的理解是冒泡排序就是从第一个数开始让第一个数和第二个数进行比较大的放在后面小的放在前面，然后让第二个元素和第三个元素进行比较同理大的在后小的在前，直到倒数第二个元素和最后一个元素的比较完成后数组最后一个元素就是最大的元素，然后进行第二趟冒泡再进行第二趟冒泡时就不需要和最后一个元素a[n - 1]比较了因为最后一个元素已经是最大了，第二趟只需要比较前面n - 1个数（其中n为数组元素的个数），第二趟比较也是从a[0]开始和a[1]比较大在后小在前，a[1]和a[2]比较以此类推直到a[n - 2]和a[n - 3]比较这一趟冒泡过程结束，到第三趟冒泡确定第三大得数，直到n - 1趟冒泡结束整个冒泡排序；经过冒泡排序最后数组就就变得有序了。

插入排序

插入排序的主要思想是在有序序列中，找到合适的位置插入 。

实现插入排序的核心代码：

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;
}

假设数组为 int a[5] = { 5, 2, 10, 3, 9};
其实插入排序跟我们平时, 排队差不多，假设我们要把数组元素按升序排列，组第一个元素我们认为它是有序的，我们用一个临时变量保存第二个元素然后拿这个临时变量temp和第一个元素比较如果第二个元素比第一个元素小那么第一个元素往后移动一个位置因为第一个元素前没有数据了所以把temp赋值给第一个元素，以上的例子就是temp = 2；2 小于 5,5往后移动四个字节把2覆盖掉，此时数组元素就是 5， 5， 10， 3， 9然后把temp赋值给a[0]此时数组元素就是2，5，10，3，9，然后拿第三个元素和前面的元素比较10大于5和2不用动，再拿第四个元素和前面的元素比较，3小于10,10往后移动，把3赋值给未移动前10的位置，3再和5比较3小于5，5往后移动把3赋给5移动前的位置，3再和2比较3大于2结束比较，最后的9和前面元素的比较的过程也是一样的如果比前一个元素小，前一个元素就往后移动直到大于前一个元素或者到数组首元素为止。

二分查找

二分查找的前提是数组元素有序，输入要查找的元素，设置中心坐标，用中心坐标元素和要查找的元素比较如果要查找的元素大就往右找即begin = mid + 1;再更新坐标再继续找，如果要查找的元素小就往左找end = mid - 1;再比较直到找到为止。

#include <stdio.h>

int main(void)
{
	int a[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	int begin = 0;
	int key = 0;
	int end  = sizeof(a) / sizeof(a[0]);
	scanf("%d", &key);

	while(begin <= end)
	{
		int mid = (begin + end) / 2;

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

	if(begin <= end)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}

	return 0;
}