1 public static void main(String[] args)
 2     {
 3         int[] arr = {1, 12, 11, 4, 5, 7, 3, 1, 23, 56, 34, 76, 25};
 4         heapSort(arr);
 5     }
 6 
 7     /**
 8      * 堆排序
 9      * @param arr 待排序的数组
10      */
11     private static void heapSort(int[] arr) {
12         for (int i=arr.length/2; i>=0; i--)
13         {
14             buildHeapTree(arr, i, arr.length);
15         }
16         
17         for (int i=arr.length-1; i>=0; i--)
18         {
19             swap(arr, 0, i);        // 交换根结点和堆树中最后一个结点
20             buildHeapTree(arr, 0, i);    // 再次以下标为0的元素开始构建层次递减的堆树
21         }
22         
23         System.out.println(Arrays.toString(arr));
24     }
25     
26     /**
27      * 构建堆树（满足时一颗完全二叉树，且任何结点大于他的子结点）
28      * @param arr  传入的数组
29      * @param rootIndex 根结点对应的数组下标（即以当前下标作为根结点来将数组中改下标之后的元素作为其子节点的堆树）
30      * @param deep     堆的深度（对于超过堆深度的数组中的元素不进行堆树的构建）
31      */
32     private static void buildHeapTree(int[] arr, int rootIndex, int deep) {
33         int leftChildIndex = rootIndex * 2 + 1;
34         int rightChildIndex = rootIndex * 2 + 2;
35         int maxIndex = rootIndex;
36         if (leftChildIndex < deep && arr[leftChildIndex] > arr[rootIndex])
37         {
38             // 如果左子结点大于右子结点，说明当前最大结点的下标应该为左子结点的下标
39             maxIndex = leftChildIndex;
40         }
41         
42         if (rightChildIndex < deep && arr[rightChildIndex] > arr[maxIndex])
43         {
44             // 如果右子结点的值大于与左子结点比较之后得到的最大的结点的值，则说明最大结点的下标应该为右子结点的下标
45             maxIndex = rightChildIndex;
46         }
47         
48         if (maxIndex != rootIndex)
49         {
50             // 以当前下标从数组中的元素开始没法够造成堆树，此时需要在树中将最大值所在的结点和根结点的位置互换，又因为堆树的构建是自下往上的，互换了之后需要考虑对前面最大值所在堆树的影响，所以需要再次递归调用以前面最大值元素所在位置为根结点构建堆树、
51             swap(arr, maxIndex, rootIndex);
52             buildHeapTree(arr, maxIndex, deep);
53         }
54     }
55 
56     private static void swap(int[] arr, int index1, int index2) {
57         int temp = arr[index1];
58         arr[index1] = arr[index2];
59         arr[index2] = temp;
60     }

 1 public static void main(String[] args)
 2     {
 3         int[] arr = {1, 12, 11, 4, 5, 7, 3, 1, 23, 56, 34, 76, 25};
 4         quickSort(arr);
 5     }
 6 
 7     private static void quickSort(int[] arr) {
 8         divideQuickSort(arr, 0, arr.length - 1);
 9         System.out.println(Arrays.toString(arr));
10     }
11 
12     private static void divideQuickSort(int[] arr, int start, int end) {
13         if (start >= end)
14         {
15             return;
16         }
17         
18         int r = partition(arr, start, end);
19         divideQuickSort(arr, start, r - 1);
20         divideQuickSort(arr, r + 1, end);
21     }
22 
23     /**
24      * 得到快速排序的分割点
25      * @param arr     传入的待排序的数组
26      * @param start  排序的起始元素下标
27      * @param end  排序的终止元素下标
28      * @return          分割点的下标
29      */
30     private static int partition(int[] arr, int start, int end) {
31         // 先要找一个对比的元素，这里取终止元素作为对比的元素
32         int compareValue = arr[end];
33         
34         // 从起始元素到比较元素前一个元素循环与终止元素进行比对
35         int placeStartIndex = start;
36         for (int i = start; i <= end-1; i++)
37         {
38             if (arr[i] < compareValue)
39             {
40                 // 发现比比较元素小的元素，通过交换位置依次从起始元素位置开始摆放
41                 swap(arr, i, placeStartIndex++);
42             }
43         }
44         
45         // 将比较元素放到比它都小的元素的右侧
46         swap(arr, placeStartIndex, end);
47         
48         // 此时返回当前比较元素交换之后的位置
49         return placeStartIndex;
50     }
51     
52     private static void swap(int[] arr, int index1, int index2) {
53         int temp = arr[index1];
54         arr[index1] = arr[index2];
55         arr[index2] = temp;
56     }