排序算法---归并排序 桃扇骨 2022-03-11 06:16 250阅读 0赞 归并排序的基本思路是江两个有序的系列合并,成为一个新的有序序列。 首先考虑如何合并两个有序序列: //两个有序数组合并 void mergSortArray(int a[] ,int n,int b[],int m ,int c[]){ int i,j,k; i = j = k = 0; while(i<n&&j<m){ if(a[i]<b[j]){ c[k++] = a[i++]; }else{ c[k++] = b[j++]; } } while(i<n){ c[k++] = a[i++]; } while(j<m){ c[k++] = b[j++]; } } 以上合并有序序列效率还是比较高的,可以达到O(n)。 解决了两个有序的序列的合并,再来看看归并排序。 其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了? 可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先**递****归**的分解数列,再**合****并**数列就完成了**归并**排序 下面是c语言实现: #include <stdio.h> //一个数组 条件(mid两边有序) 合并 void mergSortArray(int a[] ,int first ,int mid,int last ,int temp[]){ int i = first; int m = mid; int j = mid+1; int n = last; int k = 0; while(i<=m&&j<=n){ if(a[i]<a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } while(i<=m){ temp[k++] = a[i++]; } while(j<=n){ temp[k++] = a[j++]; } for( int i = 0;i<k;i++){ a[first +i ] = temp[i]; } } //归并排序 先递归把 数组分成只有一段 然后在执行 合并mergSortArray() 方法 void mergeSort(int a[] ,int first,int last,int temp[]){ if(first<last){ int mid = (first + last) /2; mergeSort(a,first,mid,temp); mergeSort(a,mid+1,last,temp); mergSortArray(a,first,mid,last,temp); } } void print(int a[] ,int n) { for (int i = 0;i<n;i++) { printf("%d ",a[i]); } printf("\n"); } int main(int argc, char *argv[]) { int a[]={ 0,59,48,75,98,86,23,37,60 }; print(a,9); int *temp = new int[8]; mergeSort(a,1,8,temp); print(a,9); print(temp,8); return 0; }
还没有评论,来说两句吧...