筆記整理（數組與函數結合：排序）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;
		}
	}
}