归并排序
- 归并排序图
归并排序图.png
- 递归实现简介
-
代码示例
mergesort(left,right,**a){ if(left<right){ int mid = 1/2(left+right); mergesort(left,mid,**a); mergesort(mid+1,right,**a); merge(a,b,left,right); copy(a,b,left,right); } } -
代码解释
-
mergesort方法是向下分裂的方法 -
merge是一个排序方法,对a中的元素用两个指针移动进行比较存入b中 -
copy是一个赋值方法,把b中排序好的值给a
-
-
- 非递归实现简介
-
代码示例
void merge_sort(int *list, int length){ int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * length); for(i=1;i<length;i*=2){ right_min = left_max = left_min+i; right_max = left_max+i; if(right_max>length){ right_max = length; } next = 0; while(left_min<left_max&&right_min<right_max){ tmp[next++] = list[left_min]>list[right_min]?list[right_min++]:list[left_min++]; } while(left_min < left_max){ list[--right_min] = list[--left_max]; } while(next>0){ list[--right_min] = tmp[--next]; } } } -
算法实现解释
- 代码实现步骤(按照i=1,2,4依次进行,都是相同的,所以只列出i=1的情况)
-
i=1:
left[10],right[4] left_min=0,left_max=1,right_min=1,right_max=2 right_max<length 双指针移动逐步比较直到有一边到达尾部 点睛之笔是最后的两个while, 第一个while是判断当left未移动到尾部时,将当前指针指向的值及之后的移动到队尾 如果是right未移动到尾部,直接将tmp中的值按序赋值到list中即可
-
- 代码实现步骤(按照i=1,2,4依次进行,都是相同的,所以只列出i=1的情况)
-
