笔记整理（数组与函数结合：排序）12.9

（一）排序

（1）冒泡排序

思想：就是相邻元素进行比较，然后排序，最多会进行n-1趟排序的过程，每趟最多会进行n-1次交换；每一趟下来会找出所剩元素中的最大值或最小值

例如：a[5]={7,4,10,18,-4}进行从大到小排序

第一趟：7与4比较，7>4,不交换，4与10比较，4<10,交换，4与18比较，4<18,交换，4与-4比较，4>-4,不交换。交换后：7,10,18,4，-4；第一趟后就冒出来一个最小值

第二趟：前四位继续进行交换，后结果为：10,18,7,4，-4；

第三趟：结果：18,10,7,4，-4

第三趟结束后已经出现结果了，然而有时候很不幸得排n-1次；

#include <stdio.h> 
#include <stdlib.h>
#define N 30
void Sort(int arr[],int n);
int main(int argc, char** argv) 
{
	int z,i;
	int a[N];
	printf("input z:"); 
	scanf("%d",&z);//输入数组大小 
	for(i=0;i<z;i++)
	{
		scanf("%d",&a[i]);//输出数组 
	}
	Sort(a,z);//调用排序函数 
	for(i=0;i<z;i++)
	{
		printf("%d ",a[i]);//输出 排序后的结果 
	}
	return 0;
}
void Sort(int arr[],int n)
{
	int temp, i,j;
	for(i=0;i<n-1;i++)//外循环表示需循环的趟数 
	{
		for(j=0;j<n-1-i;j++)//内循环表示每一趟需要进行交换的次数 
		{
			if(arr[j+1]>arr[j])//将数组元素从大到小排序
			//if(arr[j]>arr[j+1]) 将数组元素从小到大排序 
			{
			temp=arr[j];//用中间变量实现交换 
			arr[j]=arr[j+1];
			arr[j+1]=temp;}	
		}
	 } 
}
           

（2）交换排序

思想：以升序排序为例（降序时则反过来），将第一个数与后面每一个数进行比较，若有小于该数的则交换，大于则不交换，这一轮结束后会得到一个最小值放在第一个数的位置；然后进入第二轮比较，直到第n-1轮，求出一个最小数放在n-1的位置，第n个位置就是最大值，例子就不举了，很多教材上都有

#include <stdio.h> 
#include <stdlib.h>
#define N 30
void Sort(int arr[],int n);
int main(int argc, char** argv) 
{
	int z,i;
	int a[N];
	printf("input z:"); 
	scanf("%d",&z);//输入数组大小 
	for(i=0;i<z;i++)
	{
		scanf("%d",&a[i]);//输出数组 
	}
	Sort(a,z);//调用排序函数 
	for(i=0;i<z;i++)
	{
		printf("%d ",a[i]);//输出 排序后的结果 
	}
	return 0;
}
void Sort(int arr[],int n)
{
	int temp, i,j;
	for(i=0;i<n-1;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(arr[i]>arr[j])
			{
				temp=arr[i];
				arr[i]=arr[j];
				arr[j]=temp;
			}
		}
	}
}
           

（3）选择法排序

思想：每一轮找出余下数据的最大值后再与第i+1个数交换位置这样每轮只用交换一次，与交换排序相比交换操作减少，最多进行n-1次交换

#include <stdio.h> 
#include <stdlib.h>
#define N 30
void Sort(int arr[],int n);
int main(int argc, char** argv) 
{
	int z,i;
	int a[N];
	printf("input z:"); 
	scanf("%d",&z);//输入数组大小 
	for(i=0;i<z;i++)
	{
		scanf("%d",&a[i]);//输出数组 
	}
	Sort(a,z);//调用排序函数 
	for(i=0;i<z;i++)
	{
		printf("%d ",a[i]);//输出 排序后的结果 
	}
	return 0;
}
void Sort(int arr[],int n)
{
	int temp, i,j,k;
	for(i=0;i<n-1;i++)
	{   k=i;
		for(j=i+1;j<n;j++)
		{
			if(arr[j]>arr[k])
			k=j;
		}
		if(k!=i)
		{
			temp=arr[k];
			arr[k]=arr[j];
			arr[j]=temp;
		}
	}
}