排序原理:
1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止。
2.将相邻的两个子组进行合并成一个有序的大组;
3.不断的重复步骤2,直到最终只有一个组为止。
排序过程:
例:{8,4,5,7,1,3,6,2}
package com.sort;
/*--------------
* Author:Real_Q
* Date:2021-01-09
* Time:10:44
* Description:归并排序
---------------*/
public class MerageSort {
public static void merageSort(int[] array) {
int low = 0;
int high = array.length - 1;
merageSort(array, low, high);
}
private static void merageSort(int[] array, int low, int high) {
//如果low>=high,跳出函数
if (low >= high) {
return;
}
//把数组分成相等的两等分
int middle = low + (high - low) / 2;
//对分组的数组进行排序,递归调用函数本身
merageSort(array,low,middle);
merageSort(array,middle+1,high);
//对排序好的分数组进行合并
mergage(array,low,middle,high);
}
private static void mergage(int[] array, int low, int middle, int high) {
//存放左子数组起始索引
int left = low;
//存放右子数组索引
int right = middle+1;
//存放辅助数组起始索引
int index = low;
//定义一个辅助数组
int[] assit = new int[array.length];
//扫描左子组 右子组元素
while(left <= middle && right <= high ){//无论哪一个先扫描完 跳出循环
//把最小的值赋值给辅助数组,对应索引和辅助数组索引加一
if(less(array[left],array[right])){
assit[index++] = array[left++];
}else{
assit[index++] = array[right++];
}
}
//跳出循环,如果左子组未扫描完,将剩余的元素放在已完成扫描的数组后面
while(left <= middle){
assit[index++] = array[left++];
}
//跳出循环,如果左子组未扫描完,将剩余的元素放在已完成扫描的数组后面
while(right <= high ){
assit[index++] = array[right++];
}
//讲完成排序的辅助数组的值赋值给原数组
for (int i = low; i <= high ; i++) {
array[i] = assit[i];
}
}
//比较两个元素的大小,返回比较结果
public static boolean less(int a, int b) {
return (a - b < 0);
}
//交换数组中的两个元素
public static void exchange(int[] array, int index1, int index2) {
int temp;
temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
测试类:
package com.testsort;
/*--------------
* Author:Real_Q
* Date:2021-01-09
* Time:11:43
* Description:
---------------*/
import java.util.Arrays;
import static com.sort.MerageSort.merageSort;
public class TestMerage {
public static void main(String[] args) {
int[] array = {8,4,5,7,1,3,6,2};
merageSort(array);
System.out.println(Arrays.toString(array));
}
}