Sort
排序
排序
副程式寫法
1.氣泡排序 Bubble Sort
#define SWAP(x,y,t)(t=x,x=y,y=t)
宣告：void bubble(int[],int);
呼叫：bubble(a,n);
1.1-雙層迴圈法：
void bubble(int a[],int n){
int i,j,temp;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(a[j]<a[i])
SWAP(a[i],a[j],temp);
}
}
}
1.2-相鄰兩數比較法：
宣告：void one_bubble(int[],int);
呼叫：for(int i=0;i<n-1;i++){
one_bubble(arr,n-1-i);
}
void one_bubble(int a[],int end){
int j,temp;
for(j=0;j<end;j++){
if(a[j]>a[j+1])
SWAP(a[j],a[j+1],temp);
}
}
2.選擇排序 Select Sort
宣告：void select(int[],int);
呼叫：select(arr,n);
void select(int a[],int n){
int temp,key;
for (int i=0;i<n;i++){
key = i;
for(int j=i+1;j<n;j++){
if(a[j]<a[key])
key = j;
}
if(key!=i)
SWAP(a[i],a[key],temp);
}
}
3.插入排序 Insertion Sort
宣告：void Insert(int [],int);
呼叫：Insert(a,n);
void Insert(int a[],int n){
int tmp,j,k,l;
for(int i=1;i<n;i++){
tmp=a[i];
j=i-1;
while(a[j]>tmp && j>=0){
a[j+1]=a[j];
j--;
}
a[j+1]=tmp;
Print(a,n);
}
}
4.快速排序 Quick Sort，分治、遞迴。
宣告：int partition(int[],int,int);
void QuickSort(int[],int,int);
呼叫：QuickSort(a,0,n-1);
int partition(int a[],int left,int right){
int i,j,base,tmp;
base=a[right];
j=left-1;
for(i=left;i<right;i++){
if(a[i]<=base){
j++;
SWAP(a[i],a[j],tmp);
}
}
SWAP(a[j+1],a[right],tmp);
return j+1;
}
void QuickSort(int a[],int left,int right){
int p;
if(left<right){
p=partition(a,left,right);
QuickSort(a,left,p-1);
QuickSort(a,p+1,right);
}
}
5.合併排序 Merge Sort，分治、遞迴。