#30649: c語言新手 merge sort觀念請進！
tinakga920029@gmail.com
(云婷)
學校
:
金門縣金城國中
編號 : 190665
來源 : [218.173.75.121]
最後登入時間 ：
2022-06-03 12:21:10
- Merge Sort
- 將兩個已經排序過的紀錄合併，而得到另一個排序好的紀錄
- 可分為遞迴和非遞迴
- 將資料量n切成n/2和n/2兩半部分，再各自Merge Sort，最後合併成兩半部的排序結果而成
- 切割資料量n的公式[(low+high)/2]
- [ ]：Run已經排序好的檔案紀錄
- Run的長度：Run中記錄個數
- 時間複雜度O(nlogn)
- Divide該陣列成為兩個具有n/2個項目的子陣列
- Conquer每一個子陣列（除非該陣列夠小，否則使用遞回）
- Combine所有子陣列的所有解答來得到解答（binary search不需要combine)
- Merge sort是 out-place的資料結構：需要使用暫存的輔助資料結構，佔用額外記憶體。 補充：in-place的資料結構：使用資料原來的資料結構(陣列)進行排序，不需使用暫存的輔助資料結構，不佔用額外記憶體。 如前面提到的Binary search
#include<stdio.h>
#include<math.h>
void print(int*,int);
void divide(int*,int,int);
void conquer(int*,int,int,int);
int main(){
int size;
scanf("%d",&size);//讀入串列大小
int arr[size];
for(int i=0;i<size;i++){//將資料放入串列
scanf("%d",&arr[i]);
}
int l=0,r=size-1;
divide(arr,l,r);
print(arr,size);//印出來
}
void print(int*arr,int size){
for(int i=0;i<size;i++){
printf("%d",arr[i]);
printf(" ");
}
printf("\n");
}
void divide(int*arr,int l,int r){
int mid;
if(l<r){//代表data還沒切割到最後一個
mid=(l+r)/2;
divide(arr,l,mid);
divide(arr,mid+1,r);
conquer(arr,l,mid,r);
}
}
void conquer(int*arr,int l,int mid,int r){
int t1=(mid-l+1);
int t2=(r-mid);
int temp1[t1];
int temp2[t2];
//宣告出兩個陣列將資料存入
for(int i=0;i<t1;i++){
temp1[i]=arr[l+i];
}
for(int j=0;j<t2;j++){
temp2[j]=arr[mid+j+1];
}
int i=0;//代表temp1陣列起始
int j=0;//代表temp2陣列起始
int initial=l;//代表原始陣列的index
while(i<t1&&j<t2){//代表各arr有大於一個data
if(temp1[i]<=temp2[j]){
arr[initial]=temp1[i];
i++;
}
else if(temp1[i]>temp2[j]){
arr[initial]=temp2[j];
j++;
}
initial++;//無論怎樣原始陣列都會讀入一個較小的值且往前
}
while(i<t1){//當陣列一邊為空
arr[initial]=temp1[i];
i++;
initial++;
}
while(j<t2){
arr[initial]=temp2[j];
j++;
initial++;
}
}
ZeroJudge Forum