首页 > 代码库 > 归并排序

归并排序

tag: 算法基本功 -> 排序 ->快速排序

 

归并排序思路:

(1) 通过递归的方式把数据拆分成两两数据对(可能存在落单的数)

(2) 将两两数据对进行排序同时将排序结果存在临时数组中

(3) 把临时数组中已经排好的数按照对应的序号更新到原数组中

 

package com.zhaochao.sort;

/**
* Created by zhaochao on 17/1/16.
*/
public class MergeSort {

public void mergeSort(int[] arrs, int left, int right) {

if(left >= right || arrs == null || arrs.length <= 1) {
return;
}

int mid = (left + right) / 2;
mergeSort(arrs, left, mid);
mergeSort(arrs,mid + 1, right);
sort(arrs,left,right);

}

public void sort(int[] arrs, int left, int right) {
if(left >= right) {
return;
}

int mid = (left + right) / 2;
int[] tmp = new int[right - left + 1];

int i = left;
int j = mid + 1;
int count = 0;

while((i <= mid) && (j <= right)) {
if ( arrs[i] < arrs[j]) {
tmp[count++] = arrs[i++];
}
else {
tmp[count++] = arrs[j++];
}
}
while(i <= mid){
tmp[count++] = arrs[i++];
}
while(j <= right) {
tmp[count++] = arrs[j++];
}

for(int p = 0; p < right - left + 1; p++) {
arrs[p + left] = tmp[p];
}

}

public static void main(String[] args) {

MergeSort test = new MergeSort();
//int[] arrs = {9,8,7,6,1,2,3};
int[] arrs = {9,8,7,6,1,2};
test.mergeSort(arrs,0,5);
for(int i = 0; i < 6; i++) {
System.out.println(arrs[i]);
}
}


}

 

归并排序