归并排序
原理:
归并排序是一种概念上最简单的排序算法,归并排序是基于分治法的。归并排序将待排序的元素序列分成两个长度相等的子序列,为每一个子序列排序,然后再将他们合并成一个子序列。合并两个子序列的过程也就是两路归并。
算法基本步骤
1,申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
2,设定两个指针,最初位置分别为两个已经排序序列的起始位置;
3,比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
4,重复步骤 3 直到某一指针达到序列尾;
5,将另一序列剩下的所有元素直接复制到合并序列尾
public class merge_Sort {
public static int[] sort (int[] a,int low,int high) {
int mid = (low+high)/2;
if(low<high){
sort(a,low,mid);
sort(a,mid+1,high);
//左右归并
merge(a,low,mid,high);
}
return a;
}
public static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high-low+1];
int i= low;
int j = mid+1;
int k=0;
// 把较小的数先移到新数组中
while(i<=mid && j<=high){
if(a[i]<a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while(i<=mid){
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while(j<=high){
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for(int x=0;x<temp.length;x++){
a[x+low] = temp[x];
}
}
public static void main(String[] args) {
int[] arr = {6,5,3,1,8,7,2,4};
sort(arr, 0, arr.length-1);
System.out.println("排好序的数组:");
for (int e : arr)
System.out.print(e+" ");
}
}