归并排序的算法实现
程序员文章站
2024-03-16 12:20:58
...
归并排序的算法实现
归并排序的基本思想是:
将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。
算法:
1.把待排序的n个记录看作长度为1的有序序列,将相邻的子序列两两归并为长度为2或1的有序序列
2.把得到的n/2个长度为2的有序序列再归并为长度为2*2的有序序列
3.按照2的方式,重复对相邻的有序子序列进行归并操作,直到成为一个有序序列为止。
排序以一下方式进行:
一下是我的算法实现:
public void merge_sort(int[]data,int left,int right){
if(left<right){
int mid=(left+right)/2;
//递归调用将数组分组,将数组分成n个记录
merge_sort(data, left, mid);
merge_sort(data, mid+1, right);
//将被分开的数组进行排序,合并
merge(data,left,mid,right);
}
}
private void merge(int[] data, int left, int mid, int right) {
int i=0,k=0;
//用于控制合并过程时下标的处理
int begin1=left,end1=mid,begin2=mid+1,end2=right;
//用于存放数据
int []temp=new int[right-left+1];
//开始比较赋值
while(begin1<=end1&&begin2<=end2){
//依次比较两个排好序的子序列,最初两个子序列中最小元素放入临时数组
if(data[begin1]<data[begin2]){
temp[k]=data[begin1];
begin1++;
}
else{
temp[k]=data[begin2];
begin2++;
}
k++;
}
//如果一个子序列已经完全放入临时数组,将剩余部分的数组放入临时数组
while(begin1<=end1){
temp[k++]=data[begin1++];
}
while(begin2<=end2){
temp[k++]=data[begin2++];
}
//将排好序的临时数组拷贝到原始数组
k=0;
for(i=left;i<=right;i++){
data[i]=temp[k++];
}
}
上一篇: 归并排序的Java实现
下一篇: Javascript面向对象编程--闭包