复习下排序

2019-03-03 20:47:08
  1. package com.test.sort;
  2. import java.util.Arrays;
  3. import java.util.Random;
  4. public class Main {
  5. public static void main(String[] args) {
  6. int[] arr = generArr(10000);
  7. print(arr);
  8. bubbleSort(arr);
  9. // selectSort(arr);
  10. // insertSort(arr);
  11. // quickSort(arr);
  12. // mergeSort(arr);
  13. // heapSort(arr);
  14. // shellSort(arr);
  15. System.out.println(validator(arr));
  16. print(arr);
  17. }
  18. private static boolean validator(int[] arr) {
  19. int n = arr.length;
  20. for (int i = 1; i < n; i++) {
  21. if (arr[i] < arr[i - 1]) {
  22. return false;
  23. }
  24. }
  25. return true;
  26. }
  27. private static void swap(int[] arr, int x, int y) {
  28. int t = arr[x];
  29. arr[x] = arr[y];
  30. arr[y] = t;
  31. }
  32. private static void print(int[] arr) {
  33. System.out.println(Arrays.toString(arr));
  34. }
  35. private static int[] generArr(int n) {
  36. return new Random().ints(n).toArray();
  37. }
  38. // 冒泡排序
  39. // 时间复杂度:平均 O(n^2) 最好 O(n) 最差 O(n^2)
  40. // 空间复杂度:O(1)
  41. // 稳定
  42. public static void bubbleSort(int[] arr) {
  43. int n = arr.length, end = n - 1;
  44. for (int i = 1; i <= n - 1; i++) {
  45. boolean flag = true;
  46. int pos = 0;
  47. for (int j = 0; j < end; j++) {
  48. if (arr[j] > arr[j + 1]) {
  49. swap(arr, j, j + 1);
  50. flag = false;
  51. pos = j + 1;
  52. }
  53. }
  54. if (flag) {
  55. return;
  56. }
  57. end = pos;
  58. }
  59. }
  60. // 选择排序
  61. // 时间复杂度:平均 O(n^2) 最好 O(n^2) 最差 O(n^2)
  62. // 空间复杂度:O(1)
  63. // 不稳定
  64. public static void selectSort(int[] arr) {
  65. int n = arr.length;
  66. for (int i = 0; i < n - 1; i++) {
  67. int k = i;
  68. for (int j = i + 1; j < n; j++) {
  69. if (arr[j] < arr[k]) {
  70. k = j;
  71. }
  72. }
  73. if (k != i) {
  74. swap(arr, k, i);
  75. }
  76. }
  77. }
  78. // 插入排序
  79. // 时间复杂度:平均 O(n^2) 最好 O(n) 最差 O(n^2)
  80. // 空间复杂度:O(1)
  81. // 稳定
  82. public static void insertSort(int[] arr) {
  83. int n = arr.length;
  84. for (int i = 1; i < n; i++) {
  85. int tmp = arr[i];
  86. for (int j = i - 1; j >= 0; j--) {
  87. if (tmp < arr[j]) {
  88. arr[j + 1] = arr[j];
  89. } else {
  90. arr[j + 1] = tmp;
  91. break;
  92. }
  93. }
  94. }
  95. }
  96. // 快速排序
  97. // 时间复杂度:平均 O(n*logn) 最好 O(n*logn) 最差 O(n^2)
  98. // 空间复杂度:O(logn)
  99. // 不稳定
  100. public static void quickSort(int[] arr) {
  101. quickSort(arr, 0, arr.length - 1);
  102. }
  103. private static void quickSort(int[] arr, int start, int end) {
  104. if (start >= end) {
  105. return;
  106. }
  107. int key = arr[start];
  108. int left = start + 1, right = end;
  109. while (left < right) {
  110. while (left < right && arr[left] <= key) {
  111. left++;
  112. }
  113. while (left < right && arr[right] > key) {
  114. right--;
  115. }
  116. swap(arr, left, right);
  117. }
  118. if (arr[right] > key) {
  119. right--;
  120. }
  121. swap(arr, right, start);
  122. quickSort(arr, start, right - 1);
  123. quickSort(arr, right + 1, end);
  124. }
  125. // 归并排序
  126. // 时间复杂度:平均 O(n*logn) 最好 O(n*logn) 最差 O(n*logn)
  127. // 空间复杂度:O(n)
  128. // 稳定
  129. public static void mergeSort(int[] arr) {
  130. mergeSort(arr, 0, arr.length - 1);
  131. }
  132. private static void mergeSort(int[] arr, int start, int end) {
  133. if (end > start) {
  134. int mid = (start + end) / 2;
  135. mergeSort(arr, start, mid);
  136. mergeSort(arr, mid + 1, end);
  137. merge(arr, start, end);
  138. }
  139. }
  140. private static void merge(int[] arr, int start, int end) {
  141. int mid = (start + end) / 2, i = start, j = mid + 1, k = 0;
  142. int[] tmp = new int[end - start + 1];
  143. while (i <= mid && j <= end) {
  144. if (arr[i] < arr[j]) {
  145. tmp[k++] = arr[i++];
  146. } else {
  147. tmp[k++] = arr[j++];
  148. }
  149. }
  150. while (i <= mid) {
  151. tmp[k++] = arr[i++];
  152. }
  153. while (j <= end) {
  154. tmp[k++] = arr[j++];
  155. }
  156. System.arraycopy(tmp, 0, arr, start, end - start + 1);
  157. }
  158. // 堆排序
  159. // 时间复杂度:平均 O(n*logn) 最好 O(n*logn) 最差 O(n*logn)
  160. // 空间复杂度:O(1)
  161. // 不稳定
  162. public static void heapSort(int[] arr) {
  163. int len = arr.length, n = len - 1, k = (n - 1) / 2;
  164. for (int i = k; i >= 0; i--) {
  165. adjustHeap(arr, i, n);
  166. }
  167. for (int i = n; i > 0; i--) {
  168. swap(arr, 0, i);
  169. adjustHeap(arr, 0, i - 1);
  170. }
  171. }
  172. private static void adjustHeap(int[] arr, int k, int n) {
  173. int j = 2 * k + 1;
  174. while (j <= n) {
  175. if (j < n && arr[j] < arr[j + 1]) {
  176. j++;
  177. }
  178. if (arr[k] < arr[j]) {
  179. swap(arr, k, j);
  180. k = j;
  181. j = 2 * k + 1;
  182. } else {
  183. break;
  184. }
  185. }
  186. }
  187. // 希尔排序
  188. // 时间复杂度:平均 O(n*1.3) 最好 O(n) 最差 O(n^2)
  189. // 空间复杂度:O(1)
  190. // 不稳定
  191. public static void shellSort(int[] arr) {
  192. int[] steps = {1, 5, 19, 41, 109};
  193. int n = arr.length;
  194. for (int i = steps.length - 1; i >= 0; i--) {
  195. int step = steps[i];
  196. for (int j = step; j < n; j += step) {
  197. int k = j - step, tmp = arr[j];
  198. while (k >= 0) {
  199. if (arr[k] > tmp) {
  200. arr[k + step] = arr[k];
  201. k -= step;
  202. } else {
  203. arr[k + step] = tmp;
  204. break;
  205. }
  206. }
  207. }
  208. }
  209. }
  210. }

1
1
0

添加评论

正在回复:
取消
1
1
1
0