开发笔记:9.八大排序

1 package com.duan.array;
2
3 import java.util.Arrays;
4 //分而治之。假设初始序列有N个记录，则可以看成N个有序的子序列，每个子序列的长度为1，然后两两合并得到一个N/2
5 //个长度为2或1的有序子序列，再两两归并...如此重复直到得到一个长度为N的有序序列为止。
6 public class MergeSort {
7 public static void main(String[] args) {
8 int[]arr={2,3,5,8,4,1,7,6,9,10};
9 chaifen(arr,0,arr.length-1);
10 System.out.println(Arrays.toString(arr));
11 }
12
13 private static void chaifen(int[] arr, int startIndex, int endIndex) {
14 int centerIndex=(startIndex+endIndex)/2;
15 if(startIndex<endIndex){
16 //左边递归拆
17 chaifen(arr,startIndex,centerIndex);
18 //右边递归拆
19 chaifen(arr,centerIndex+1,endIndex);
20 //合并
21 hebing(arr,startIndex,centerIndex,endIndex);
22 }
23 }
24
25 private static void hebing(int[] arr, int startIndex, int centerIndex, int endIndex) {
26 //定义一个临时数组
27 int[] tempArray=new int [endIndex-startIndex+1];
28 //定义临时数组起始索引
29 int index=0;
30 //定义第一个数组起始索引
31 int i=startIndex;
32 //定义第二个数组起始索引
33 int j=centerIndex+1;
34 //遍历数组开始归并
35 while(i<=centerIndex&&j<=endIndex){
36 if(arr[i]<=arr[j]){
37 tempArray[index]=arr[i];
38 i++;//增加索引
39 }else{
40 tempArray[index]=arr[j];
41 j++;//增加索引
42 }
43 index++;//临时数组增加索引
44 }
45 //处理左边剩余元素
46 while (i<=centerIndex){
47 tempArray[index]=arr[i];
48 i++;
49 index++;
50 }
51 //处理右边剩余元素
52 while (j<=endIndex){
53 tempArray[index]=arr[j];
54 j++;
55 index++;
56 }
57 //遍历临时数组赋值到原始数组
58 for (int m = 0; m ) {
59 arr[m+startIndex]=tempArray[m];
60 }
61 }
62 }