Created
February 11, 2019 05:02
-
-
Save edwardyi/e1090271ca4eba5492633807e941f4e0 to your computer and use it in GitHub Desktop.
Merge Sort In C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // https://www.bilibili.com/video/av9982752/?spm_id_from=333.788.videocard.1 | |
| #include <stdio.h> | |
| void merge(int arr[], int L, int M, int R) { | |
| int LEFT_SIZE = M-L; | |
| int RIGHT_SIZE = R-M+1; | |
| int left[LEFT_SIZE]; | |
| int right[RIGHT_SIZE]; | |
| int i,j,k; | |
| // 下標從L開始 | |
| for(i=L;i<M;i++) | |
| { | |
| left[i-L] = arr[i]; | |
| } | |
| // 下標從M開始 | |
| for(i=M;i<R;i++) | |
| { | |
| right[i-M] = arr[i]; | |
| } | |
| // 重新賦值 | |
| i=0; j=0; k=L; | |
| // 取小的加一 | |
| while(i<LEFT_SIZE && j<RIGHT_SIZE) | |
| { | |
| if(left[i] < right[j]) | |
| { | |
| arr[k] = left[i]; | |
| i++; | |
| k++; | |
| } | |
| if(right[j] < left[i]) | |
| { | |
| arr[k] = right[j]; | |
| j++; | |
| k++; | |
| } | |
| } | |
| // 處理剩下的陣列 | |
| while(i<LEFT_SIZE) | |
| { | |
| arr[k] = left[i]; | |
| i++; | |
| k++; | |
| } | |
| // 當原陣列是4個的時候會修改到R的值,造成無窮迴圈 | |
| // 請見下方的測試資料 | |
| while(j<RIGHT_SIZE) | |
| { | |
| arr[k] = right[j]; | |
| j++; | |
| k++; | |
| } | |
| } | |
| void mergeSort(int arr[], int L, int R) | |
| { | |
| // 一個以上的元素才會呼叫到遞迴的方法,剩下一個元素不處理 | |
| if(L<R) { | |
| return ; | |
| } else { | |
| int M = (L+R) / 2; | |
| // printf("L=%d R=%d M=%d \n",L ,R , M); | |
| mergeSort(arr, L, M); | |
| mergeSort(arr, M+1, R); | |
| merge(arr, L, M+1 ,R); | |
| } | |
| } | |
| int main() { | |
| int L = 0; | |
| int M = 3; | |
| int R1 = 6; | |
| int arr[] = {3,9,20,8,21,22}; | |
| // 出現無窮迴圈的情況 | |
| // int M = 2; | |
| // int R1 = 4; | |
| // int arr[] = {3,9,8,20}; | |
| // 已經排序好的陣列 | |
| // merge(arr, L, M, R1); | |
| mergeSort(arr, L, R1); | |
| int i=0; | |
| // printf("second arr value %d R1=%d",arr[1], R1); | |
| for(i=0; i<R1; i++) { | |
| printf("i=%d, R=%d,arr[i]=%d\n",i,R1, arr[i]); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment