归并排序

xiaoxiao2021-02-28 94

/** 归并排序 **/ #include<stdio.h> #include<stdlib.h> //全局数组 int arrays[] = {1,4,2,5,2,87,3,4356,6,2,9,67,4,24,35,76,768,9,54,543,87,79,79,4,3534,54}; int b[100]; //合并 void MERGE(int low,int mid,int high) { int h = low;//左边部分数组第一个下标 int i=low; //辅助数组的第一个下标 int j = mid + 1;//右边数组第一个下标 //左右两个集合都没取尽 while( (h <= mid) && (j <= high)) { if(arrays[h] <= arrays[j]) { b[i] = arrays[h]; h++; } else { b[i] = arrays[j]; j++; } i++; } //处理剩下的一边的元素 //如果剩下左边的元素 while(h <= mid) { b[i] = arrays[h]; i++; h++;

}

//处理剩下右边的元素

while(j <= high) { b[i] = arrays[j]; i++; j++; } //把辅助数组中的值赋值到原数组的原位置 for(int q = low;q <=high;q++) { arrays[q]=b[q]; } } //拆分 void MERGESORT(int low,int high) { if(low < high) { int mid = (low+high)/2; MERGESORT(low,mid); MERGESORT(mid+1,high); MERGE(low,mid,high); } } void printAll() { int k = sizeof(arrays) /sizeof(arrays[0]); for(int i = 0;i < k ; i++) { printf("%d ",arrays[i]); } } void main() { printf("before : \n"); printAll(); printf("\n"); int k = sizeof(arrays) /sizeof(arrays[0]); MERGESORT(0,k); printf("atfer : \n"); printAll();

}

总结：

归并排序是先拆分，再合并。这样的好处是可以利用一个辅助数组，将排好序的数组，依次放入辅助数组，而不用移动元素。

转载请注明原文地址: https://www.6miu.com/read-57520.html

技术

最新回复(0)