BAT 经典算法笔试题-归并排序算法
共 1492字,需浏览 3分钟
·
2021-11-20 23:59
一、算法思想
归并排序的主要思想是分治法。主要过程是:
1. 将n个元素从中间切开,分成两部分。
2. 将剩下的数组通过递归的方式一直分割,直到数组的大小为 1,此时只有一个元素,那么该数组就是有序的了。
3. 从最底层开始逐步合并两个排好序的数列。把两个数组大小为1的合并成一个大小为2的有序数列,再把两个大小为2有序数列的合并成4的有序数列 … 直到全部小的数组合并起来。
二、思考
那么如何将两个有序数列合成一个有序的数列呢?
我们举个栗子把,一看就懂啦。
三、举个栗子
那么问题来了,难道归并排序只能排这种有序的数组么?
四、问题解决
五、算法实现
#include
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;
// 填充左边的数组
for (i=L; ileft[i-L] = arr[i];
}
// 填充右边的数组
for (i=M; i<=R; i++){
right[i-M] = arr[i];
}
// for (int i=0; i
// printf("%d\n",left[i]);
// }
//
// for (int i=0; i
// printf("%d\n",right[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++;
}else{
arr[k] = right[j];
j++;
k++;
}
}
while(i < LEFT_SIZE){
arr[k] = left[i];
i++;
k++;
}
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;
mergeSort(arr,L,M);
mergeSort(arr, M+1,R);
merge(arr, L, M+1,R);
}
}
int main(){
// int arr[] = {3,7,8,10,2,4,6,9};
int arr[] = {8,7,2,10,3,9,4,6};
int L = 0;
int M = 4;
int R = 7;
mergeSort(arr,L,R);
for (int i=0; i<=R; i++){
printf("%d\n",arr[i]);
}
}