java分治排序算法_Java学习笔记——排序算法之进阶排序（堆排序与分治并归排序）...

春蚕到死丝方尽&＃xff0c;蜡炬成灰泪始干

——无题

这里介绍两个比较难的算法&＃xff1a;

1、堆排序

2、分治并归排序

先说堆。

这里请大家先自行了解完全二叉树的数据结构。

堆是完全二叉树。大顶堆是在堆中&＃xff0c;任意双亲值都大于(或等于)其孩子值&＃xff0c;就称其为大顶堆。

堆排序的步骤&＃xff1a;

1、把数组想象成一个堆。数组的index&＃43;1就是其对应在堆中的序号

2、调堆中各值的顺序&＃xff0c;得到大顶堆

3、将堆首位值与堆末尾值交换&＃xff0c;最大值排序完毕

4、将堆得大小减1&＃xff0c;重复步骤2和步骤3&＃xff0c;直到堆中只剩下一个元素。排序完毕

上代码&＃xff1a;

1 public classHeapSort {2

3 public static void heapSort(int[] arr){4 //建立完全二叉树&＃xff0c;从最后一个双亲开始调整双亲值&＃xff0c;直到根&＃xff0c;调整完毕后大顶堆建立完成

5 for (int i &＃61; arr.length >> 1; i > 0; i --) {6 heapAdjust(arr, i, arr.length);//调用堆要从1到length才符合堆的定义

7 }8 //堆顶和堆低交换,获取最大值,然后调整大顶堆

9 for (int i &＃61; arr.length - 1; i > 0; i--) {10 arr[i] &＃61; arr[i]^arr[0];11 arr[0] &＃61; arr[i]^arr[0];12 arr[i] &＃61; arr[i]^arr[0];13 heapAdjust(arr, 1, i);//因为堆计数要从1开始,所以size &＃61; endIndex &＃43; 1

14 }15 }16 //调整大顶堆.先找左子,然后和右子比,取值大的,在和双亲自己比,自己比儿子大,break,否则交换.注意:根要从1开始才能找到左子

17 public static void heapAdjust(int[] arr, int parents, intsize){18 int j;//孩子们的标记是j,索引全部-1

19 int i &＃61; parents;//双亲是i,索引全部-1

20 while (i <<1 <&＃61;size) {21 j &＃61; i <<1;//左子

22 if (j &＃43; 1 <&＃61; size) {//有右子

23 if (arr[j - 1] arr[j - 1])27 break;28 arr[i-1] &＃61; arr[i-1]^arr[j-1];29 arr[j-1] &＃61; arr[i-1]^arr[j-1];30 arr[i-1] &＃61; arr[i-1]^arr[j-1];31 i &＃61; j;//儿子变为父亲,这里不知道是左子还是右子,所以不能直接通过for循环的迭代步骤<

32 }33 }34 }

再说分治并归排序

这里先要了解什么是递归

1 public classMergingTest {2

3 public static voidmain(String[] args) {4 mSort(0, 3);5 }6 private static void mSort(int left, intright) {7 int m &＃61; (left &＃43; right)/2;8 if (left &＃61;&＃61;right) {9 System.out.println(left);10 return;11 }12 mSort(left, m);13 mSort(m&＃43;1, right);14 }15 }

这几行代码是并归算法的核心。运行代码将输出0123456789&＃xff0c;虽然看上去很简单&＃xff0c;但是如果真能明白&＃xff0c;说明你已经完全理解递归的思想了&＃xff0c;写出并归算法也就不在话下了。

为什么会输出0123呢&＃xff1f;

代码执行的走向&＃xff1a;1→2→4→2→5→2→1→3→6→3→7→3→1→return

能领悟这个东西就好办了&＃xff0c;上代码:

1 public classMergingSort {2

3 public static void mergingSort(int[] arr) {4 int[] temp &＃61; new int[arr.length];

//temp是相当于一张牌&＃xff0c;通过left,m,right在逻辑上分成两个数组&＃xff0c;进行分治排序,arr是原数组&＃xff0c;对数组排序不传数组怎么行&＃xff1f;&＃xff01;5 mSort(arr, temp, 0, arr.length-1);6 }7 private static void mSort(int[] arr, int[] temp, int left, intright) {

//这里的分组逻辑没有使用到temp和arr&＃xff0c;而是把它们作为参数传入merge方法8 int m &＃61; (left&＃43;right)/ 2;9 if (left &＃61;&＃61;right) {10 return;11 }12 mSort(arr, temp, left, m);13 mSort(arr, temp, m&＃43;1, right);14 merge(arr,temp,left,m,right);15 }16 private static void merge(int[]arr, int[] temp, int left, int m, intright) {

//分治排序极其简单&＃xff0c;已知两个有序数组&＃xff0c;要把他们合并成一个有序数组&＃xff0c;用什么方法都不用说&＃xff0c;大家一想就知道了。17 for (int c &＃61; 0;c

//使用分支结构&＃xff0c;把每摞牌最小的那个挑出来给arr27 if (temp[i]

//使用分支结构&＃xff0c;把剩下的那摞牌都塞给arr34 if (i >m) {35 while (j <&＃61;right) {36 arr[k&＃43;&＃43;] &＃61; temp[j&＃43;&＃43;];37 }38 }39 if (j >right) {40 while (i <&＃61;m) {41 arr[k&＃43;&＃43;] &＃61; temp[i&＃43;&＃43;];42 }43 }44 }45

46 }