各种排序算法：冒择路(入)兮(稀)快归堆，桶式排序，基数排序
冒泡排序，选择排序，插入排序，稀尔排序，快速排序，归并排序，堆排序，桶式排序，基数排序
一、冒泡排序(BubbleSort)
1. 基本思想：
两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。
2. 排序过程：
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上”漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。
【示例】：
49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97
java代码实现：
04.
05.public class BubbleSort {
06.
07.
14. public void bubble(Integer[] array, int from, int end) {
15. //需array.length – 1轮比较
16. for (int k = 1; k < end – from + 1; k++) {
17. //每轮循环中从最后一个元素开始向前起泡，直到i=k止，即i等于轮次止
18. for (int i = end – from; i >= k; i–) {
19. //按照一种规则（后面元素不能小于前面元素）排序
20. if ((array[i].compareTo(array[i – 1])) < 0) {
21. //如果后面元素小于了（当然是大于还是小于要看比较器实现了）前面的元素，则前后交换
22. swap(array, i, i – 1);
23. }
24. }
25. }
26. }
27.
28.
34. public void swap(Integer[] array, int i, int j) {
35. if (i != j) {//只有不是同一位置时才需交换
36. Integer tmp = array[i];
37. array[i] = array[j];
38. array[j] = tmp;
39. }
40. }
41.
42.
43.
47. public static void main(String[] args) {
48. Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 11, 10 };
49. BubbleSort bubblesort = new BubbleSort();
50. bubblesort.bubble(intgArr,0,intgArr.length-1);
51. for(Integer intObj:intgArr){
52. System.out.print(intObj + ” “);
53. }
54. }
55.}
另外一种实现方式：
public class BubbleSort2{
public static void main(String[] args){
int[] a = {3,5,9,4,7,8,6,1,2};
BubbleSort2 bubble = new BubbleSort2();
bubble.bubble(a);
for(int num:a){
System.out.print(num + ” “);
}
}
public void bubble(int[] a){
for(int i=a.length-1;i>0;i–){
for(int j=0;j<i;j++){
if(new Integer(a[j]).compareTo(new Integer(a[j+1]))>0){
swap(a,j,j+1);
}
}
}
}
public void swap(int[] a,int x,int y){
int temp;
temp=a[x];
a[x]=a[y];
a[y]=temp;
}
}
二、选择排序
1. 基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
2. 排序过程：
【示例】：
初始关键字[49 38 65 97 76 13 27 49]
第一趟排序后13 ［38 65 97 76 49 27 49]
第二趟排序后13 27 ［65 97 76 49 38 49]
第三趟排序后13 27 38 [97 76 49 65 49]
第四趟排序后13 27 38 49 [49 97 65 76]
第五趟排序后13 27 38 49 49 [97 97 76]
第六趟排序后13 27 38 49 49 76 [76 97]
第七趟排序后13 27 38 49 49 76 76 [ 97]
最后排序结果13 27 38 49 49 76 76 97
java代码实现：
01.
04.public class SelectSort {
05.
06.
13. public void select(Integer[] array) {
14. int minIndex;//最小索引
15.
21. for (int i=0; i<array.length; i++) {
22. minIndex = i;//假设每轮第一个元素为最小元素
23. //从假设的最小元素的下一元素开始循环
24. for (int j=i+1;j<array.length; j++) {
25. //如果发现有比当前array[smallIndex]更小元素，则记下该元素的索引于smallIndex中
26. if ((array[j].compareTo(array[minIndex])) < 0) {
27. minIndex = j;
28. }
29. }
30.
31. //先前只是记录最小元素索引，当最小元素索引确定后，再与每轮的第一个元素交换
32. swap(array, i, minIndex);
33. }
34. }
35.
36. public static void swap(Integer[] intgArr,int x,int y){
37. //Integer temp; //这个也行
38. int temp;
39. temp=intgArr[x];
40. intgArr[x]=intgArr[y];
41. intgArr[y]=temp;
42. }
43.
44.
48. public static void main(String[] args) {
49. Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
50. SelectSort insertSort = new SelectSort();
51. insertSort.select(intgArr);
52. for(Integer intObj:intgArr){
53. System.out.print(intObj + ” “);
54. }
55.
56. }
57.}
三、插入排序(Insertion Sort)
1. 基本思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
2. 排序过程：
【示例】：
[初始关键字] [49] 38 65 97 76 13 27 49
J=2(38) [38 49] 65 97 76 13 27 49
J=3(65) [38 49 65] 97 76 13 27 49
J=4(97) [38 49 65 97] 76 13 27 49
J=5(76) [38 49 65 76 97] 13 27 49
J=6(13) [13 38 49 65 76 97] 27 49
J=7(27) [13 27 38 49 65 76 97] 49
J=8(49) [13 27 38 49 49 65 76 97]
java代码实现：
public class InsertSort {
public void insert(Integer[] array, int from, int end) {
for (int i=from+1; i<=end; i++) {
for (int j = 0; j < i; j++) {
Integer insertedElem = array[i];//待插入到有序数组的元素
//从有序数组中最一个元素开始查找第一个大于待插入的元素
if ((array[j].compareTo(insertedElem)) > 0) {
//找到插入点后，从插入点开始向后所有元素后移一位
move(array, j, i – 1);
//将待排序元素插入到有序数组中
array[j] = insertedElem;
break;
}
}
}
//=======以下是java.util.Arrays的插入排序算法的实现
}
public void move(Integer[] array, int startIndex, int endIndex) {
for (int i = endIndex; i >= startIndex; i–) {
array[i+1] = array[i];
}
}
public static void main(String[] args) {
Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
InsertSort insertSort = new InsertSort();
insertSort.insert(intgArr,0,intgArr.length-1);
for(Integer intObj:intgArr){
System.out.print(intObj + ” “);
}
}
}
四、稀尔排序
java代码实现：
01.
06.public class ShellSort {
07.
08.
15. public void sort(Integer[] array, int from, int end) {
16. //初始步长，实质为每轮的分组数
17. int step = initialStep(end – from + 1);
18.
19. //第一层循环是对排序轮次进行循环。(step + 1) / 2 – 1 为下一轮步长值
20. for (; step >= 1; step = (step + 1) / 2 – 1) {
21. //对每轮里的每个分组进行循环
22. for (int groupIndex = 0; groupIndex < step; groupIndex++) {
23.
24. //对每组进行直接插入排序
25. insertSort(array, groupIndex, step, end);
26. }
27. }
28. }
29.
30.
38. public void insertSort(Integer[] array, int groupIndex, int step, int end) {
39. int startIndex = groupIndex;//从哪里开始排序
40. int endIndex = startIndex;//排到哪里
41.
45. while ((endIndex + step) <= end) {
46. endIndex += step;
47. }
48.
49. // i为每小组里的第二个元素开始
50. for (int i = groupIndex + step; i <= end; i += step) {
51. for (int j = groupIndex; j < i; j += step) {
52. Integer insertedElem = array[i];
53. //从有序数组中最一个元素开始查找第一个大于待插入的元素
54. if ((array[j].compareTo(insertedElem)) >= 0) {
55. //找到插入点后，从插入点开始向后所有元素后移一位
56. move(array, j, i – step, step);
57. array[j] = insertedElem;
58. break;
59. }
60. }
61. }
62. }
63.
64.
82. public static int initialStep(int len) {
83.
88. int step = 1;
89.
90. //试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长
91. while ((step + 1) * 2 – 1 < len – 1) {
92. step = (step + 1) * 2 – 1;
93. }
94.
95. System.out.println(“初始步长: ” + step);
96. return step;
97. }
98.
99.
106. protected final void move(Integer[] array, int startIndex, int endIndex, int step) {
107. for (int i = endIndex; i >= startIndex; i -= step) {
108. array[i + step] = array[i];
109. }
110. }
111.
112.
113.
117. public static void main(String[] args) {
118. Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 0 };
119. ShellSort shellSort = new ShellSort();
120. shellSort.sort(intgArr,0,intgArr.length-1);
121. for(Integer intObj:intgArr){
122. System.out.print(intObj + ” “);
123. }
124. }
125.}
五、快速排序（Quick Sort）
1. 基本思想：
在当前无序区R[1..H]中任取一个数据元素作为比较的”基准”(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
2. 排序过程：
【示例】：
初始关键字 ［49 38 65 97 76 13 27 49］
一趟排序之后 ［27 38 13］49 ［76 97 65 49］
二趟排序之后 ［13］27 ［38］49 ［49 65］76 ［97］
三趟排序之后13 27 38 49 49 ［65］76 97
最后的排序结果13 27 38 49 49 65 76 97
各趟排序之后的状态
java代码实现：
01.
04.
05.public class QuickSort {
06.
07.
14. //定义了一个这样的公有方法sort，在这个方法体里面执行私有方法quckSort（这种方式值得借鉴）。
15. public void sort(Integer[] array, int from, int end) {
16. quickSort(array, from, end);
17. }
18.
19.
26. private void quickSort(Integer[] array, int low, int high) {
27.
32. if (low < high) {
33. //对分区进行排序整理
34.
35. //int pivot = partition1(array, low, high);
36. int pivot = partition2(array, low, high);
37. //int pivot = partition3(array, low, high);
38.
39.
44. quickSort(array, low, pivot – 1);
45. quickSort(array, pivot + 1, high);
46. }
47.
48. }
49.
50.
59. private int partition1(Integer[] array, int low, int high) {
60. Integer pivotElem = array[low];//以第一个元素为中枢元素
61. //从前向后依次指向比中枢元素小的元素，刚开始时指向中枢，也是小于与大小中枢的元素的分界点
62. int border = low;
63.
64.
69. for (int i = low + 1; i <= high; i++) {
70. //如果找到一个比中枢元素小的元素
71. if ((array[i].compareTo(pivotElem)) < 0) {
72. swap(array, ++border, i);//border前移，表示有小于中枢元素的元素
73. }
74. }
75.
83. swap(array, border, low);
84. return border;
85. }
86.
87.
96. private int partition2(Integer[] array, int low, int high) {
97. int pivot = low;//中枢元素位置，我们以第一个元素为中枢元素
98. //退出条件这里只可能是low = high
99. while (true) {
100. if (pivot != high) {//如果中枢元素在低指针位置时，我们移动高指针
101. //如果高指针元素小于中枢元素时，则与中枢元素交换
102. if ((array[high].compareTo(array[pivot])) < 0) {
103. swap(array, high, pivot);
104. //交换后中枢元素在高指针位置了
105. pivot = high;
106. } else {//如果未找到小于中枢元素，则高指针前移继续找
107. high–;
108. }
109. } else {//否则中枢元素在高指针位置
110. //如果低指针元素大于中枢元素时，则与中枢元素交换
111. if ((array[low].compareTo(array[pivot])) > 0) {
112. swap(array, low, pivot);
113. //交换后中枢元素在低指针位置了
114. pivot = low;
115. } else {//如果未找到大于中枢元素，则低指针后移继续找
116. low++;
117. }
118. }
119. if (low == high) {
120. break;
121. }
122. }
123. //返回中枢元素所在位置，以便下次分区
124. return pivot;
125. }
126.
127.
136. private int partition3(Integer[] array, int low, int high) {
137. int pivot = low;//中枢元素位置，我们以第一个元素为中枢元素
138. low++;
139. //—-调整高低指针所指向的元素顺序，把小于中枢元素的移到前部分，大于中枢元素的移到后面部分
140. //退出条件这里只可能是low = high
141.
142. while (true) {
143. //如果高指针未超出低指针
144. while (low < high) {
145. //如果低指针指向的元素大于或等于中枢元素时表示找到了，退出，注：等于时也要后移
146. if ((array[low].compareTo(array[pivot])) >= 0) {
147. break;
148. } else {//如果低指针指向的元素小于中枢元素时继续找
149. low++;
150. }
151. }
152.
153. while (high > low) {
154. //如果高指针指向的元素小于中枢元素时表示找到，退出
155. if ((array[high].compareTo(array[pivot])) < 0) {
156. break;
157. } else {//如果高指针指向的元素大于中枢元素时继续找
158. high–;
159. }
160. }
161. //退出上面循环时low = high
162. if (low == high) {
163. break;
164. }
165.
166. swap(array, low, high);
167. }
168.
169. //—-高低指针所指向的元素排序完成后，还得要把中枢元素放到适当的位置
170. if ((array[pivot].compareTo(array[low])) > 0) {
171. //如果退出循环时中枢元素大于了低指针或高指针元素时，中枢元素需与low元素交换
172. swap(array, low, pivot);
173. pivot = low;
174. } else if ((array[pivot].compareTo(array[low])) <= 0) {
175. swap(array, low – 1, pivot);
176. pivot = low – 1;
177. }
178.
179. //返回中枢元素所在位置，以便下次分区
180. return pivot;
181. }
182.
183.
189. public void swap(Integer[] array, int i, int j) {
190. if (i != j) {//只有不是同一位置时才需交换
191. Integer tmp = array[i];
192. array[i] = array[j];
193. array[j] = tmp;
194. }
195. }
196.
197.
201. public static void main(String[] args) {
202. Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
203. QuickSort quicksort = new QuickSort();
204. quicksort.sort(intgArr,0,intgArr.length-1);
205. for(Integer intObj:intgArr){
206. System.out.print(intObj + ” “);
207. }
208. }
209.}
六、归并排序
java代码实现：
**
02.归并排序：里面是一个递归程序，深刻理解之。
03.*/
04.public class MergeSort{
05.
06.
13. public void partition(Integer[] arr, int from, int end) {
14. //划分到数组只有一个元素时才不进行再划分
15. if (from < end) {
16. //从中间划分成两个数组
17. int mid = (from + end) / 2;
18. partition(arr, from, mid);
19. partition(arr, mid + 1, end);
20. //合并划分后的两个数组
21. merge(arr, from, end, mid);
22. }
23. }
24.
25.
34. public void merge(Integer[] arr, int from, int end, int mid) {
35. Integer[] tmpArr = new Integer[10];
36. int tmpArrIndex = 0;//指向临时数组
37. int part1ArrIndex = from;//指向第一部分数组
38. int part2ArrIndex = mid + 1;//指向第二部分数组
39.
40. //由于两部分数组里是有序的，所以每部分可以从第一个元素依次取到最后一个元素，再对两部分
41. //取出的元素进行比较。只要某部分数组元素取完后，退出循环
42. while ((part1ArrIndex <= mid) && (part2ArrIndex <= end)) {
43. //从两部分数组里各取一个进行比较，取最小一个并放入临时数组中
44. if (arr[part1ArrIndex] – arr[part2ArrIndex] < 0) {
45. //如果第一部分数组元素小，则将第一部分数组元素放入临时数组中，并且临时数组指针
46. //tmpArrIndex下移一个以做好下次存储位置准备，前部分数组指针part1ArrIndex
47. //也要下移一个以便下次取出下一个元素与后部分数组元素比较
48. tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
49. } else {
50. //如果第二部分数组元素小，则将第二部分数组元素放入临时数组中
51. tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
52. }
53. }
54. //由于退出循环后，两部分数组中可能有一个数组元素还未处理完，所以需要额外的处理，当然不可
55. //能两部分数组都有未处理完的元素，所以下面两个循环最多只有一个会执行，并且都是大于已放入
56. //临时数组中的元素
57. while (part1ArrIndex <= mid) {
58. tmpArr[tmpArrIndex++] = arr[part1ArrIndex++];
59. }
60. while (part2ArrIndex <= end) {
61. tmpArr[tmpArrIndex++] = arr[part2ArrIndex++];
62. }
63.
64. //最后把临时数组拷贝到源数组相同的位置
65. System.arraycopy(tmpArr, 0, arr, from, end – from + 1);
66. }
67.
68.
72. public static void main(String[] args) {
73. Integer[] intgArr = {5,9,1,4,2,6,3,8,0,7};
74. MergeSort insertSort = new MergeSort();
75. insertSort.partition(intgArr,0,intgArr.length-1);
76. for(Integer a:intgArr){
77. System.out.print(a + ” “);
78. }
79. }
80.}
七、堆排序(Heap Sort)
1. 基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2. 堆的定义: N个元素的序列K1,K2,K3,…,Kn.称为堆，当且仅当该序列满足特性：
Ki≤K2i Ki ≤K2i+1(1≤I≤[N/2])
堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。
3. 排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆
java代码实现：
01.
04.public class HeapSort {
05.
06.
13. public void sort(Integer[] array, int from, int end) {
14. //创建初始堆
15. initialHeap(array, from, end);
16.
17.
21. for (int i = end – from + 1; i >= 2; i–) {
22. //根节点与最后一个叶子节点交换位置，即数组中的第一个元素与最后一个元素互换
23. swap(array, from, i – 1);
24. //交换后需要重新调整堆
25. adjustNote(array, 1, i – 1);
26. }
27.
28. }
29.
30.
39. private void initialHeap(Integer[] arr, int from, int end) {
40. int lastBranchIndex = (end – from + 1) / 2;//最后一个非叶子节点
41. //对所有的非叶子节点进行循环 ，且从最一个非叶子节点开始
42. for (int i = lastBranchIndex; i >= 1; i–) {
43. adjustNote(arr, i, end – from + 1);
44. }
45. }
46.
47.
54. private void adjustNote(Integer[] arr, int parentNodeIndex, int len) {
55. int minNodeIndex = parentNodeIndex;
56. //如果有左子树，i * 2为左子节点索引
57. if (parentNodeIndex * 2 <= len) {
58. //如果父节点小于左子树时
59. if ((arr[parentNodeIndex – 1].compareTo(arr[parentNodeIndex * 2 – 1])) < 0) {
60. minNodeIndex = parentNodeIndex * 2;//记录最大索引为左子节点索引
61. }
62.
63. // 只有在有或子树的前提下才可能有右子树，再进一步断判是否有右子树
64. if (parentNodeIndex * 2 + 1 <= len) {
65. //如果右子树比最大节点更大
66. if ((arr[minNodeIndex – 1].compareTo(arr[(parentNodeIndex * 2 + 1) – 1])) < 0) {
67. minNodeIndex = parentNodeIndex * 2 + 1;//记录最大索引为右子节点索引
68. }
69. }
70. }
71.
72. //如果在父节点、左、右子节点三都中，最大节点不是父节点时需交换，把最大的与父节点交换，创建大顶堆
73. if (minNodeIndex != parentNodeIndex) {
74. swap(arr, parentNodeIndex – 1, minNodeIndex – 1);
75. //交换后可能需要重建堆，原父节点可能需要继续下沉
76. if (minNodeIndex * 2 <= len) {//是否有子节点，注，只需判断是否有左子树即可知道
77. adjustNote(arr, minNodeIndex, len);
78. }
79. }
80. }
81.
82.
88. public void swap(Integer[] array, int i, int j) {
89. if (i != j) {//只有不是同一位置时才需交换
90. Integer tmp = array[i];
91. array[i] = array[j];
92. array[j] = tmp;
93. }
94. }
95.
96.
100. public static void main(String[] args) {
101. Integer[] intgArr = { 5, 9, 1, 4, 2, 6, 3, 8, 0, 7 };
102. HeapSort heapsort = new HeapSort();
103. heapsort.sort(intgArr,0,intgArr.length-1);
104. for(Integer intObj:intgArr){
105. System.out.print(intObj + ” “);
106. }
107. }
108.
109.}
八、桶式排序
java代码实现：
01.
11.public class BucketSort {
12. public void sort(int[] keys,int from,int len,int max)
13. {
14. int[] temp=new int[len];
15. int[] count=new int[max];
16.
17.
18. for(int i=0;i<len;i++)
19. {
20. count[keys[from+i]]++;
21. }
22. //calculate position info
23. for(int i=1;i<max;i++)
24. {
25. count[i]=count[i]+count[i-1];//这意味着有多少数目小于或等于i，因此它也是position+ 1
26. }
27.
28. System.arraycopy(keys, from, temp, 0, len);
29. for(int k=len-1;k>=0;k–)//从最末到开头保持稳定性
30. {
31. keys[–count[temp[k]]]=temp[k];// position +1 =count
32. }
33. }
34.
37. public static void main(String[] args) {
38.
39. int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};
40. BucketSort bucketSort=new BucketSort();
41. bucketSort.sort(a,0,a.length,20);//actually is 18, but 20 will also work
42.
43.
44. for(int i=0;i<a.length;i++)
45. {
46. System.out.print(a[i]+”,”);
47. }
48.
49. }
50.
51.
52.}
九、基数排序
java代码实现：
01.
04.import java.util.Arrays;
05.public class RadixSort {
06.
07.
13. public int digit(long x, long d) {
14.
15. long pow = 1;
16. while (–d > 0) {
17. pow *= 10;
18. }
19. return (int) (x / pow % 10);
20. }
21.
22.
30. public long[] radixSortAsc(long[] arr) {
31. //从低位往高位循环
32. for (int d = 1; d <= getMax(arr); d++) {
33. //临时数组，用来存放排序过程中的数据
34. long[] tmpArray = new long[arr.length];
35. //位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个..是9的有多少个数
36. int[] count = new int[10];
37. //开始统计0有多少个，并存储在第0位，再统计1有多少个，并存储在第1位..依次统计到9有多少个
38. for (int i = 0; i < arr.length; i++) {
39. count[digit(arr[i], d)] += 1;
40. }
41.
48. for (int i = 1; i < 10; i++) {
49. count[i] += count[i – 1];
50. }
51.
52.
62. for (int i = arr.length – 1; i >= 0; i–) {//只能从最后一个元素往前处理
63. //for (int i = 0; i < arr.length; i++) {//不能从第一个元素开始循环
64. tmpArray[count[digit(arr[i], d)] – 1] = arr[i];
65. count[digit(arr[i], d)]–;
66. }
67.
68. System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
69. }
70. return arr;
71. }
72.
73.
80. public long[] radixSortDesc(long[] arr) {
81. for (int d = 1; d <= getMax(arr); d++) {
82. long[] tmpArray = new long[arr.length];
83. //位记数器，从第0个元素到第9个元素依次用来记录当前比较位是9的有多少个..是0的有多少个数
84. int[] count = new int[10];
85. //开始统计0有多少个，并存储在第9位，再统计1有多少个，并存储在第8位..依次统计
86. //到9有多少个，并存储在第0位
87. for (int i = 0; i < arr.length; i++) {
88. count[9 – digit(arr[i], d)] += 1;
89. }
90.
91. for (int i = 1; i < 10; i++) {
92. count[i] += count[i – 1];
93. }
94.
95. for (int i = arr.length – 1; i >= 0; i–) {
96. tmpArray[count[9 – digit(arr[i], d)] – 1] = arr[i];
97. count[9 – digit(arr[i], d)]–;
98. }
99.
100. System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
101. }
102. return arr;
103. }
104.
105. private int getMax(long[] array) {
106. int maxlIndex = 0;
107. for (int j = 1; j < array.length; j++) {
108. if (array[j] > array[maxlIndex]) {
109. maxlIndex = j;
110. }
111. }
112. return String.valueOf(array[maxlIndex]).length();
113. }
114.
115. public static void main(String[] args) {
116. long[] ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
117. RadixSort rs = new RadixSort();
118. System.out.println(“升- ” + Arrays.toString(rs.radixSortAsc(ary)));
119.
120. ary = new long[] { 123, 321, 132, 212, 213, 312, 21, 223 };
121. System.out.println(“降- ” + Arrays.toString(rs.radixSortDesc(ary)));
122. }
123.}
十、几种排序算法的比较和选择
1. 选取排序方法需要考虑的因素：
(1) 待排序的元素数目n；
(2) 元素本身信息量的大小；
(3) 关键字的结构及其分布情况；
(4) 语言工具的条件，辅助空间的大小等。
2. 小结：
(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。
(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。
(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于”比较”的排序算法，至少需要O(nlog2n)的时间。
(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
排序简介
排序是数据处理中经常使用的一种重要运算,在计算机及其应用系统中,花费在排序上的时间在系统运行时间中占有很大比重;并且排序本身对推动算法分析的发展也起很大作用。目前已有上百种排序方法，但尚未有一个最理想的尽如人意的方法，本章介绍常用的如下排序方法，并对它们进行分析和比较。
1、插入排序（直接插入排序、折半插入排序、希尔排序）；
2、交换排序（起泡排序、快速排序）；
3、选择排序（直接选择排序、堆排序）；
4、归并排序；
5、基数排序；
学习重点
1、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；
2、掌握插入排序(直接插入排序、折半插入排序、希尔排序)、交换排序（起泡排序、快速排序）、选择排序（直接选择排序、堆排序）、二路归并排序的方法及其性能分析方法；
3、了解基数排序方法及其性能分析方法。
排序（sort）或分类
所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
1．被排序对象–文件
被排序的对象–文件由一组记录组成。
记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字(Key)。
注意：
在不易产生混淆时，将关键字项简称为关键字。
2．排序运算的依据–关键字
用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。
关键字的选取应根据问题的要求而定。
【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用”准考证号”作为关键字。若要按照考生的总分数排名次，则需用”总分数”作为关键字。
排序的稳定性
当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
注意：
排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。
排序方法的分类
1．按是否涉及数据的内、外存交换分
在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。
注意：
① 内排序适用于记录个数不很多的小文件
② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。
2．按策略划分内部排序方法
可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。
排序算法分析
1．排序算法的基本操作
大多数排序算法都有两个基本的操作：
(1) 比较两个关键字的大小；
(2) 改变指向记录的指针或移动记录本身。
注意：
第(2)种基本操作的实现依赖于待排序记录的存储方式。
2．待排文件的常用存储方式
（1） 以顺序表(或直接用向量)作为存储结构
排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）
（2） 以链表作为存储结构
排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表(或链式)排序；
（3） 用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)
排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。
3．排序算法性能评价
（1） 评价排序算法好坏的标准
评价排序算法好坏的标准主要有两条：
① 执行时间和所需的辅助空间
② 算法本身的复杂程度
（2） 排序算法的空间复杂度
若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。
非就地排序一般要求的辅助空间为O(n)。
（3） 排序算法的时间开销
大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
文件的顺序存储结构表示
#define n l00 //假设的文件长度，即待排序的记录数目
typedef int KeyType；//假设的关键字类型
typedef struct{ //记录类型
KeyType key；//关键字项
InfoType otherinfo；//其它数据项，类型InfoType依赖于具体应用而定义
}RecType；
typedef RecType SeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵
注意：
若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。
【例】关键字为字符串时，可定义宏”#define LT(a，b)(Stromp((a)，(b))<0)”。那么算法中”a<b”可用”LT(a，b)”取代。若使用C++，则定义重载的算符”<“更为方便。
按平均时间将排序分为四类：
（1）平方阶(O(n2))排序
一般称为简单排序，例如直接插入、直接选择和冒泡排序；
（2）线性对数阶(O(nlgn))排序
如快速、堆和归并排序；
（3）O(n1+￡)阶排序
￡是介于0和1之间的常数，即0<￡<1，如希尔排序；
（4）线性阶(O(n))排序
如桶、箱和基数排序。
各种排序方法比较
简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。
影响排序效果的因素
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
①待排序的记录数目n；
②记录的大小(规模)；
③关键字的结构及其初始状态；
④对稳定性的要求；
⑤语言工具的条件；
⑥存储结构；
⑦时间和辅助空间复杂度等。
不同条件下，排序方法的选择
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。
4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。
当文件的n个关键字随机分布时，任何借助于”比较”的排序算法，至少需要O(nlgn)的时间。
箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键字)时，无法使用箱排序和基数排序，这时只有借助于”比较”的方法来排序。
若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。
(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。
(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交换R[i]和R[j]，则只需交换t[i]和t[j]即可；排序结束后，向量t就指示了记录之间的顺序关系：
R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key
若要求最终结果是：
R[0].key≤R[1].key≤…≤R[n-1].key
则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。
001
//插入排序:
002
003
package org.rut.util.algorithm.support;
004
005
import org.rut.util.algorithm.SortUtil;
006
011
public class InsertSort implements SortUtil.Sort{
012
013
016
public void sort(int[] data) {
017
int temp;
018
for(int i=1;i<data.length;i++){
019
for(int j=i;(j>0)&&(data[j]<data[j-1]);j–){
020
SortUtil.swap(data,j,j-1);
021
}
022
}
023
}
024
025
}
026
//冒泡排序:
027
028
029
for(var i=0; i<arr.length; i++) {
030
for(var j=i+1; j<=arr.length-1; j++) {
031
if(eval(arr[i]) < eval(arr[j])) {
032
temp = arr[i];
033
arr[i] = arr[j];
034
arr[j] = temp;
035
}
036
}
037
}
038
039
040
041
package org.rut.util.algorithm.support;
042
043
import org.rut.util.algorithm.SortUtil;
044
045
050
public class BubbleSort implements SortUtil.Sort{
051
052
055
public void sort(int[] data) {
056
int temp;
057
for(int i=0;i<data.length;i++){
058
for(int j=data.length-1;j>i;j–){
059
if(data[j]<data[j-1]){
060
SortUtil.swap(data,j,j-1);
061
}
062
}
063
}
064
}
065
066
}
067
068
//选择排序:
069
070
package org.rut.util.algorithm.support;
071
072
import org.rut.util.algorithm.SortUtil;
073
074
079
public class SelectionSort implements SortUtil.Sort {
080
081
086
public void sort(int[] data) {
087
int temp;
088
for (int i = 0; i < data.length; i++) {
089
int lowIndex = i;
090
for (int j = data.length – 1; j > i; j–) {
091
if (data[j] < data[lowIndex]) {
092
lowIndex = j;
093
}
094
}
095
SortUtil.swap(data,i,lowIndex);
096
}
097
}
098
099
}
100
101
//Shell排序:
102
103
package org.rut.util.algorithm.support;
104
105
import org.rut.util.algorithm.SortUtil;
106
107
112
public class ShellSort implements SortUtil.Sort{
113
114
117
public void sort(int[] data) {
118
for(int i=data.length/2;i>2;i/=2){
119
for(int j=0;j<i;j++){
120
insertSort(data,j,i);
121
}
122
}
123
insertSort(data,0,1);
124
}
125
126
131
private void insertSort(int[] data, int start, int inc) {
132
int temp;
133
for(int i=start+inc;i<data.length;i+=inc){
134
for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
135
SortUtil.swap(data,j,j-inc);
136
}
137
}
138
}
139
140
}
141
142
//快速排序:
143
144
package org.rut.util.algorithm.support;
145
146
import org.rut.util.algorithm.SortUtil;
147
148
153
public class QuickSort implements SortUtil.Sort{
154
155
158
public void sort(int[] data) {
159
quickSort(data,0,data.length-1);
160
}
161
private void quickSort(int[] data,int i,int j){
162
int pivotIndex=(i+j)/2;
163
//swap
164
SortUtil.swap(data,pivotIndex,j);
165
166
int k=partition(data,i-1,j,data[j]);
167
SortUtil.swap(data,k,j);
168
if((k-i)>1) quickSort(data,i,k-1);
169
if((j-k)>1) quickSort(data,k+1,j);
170
171
}
172
178
private int partition(int[] data, int l, int r,int pivot) {
179
do{
180
while(data[++l]<pivot);
181
while((r!=0)&&data[–r]>pivot);
182
SortUtil.swap(data,l,r);
183
}
184
while(l<r);
185
SortUtil.swap(data,l,r);
186
return l;
187
}
188
189
}
190
//改进后的快速排序:
191
192
package org.rut.util.algorithm.support;
193
194
import org.rut.util.algorithm.SortUtil;
195
196
201
public class ImprovedQuickSort implements SortUtil.Sort {
202
203
private static int MAX_STACK_SIZE=4096;
204
private static int THRESHOLD=10;
205
208
public void sort(int[] data) {
209
int[] stack=new int[MAX_STACK_SIZE];
210
211
int top=-1;
212
int pivot;
213
int pivotIndex,l,r;
214
215
stack[++top]=0;
216
stack[++top]=data.length-1;
217
218
while(top>0){
219
int j=stack[top–];
220
int i=stack[top–];
221
222
pivotIndex=(i+j)/2;
223
pivot=data[pivotIndex];
224
225
SortUtil.swap(data,pivotIndex,j);
226
227
//partition
228
l=i-1;
229
r=j;
230
do{
231
while(data[++l]<pivot);
232
while((r!=0)&&(data[–r]>pivot));
233
SortUtil.swap(data,l,r);
234
}
235
while(l<r);
236
SortUtil.swap(data,l,r);
237
SortUtil.swap(data,l,j);
238
239
if((l-i)>THRESHOLD){
240
stack[++top]=i;
241
stack[++top]=l-1;
242
}
243
if((j-l)>THRESHOLD){
244
stack[++top]=l+1;
245
stack[++top]=j;
246
}
247
248
}
249
//new InsertSort().sort(data);
250
insertSort(data);
251
}
252
255
private void insertSort(int[] data) {
256
int temp;
257
for(int i=1;i<data.length;i++){
258
for(int j=i;(j>0)&&(data[j]<data[j-1]);j–){
259
SortUtil.swap(data,j,j-1);
260
}
261
}
262
}
263
264
}
265
266
//归并排序:
267
268
package org.rut.util.algorithm.support;
269
270
import org.rut.util.algorithm.SortUtil;
271
272
277
public class MergeSort implements SortUtil.Sort{
278
279
282
public void sort(int[] data) {
283
int[] temp=new int[data.length];
284
mergeSort(data,temp,0,data.length-1);
285
}
286
287
private void mergeSort(int[] data,int[] temp,int l,int r){
288
int mid=(l+r)/2;
289
if(l==r) return ;
290
mergeSort(data,temp,l,mid);
291
mergeSort(data,temp,mid+1,r);
292
for(int i=l;i<=r;i++){
293
temp[i]=data[i];
294
}
295
int i1=l;
296
int i2=mid+1;
297
for(int cur=l;cur<=r;cur++){
298
if(i1==mid+1)
299
data[cur]=temp[i2++];
300
else if(i2>r)
301
data[cur]=temp[i1++];
302
else if(temp[i1]<temp[i2])
303
data[cur]=temp[i1++];
304
else
305
data[cur]=temp[i2++];
306
}
307
}
308
309
}
310
311
//改进后的归并排序:
312
313
package org.rut.util.algorithm.support;
314
315
import org.rut.util.algorithm.SortUtil;
316
317
322
public class ImprovedMergeSort implements SortUtil.Sort {
323
324
private static final int THRESHOLD = 10;
325
326
331
public void sort(int[] data) {
332
int[] temp=new int[data.length];
333
mergeSort(data,temp,0,data.length-1);
334
}
335
336
private void mergeSort(int[] data, int[] temp, int l, int r) {
337
int i, j, k;
338
int mid = (l + r) / 2;
339
if (l == r)
340
return;
341
if ((mid – l) >= THRESHOLD)
342
mergeSort(data, temp, l, mid);
343
else
344
insertSort(data, l, mid – l + 1);
345
if ((r – mid) > THRESHOLD)
346
mergeSort(data, temp, mid + 1, r);
347
else
348
insertSort(data, mid + 1, r – mid);
349
350
for (i = l; i <= mid; i++) {
351
temp[i] = data[i];
352
}
353
for (j = 1; j <= r – mid; j++) {
354
temp[r – j + 1] = data[j + mid];
355
}
356
int a = temp[l];
357
int b = temp[r];
358
for (i = l, j = r, k = l; k <= r; k++) {
359
if (a < b) {
360
data[k] = temp[i++];
361
a = temp[i];
362
} else {
363
data[k] = temp[j–];
364
b = temp[j];
365
}
366
}
367
}
368
369
374
private void insertSort(int[] data, int start, int len) {
375
for(int i=start+1;i<start+len;i++){
376
for(int j=i;(j>start) && data[j]<data[j-1];j–){
377
SortUtil.swap(data,j,j-1);
378
}
379
}
380
}
381
382
}
383
//堆排序:
384
385
package org.rut.util.algorithm.support;
386
387
import org.rut.util.algorithm.SortUtil;
388
389
394
public class HeapSort implements SortUtil.Sort{
395
396
399
public void sort(int[] data) {
400
MaxHeap h=new MaxHeap();
401
h.init(data);
402
for(int i=0;i<data.length;i++)
403
h.remove();
404
System.arraycopy(h.queue,1,data,0,data.length);
405
}
406
407
408
private static class MaxHeap{
409
410
411
void init(int[] data){
412
this.queue=new int[data.length+1];
413
for(int i=0;i<data.length;i++){
414
queue[++size]=data[i];
415
fixUp(size);
416
}
417
}
418
419
private int size=0;
420
421
private int[] queue;
422
423
public int get() {
424
return queue[1];
425
}
426
427
public void remove() {
428
SortUtil.swap(queue,1,size–);
429
fixDown(1);
430
}
431
//fixdown
432
private void fixDown(int k) {
433
int j;
434
while ((j = k << 1) <= size) {
435
if (j < size && queue[j]<queue[j+1])
436
j++;
437
if (queue[k]>queue[j]) //不用交换
438
break;
439
SortUtil.swap(queue,j,k);
440
k = j;
441
}
442
}
443
private void fixUp(int k) {
444
while (k > 1) {
445
int j = k >> 1;
446
if (queue[j]>queue[k])
447
break;
448
SortUtil.swap(queue,j,k);
449
k = j;
450
}
451
}
452
453
}
454
455
}
456
457
458
459
//SortUtil:
460
461
package org.rut.util.algorithm;
462
463
import org.rut.util.algorithm.support.BubbleSort;
464
import org.rut.util.algorithm.support.HeapSort;
465
import org.rut.util.algorithm.support.ImprovedMergeSort;
466
import org.rut.util.algorithm.support.ImprovedQuickSort;
467
import org.rut.util.algorithm.support.InsertSort;
468
import org.rut.util.algorithm.support.MergeSort;
469
import org.rut.util.algorithm.support.QuickSort;
470
import org.rut.util.algorithm.support.SelectionSort;
471
import org.rut.util.algorithm.support.ShellSort;
472
473
478
public class SortUtil {
479
public final static int INSERT = 1;
480
481
public final static int BUBBLE = 2;
482
483
public final static int SELECTION = 3;
484
485
public final static int SHELL = 4;
486
487
public final static int QUICK = 5;
488
489
public final static int IMPROVED_QUICK = 6;
490
491
public final static int MERGE = 7;
492
493
public final static int IMPROVED_MERGE = 8;
494
495
public final static int HEAP = 9;
496
497
public static void sort(int[] data) {
498
sort(data, IMPROVED_QUICK);
499
}
500
private static String[] name={
501
“insert”,”bubble”,”selection”,”shell”,”quick”,”improved_quick”,”merge”,”improved_merge”,”heap”
502
};
503
504
private static Sort[] impl=new Sort[]{
505
new InsertSort(),
506
new BubbleSort(),
507
new SelectionSort(),
508
new ShellSort(),
509
new QuickSort(),
510
new ImprovedQuickSort(),
511
new MergeSort(),
512
new ImprovedMergeSort(),
513
new HeapSort()
514
};
515
516
public static String toString(int algorithm){
517
return name[algorithm-1];
518
}
519
520
public static void sort(int[] data, int algorithm) {
521
impl[algorithm-1].sort(data);
522
}
523
524
public static interface Sort {
525
public void sort(int[] data);
526
}
527
528
public static void swap(int[] data, int i, int j) {
529
int temp = data[i];
530
data[i] = data[j];
531
data[j] = temp;
532
}
533
}
