DAY 1 数据结构与算法 （选择排序，冒泡排序，插入排序）

1.选择排序

        选择排序（Selection Sort）是一种简单直观的排序算法。其基本思想是每一次从待排序的数据元素中选择最小（或最大）的一个元素，放在已排好序的元素序列的末尾，直到全部待排序的数据元素排好序为止。即每一次设定一个数为最大或者最小值，然后与其他的数进行交换。

（1）首先定义第一位数字为“最小值”，然后与后面的数字一一比较，如有发现比这个数字更小的数字，就进行交换，这样就可以让第一位数字成为名副其实的最小值。

（2）之后定义第二位数字为“最小值”，再与后面的数字一一比较，如有发现比这个数字更小的数字，就进行交换，这样就可以让第二位数字成为名副其实的次小值。

.......一直到最后一位数字就终止了，这就是选择排序的大致思想和流程。

代码如下：

#include<stdio.h>
int main(void)
{
	int n;
	scanf("%d",&n);
	int arr[n];
	int i,j,k;
	for(i=0;i<n;i++)
		scanf("%d",&arr[i]);
	for(j=0;j<n;j++)//这代表定义哪一位作为“最小值”。
		{
			for(k=j+1;k<n;k++)//让后续每一位与“最小值”比较，更小即交换
				{
					if(arr[k]<arr[j])//如若更小,swap
                        {
                            int t;
                            t=arr[k];
                            arr[k]=arr[j];    
                            arr[j]=t;
                        }
				}
		}
	printf("The sorted arr:\n");
	for(i=0;i<n;i++)
		printf(" %d",arr[i]);
	return 0;
 } 

2.冒泡排序

        冒泡排序的思想也是比较简单的，它的思想是通过对待排序序列从前向后（从下标较小的元素开始）,依次对相邻两个元素的值进行两两比较，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就如果水底下的气泡一样逐渐向上冒。与选择排序所不同的是，它并不需要定义“最大最小值”

（1）首先，从第一位开始，与第二位比较，如若第一位比第二位大，则交换，一直交换到最后一位，此时可以发现，最后一位其实就是最大的。第N位就是最大的。

（2）其次，依然从第一位开始，与第二位进行比较，一直到第N-1位，此时第N-1位的数字就是最大的。

......不难发现，我们是从0~(n-1),0~(n-2)......0~(n-n) 最后达成有序。

代码如下：

#include<stdio.h>
int main(void)
{
	int n,i;
	scanf("%d",&n);
	int arr[n];
	for(i=0;i<n;i++)
		scanf("%d",&arr[i]);
	int j,k;
	for(j=n-1;j>0;j--)//0~n 0~n-1 0~n-2 .... 0~0有序
		for(k=0;k+1<j;k++)//从第一位开始，两两比较，注意边界为j.
			{
				if(arr[k]>arr[k+1])//如果左侧比右侧大则交换 swap
					{
						int t;
                        t=arr[k];
                        arr[k]=arr[j];
                        arr[j]=t;
					}
			}
	printf("The sorted arr:\n"); 
	for(i=0;i<n;i++)
		printf("%d ",arr[i]);//output
	return 0;
 }

3.插入排序

        插入排序很像我们在玩斗地主的时候的抓牌流程，假设我们抓了一张牌，为了保证有序性，我们可以从最小的一张开始从右向左进行比对，如果抓的是大王，很显然我们要把它放在最左侧，

如果是一张3，很显然我们把它放在最右侧，这对数组来说是有实际意义的，即 不能越界。

核心思想：0~0有序 0~1有序 0~2有序 0~n-1有序。

（1）0~0一定是有序的。

（1）0~1上，就让第二位与第一位比较，谁大谁放右侧（左侧亦可）。//从右向左比较，体现插入性，即在原来0~n有序的基础上，插入一个新的数字。

（2）0~2上，让第三位与第二位比较，之后更新数值后，再让第二位与第一位比较，实现0~2上的有序。

...不难发现，其实是让数据0~0有序 0~1有序.... 在0~n-2有序的前提下 插入第n位数字 并且使之有序。即为插入 排序。

代码如下：

//插入排序
#include<stdio.h>
int main(void)
{
int n,i;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
	scanf("%d",&arr[i]);
int j,k;//保证0~i有序
for(j=1;j<n;j++)//0~0一定有序，所以之间从0~1上开始
	for(k=j;k-1>=0;k--)//从右向左两两比较 0~j上有序,注意边界,最小为0，最大为n-1。 
		{
			if(arr[k-1]>arr[k])//当左侧大于右侧数值交换 swap
				{
					int t;
                    t=arr[k-1];
                    arr[k-1]=arr[k];
                    arr[k]=t;
				}	
		} 
printf("The sorted arr:");
for(i=0;i<n;i++)
	printf(" %d",arr[i]); 
return 0;	
}

 谢谢！

                                                                                                                                             2024/7/6