前言

之前还在不紧不慢的状态中，转眼间找实习就开始了，第一个目标是CVTE的嵌入式软件开发实习生的岗位，昨天刚刚网申，听了宣讲会，明天就要参加在线测评了（还是广州站的最后一次机会……），时间很紧，抓紧时间复习一下一些知识点，看过一点往年试题，排序算法部分考得挺多，便整理了一下。

冒泡排序

基本思想：比较相邻的两个数，如果前者比后者大，则进行交换。每一轮排序结束，选出一个未排序中最大的数放到数组后面。若数组长度为n，则需进行n-1轮排序才能得出结果。

#include<stdio.h>
/* 冒泡排序算法 */
void bubbleSort(int *arr ,int n)
{
	int i,j;
	for(i=0;i<n-1;i++)                         //进行n-1轮排序
	{
		for(j=0;j<n-i-1;j++)                   //对未排序部分进行排序
		{
			if(arr[j]>arr[j+1])
			{
				int temp=arr[j+1];             //比较交换
				arr[j+1]=arr[j];
				arr[j]=temp;
			}
		}
	}
}
int main()
{
	int data[]={1,8,6,3,4,5,7,9};
	int n = sizeof(data) / sizeof(int);        //计算数组长度
	bubbleSort(data,n);
	printf("数组长度为：%d\n",n);
	printf("排序后的数组为：\n");
	for(int a=0;a<n;a++)
	{
		printf("%d ",data[a]);	
	}
	printf("\n");
	return 0;
}

直接插入排序

基本思想：和交换排序不同的是它不用进行交换操作，而是用一个临时变量存储当前值。当前面的元素比后面大时，先把后面的元素存入临时变量，前面元素的值放到后面元素位置，再到最后把其值插入到合适的数组位置。

#include<stdio.h>
void InsertSort(int *arr,int n)
{
	int i,j;	
	for(i=1;i<n;i++)
	{
		j=i-1;
		if(arr[i]<arr[j])
		{
			int temp=arr[i];
			arr[i]=arr[j];
			while(temp<arr[j-1])
			{
				arr[j]=arr[j-1];
				j--;
			}
			arr[j]=temp;
		}
	}
}
int main()
{
	int arr[]={1,8,6,3,4,5,7,9,2,10};
	int n = sizeof(arr) / sizeof(int); 
	InsertSort(arr,n);
	printf("数组长度为：%d\n",n);
	printf("排序后的数组为:\n");
	for(int i=0;i<n;i++)
	{
		printf("%d",arr[i]);
	}
	printf("\n");
	return 0;
}

直接选择排序

基本思想：依次选出数组最小的数放到数组的前面。首先从数组的第二个元素开始往后遍历，找出最小的数放到第一个位置。再从剩下数组中找出最小的数放到第二个位置。以此类推，直到数组有序。

#include<stdio.h>
void SelectSort(int *arr,int n)
{
	int i,j;	
	for(i=0;i<n;i++)
	{
		int key=i;
		for(j=i+1;j<n;j++)
		{
			if(arr[j]<arr[key])
			{
				key=j;
			}
		}
			if(key!=i)
			{
				int temp=arr[key];arr[key]=arr[i];arr[i]=temp;
			}		
	}
}
int main()
{
    int data[]={1,8,6,3,4,5,7,9};
    int n = sizeof(data) / sizeof(int);        //计算数组长度
    SelectSort(data,n);
    printf("数组长度为：%d\n",n);
    printf("排序后的数组为：\n");
    for(int a=0;a<n;a++)
    {
        printf("%d ",data[a]);    
    }
    printf("\n");
    return 0;
}

完结，继续复习，白了个白。。。