排序算法二（时间复杂度为O(N*logN)）

快速排序：
 1 package test;
 2 
 3 public class QuickSort {
 4     // 快速排序
 5     public void quickSort(int s[], int l, int r) {
 6         if (l < r) {
 7             // Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
 8             int i = l, j = r, x = s[l];
 9             while (i < j) {
10                 while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
11                     j--;
12                 if (i < j)
13                     s[i++] = s[j];
14 
15                 while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
16                     i++;
17                 if (i < j)
18                     s[j--] = s[i];
19             }
20             s[i] = x;
21             quickSort(s, l, i - 1); // 递归调用
22             quickSort(s, i + 1, r);
23         }
24     }
25 
26     public static void main(String[] args) {
27         QuickSort quick = new QuickSort();
28         int[] A = { 1, 2, 3, 5, 2, 3 };
29         quick.quickSort(A, 0, A.length - 1);
30         for (int i = 0; i < A.length; i++) {
31             System.out.println(A[i]);
32         }
33     }
34 
35 }

结果运行如下： 1 2 2 3 3 4 5

其主要思想如下：先从原序列中随机选取一个初始值，然后在剩下的数组中分别找出比其小的元素，将其分别放到两个序列中，以此类推，采用随机+分治的思想

堆排序：

 1 package test;
 2 
 3 public class HeapSortTest {
 4     public static void main(String[] args) {
 5         int[] initialData = { 7, 6, 5, 4, 3, 8, 9 };
 6         HeapSortTest heapSortTest = new HeapSortTest();
 7         System.out.println("排序之前的原始数据：");
 8         heapSortTest.print(initialData);
 9 
10         heapSortTest.heapSort(initialData);
11         System.out.println("
");
12         System.out.println("排序之后的数据：");
13         heapSortTest.print(initialData);
14 
15     }
16 
17     public void heapSort(int[] data) {
18         // 考虑到需要创建多少次堆
19         for (int i = 0; i < data.length - 1; i++) {
20             createMaxHeap(data, data.length - 1 - i);
21             swap(data, 0, data.length - 1 - i);
22             // print(data);
23 
24         }
25     }
26 
27     public void swap(int[] data, int i, int j) {
28         int temp = data[i];
29         data[i] = data[j];
30         data[j] = temp;
31     }
32 
33     public void createMaxHeap(int[] data, int indexMax) {
34         // 需要创建堆
35         for (int currentNode = (indexMax - 1) / 2; currentNode >= 0; currentNode--) {
36             // 找出子节点中的较大值
37             int bigChildNode = 2 * currentNode + 1;
38             // 因为每次更新后
39             // while (bigChildNode<=indexMax)//这里的等号就是只有一个元素时
40             // {
41             if (bigChildNode < indexMax) {
42                 // 选取子节点中较大的那个节点
43                 if (data[2 * currentNode + 1] < data[2 * currentNode + 2]) {
44                     bigChildNode = 2 * currentNode + 2;
45                 }
46             }
47             if (data[currentNode] < data[bigChildNode]) {
48                 swap(data, currentNode, bigChildNode);
49                 // currentNode=bigChildNode;
50             }
51             // else
52             // {
53             // break;
54             // }
55             // }
56 
57         }
58     }
59 
60     public void print(int[] data) {
61         for (int i = 0; i < data.length; i++) {
62             System.out.print(data[i] + "	");
63         }
64 
65     }
66 }

输出结果： 1 排序之前的原始数据： 2 7 6 5 4 3 8 9 3 4 排序之后的数据： 5 3 4 5 6 7 8 9

其主要思想：就是建造堆和更新堆，需要注意的是：每更新一次堆时，实际上下次就会少更新一个元素，即排序序的部分就会多一个元素。