Classification:
1) insertion sort (direct insertion sort, hill sorting) 2) exchange sort, bubble sort, quick sort) 3) selection sort (direct selection sort, heap sort) 4) 5) merge sort distribution sorting (radix sort required auxiliary space most: merge sort required auxiliary space at least: heap sort average fastest: quick sort \
Unstable: quicksort, Hill sort, heap sort.
支那
支那
Private static final int[] NUMBERS = {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, private static final int[] NUMBERS = {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};Copy the code1. Insert sort \ directly
Basic idea: In the set of numbers to be sorted, assume that the preceding (n-1)[n>=2] number is already a row
Okay, so now we’re going to insert the NTH number into the ordered number, so that this n number
It’s also in order. Repeat until everything is sorted.
\
\
1 public static void insertSort(int[] array) { 2 for (int i = 1; i < array.length; i++) { 3 int temp = array[i]; 4 int j = i - 1; 5 for (; j >= 0 && array[j] > temp; J --) {6 array[j + 1] = array[j]; 8 } 9 array[j + 1] = temp; 10 } 11 System.out.println(Arrays.toString(array) + " insertSort"); 12}Copy the code2 .Hill sorting
Hill sort, also known as the descending incremental sort algorithm, is a more efficient and improved version of insertion sort. Hill sort is an unstable sort algorithm. Hill sort is based on the following two properties of insertion sort: insertion sort has high efficiency in the operation of almost ordered data, that is, it can achieve the efficiency of linear sort; But insert sort is generally inefficient because it can only move data one bit at a time. First take a positive integer d1 < n, put all the records separated by D1 into a group, and perform direct insertion sort in each group; Then d2 < d1, repeat the grouping and sorting operations above; Until di = 1, that is, all records are sorted in a group.
\
\
1 public static void shellSort(int[] array) { 2 int i; 3 int j; 4 int temp; 5 int gap = 1; 6 int len = array.length; 7 while (gap < len / 3) { gap = gap * 3 + 1; } 8 for (; gap > 0; gap /= 3) { 9 for (i = gap; i < len; i++) { 10 temp = array[i]; 11 for (j = i - gap; j >= 0 && array[j] > temp; j -= gap) { 12 array[j + gap] = array[j]; 13 } 14 array[j + gap] = temp; 15 } 16 } 17 System.out.println(Arrays.toString(array) + " shellSort"); 18}Copy the code3 .Simple selection sort
Basic idea: in a set of numbers to be sorted, select the smallest number and the number of the first position exchange;
Then find the smallest of the remaining numbers to swap with the second position, and cycle until the penultimate number is compared to the last number.
\
\
1 public static void selectSort(int[] array) { 2 int position = 0; 3 for (int i = 0; i < array.length; i++) { 4 int j = i + 1; 5 position = i; 6 int temp = array[i]; 7 for (; j < array.length; j++) { 8 if (array[j] < temp) { 9 temp = array[j]; 10 position = j; 11 } 12 } 13 array[position] = array[i]; 14 array[i] = temp; 15 } 16 System.out.println(Arrays.toString(array) + " selectSort"); 17}Copy the code4 .Heap sort
Basic idea: heap sort is a tree selection sort, which is an effective improvement on direct selection sort.
A heap is defined as follows: a sequence of n elements (H1, H2… , hn), if and only if meet > = 2 (hi > = h2i, hi I + 1) or (hi < < = h2i, hi = 2 + 1) I (I = 1, 2,… N /2) is called the heap. Only heaps that satisfy the former condition are discussed here. From the definition of the heap, the top element (that is, the first element) must be the largest item (the big top heap). A complete binary tree can represent the structure of a heap intuitively. The top of the heap is the root, and the rest are left and right subtrees. Start by thinking of the sequence of numbers to be sorted as a sequential binary tree, and adjust their storage order so that it becomes a heap, where the root node of the heap is the largest. The root node is then swapped with the last node of the heap. And then rearrange the n minus 1 number to make it a heap. And so on, until you have a heap of only two nodes, and you swap them, and you end up with an ordered sequence of n nodes. According to the algorithm description, heap sort requires two processes, one is to build the heap, and the other is to exchange the position of the top and the last element of the heap. So heapsort consists of two functions. One is the infiltration function that builds the heap, and the other is the function that calls the infiltration function repeatedly to achieve sorting.
\
Building pile:
\
Swap, kick the maximum number out of the heap
\
The remaining nodes are then heaped and switched to kick out the maximum number
\
And so on: the last two remaining nodes in the heap are swapped, one is kicked out, and the sorting is complete.
1 public static void heapSort(int[] array) {2 /* 3 * beginIndex = first non-leaf node. 5 * Start with the first non-leaf node. You don't need to start at the last leaf node. The 6 * leaf node can be considered as a heap-compliant node, and the root node is itself and has a maximum value below. 7 */ 8 int len = array.length - 1; 9 int beginIndex = (len - 1) >> 1; 10 for (int i = beginIndex; i >= 0; i--) { 11 maxHeapify(i, len, array); Step 2: Sort the heapified data 15 * every time, remove the topmost root node A[0] and swap the position with the tailmost node, while traversing length -1. 16 * Then rearrange the last element that has been swapped to the root node to conform to the characteristics of the heap. 17 * until the unsorted heap length is 0. 18 */ 19 for (int i = len; i > 0; i--) { 20 swap(0, i, array); 21 maxHeapify(0, i - 1, array); 22 } 23 System.out.println(Arrays.toString(array) + " heapSort"); 24 } 25 private static void swap(int i, int j, int[] arr) { 26 int temp = arr[i]; 27 arr[i] = arr[j]; 28 arr[j] = temp; 29} 30 /** 31 * Adjusts the data at index to match the characteristics of the heap. 32 * 33 * @param len Length of unsorted heap 35 */ 36 private static void maxHeapify(int index, int len, int[] arr) { 37 int li = (index << 1) + 1; Int ri = li + 1; Int cMax = li; // Maximum index of child value, default left child. 40 if (li > len) { 41 return; // The index of the left child node is out of the calculation range. 42} 43 if (ri <= len && arr[ri] > arr[li]) 44 { cMax = ri; } 45 if (arr[cMax] > arr[index]) { 46 swap(cMax, index, arr); // If the parent node is switched, 47 maxHeapify(cMax, len, arr); // Then you need to continue to determine whether the replaced parent complies with the characteristics of the heap. 49 48}}Copy the code5 .Bubble sort
Basic idea: In a set of numbers to be sorted, compare and adjust the two adjacent numbers from top to bottom for all the numbers that are not yet sorted, so that the larger number sinks and the smaller one rises. That is, whenever two adjacent numbers are compared and find that their sort is the opposite of the sort required, they are swapped.
\
1 public static void bubbleSort(int[] array) { 2 int temp = 0; 3 for (int i = 0; i < array.length - 1; i++) { 4 for (int j = 0; j < array.length - 1 - i; j++) { 5 if (array[j] > array[j + 1]) { 6 temp = array[j]; 7 array[j] = array[j + 1]; 8 array[j + 1] = temp; 9 } 10 } 11 } 12 System.out.println(Arrays.toString(array) + " bubbleSort"); 13}Copy the code6. Quicksort
Basic idea: select a base element, usually choose the first or the last element, a trip through scanning, will stay sequence is divided into two parts, part is smaller than base element, element part of the greater than or equal to the benchmark, the benchmark elements in its correct position after the sorted, and then use the same method recursively sort divided into two parts.
\
1 public static void quickSort(int[] array) { 2 _quickSort(array, 0, array.length - 1); 3 System.out.println(Arrays.toString(array) + " quickSort"); 4 } 5 6 7 private static int getMiddle(int[] list, int low, int high) { 8 int tmp = list[low]; 9 while (low < high) {10 while (low < high && list[high] >= TMP) {11 high--; 12 } 13 14 15 list[low] = list[high]; 16 while (low < high && list[low] <= TMP) {17 low++; 18 } 19 20 21 list[high] = list[low]; 22} 23 list[low] = TMP; // return low; Private static void _quickSort(int[] list, int low, private static void _quickSort(int[] list, int low, int high) { 29 if (low < high) { 30 int middle = getMiddle(list, low, high); 31 _quickSort(list, low, middle-1); 32 _quickSort(list, middle + 1, high); // Select * from the list where the list is sorted.Copy the codeMerge sort
Merge A sort is a merging of two (or more) ordered tables into a new ordered table. That is, the sequence to be sorted is divided into subsequences, each of which is ordered. Then the ordered subsequence is combined into a whole ordered sequence.
\
1 public static void mergingSort(int[] array) { 2 sort(array, 0, array.length - 1); 3 System.out.println(Arrays.toString(array) + " mergingSort"); 4 } 5 6 private static void sort(int[] data, int left, Int center = (left + right) / 2; int center = (left + right) / 2; 11 sort(data, left, center); Sort (data, center + 1, right); 15 merge(data, left, center, right); 16 } 17 } 18 19 private static void merge(int[] data, int left, int center, int right) { 20 int[] tmpArr = new int[data.length]; 21 int mid = center + 1; Int third = left; 24 int tmp = left; 27 if (data[left] <= data[mid]) {28 tmpArr[third++] = data[left++]; 29 } else { 30 tmpArr[third++] = data[mid++]; While (mid <= right) {36 tmpArr[third++] = data[mid++]; 37 } 38 39 while (left <= center) { 40 tmpArr[third++] = data[left++]; 44 while (TMP <= right) {45 data[TMP] = tmpArr[TMP ++]; 47 46}}Copy the code
8. Radix sort
Basic idea: unify all the values to be compared (positive integer) into the same digit length, and fill zeros in front of the shorter digit. Then, sort the order one by one, starting with the lowest order. So from the lowest order to the highest order, the sequence becomes an ordered sequence.
\
1 public static void radixSort(int[] array) {2 public static void radixSort(int[] array) {3 public static void radixSort(int[] array) { 3 int max = array[0]; 4 for (int i = 1; i < array.length; i++) { 5 if (array[i] > max) { 6 max = array[i]; 7 } 8 } 9 int time = 0; 10 // Judge digit; 11 while (max > 0) { 12 max /= 10; 13 time++; 14} 15 16 17 // Create 10 queues; 18 ArrayList<ArrayList<Integer>> queue = new ArrayList<>(); 19 for (int i = 0; i < 10; i++) { 20 ArrayList<Integer> queue1 = new ArrayList<>(); 21 queue.add(queue1); 22} 23 24 25 // Time allocation and collection; 26 for (int i = 0; i < time; I++) {27 // allocate array elements; 28 for (int anArray: array) {29 // Get the time of the number +1 digit; 30 int x = anArray % (int)Math.pow(10, i + 1) / (int)Math.pow(10, i); 31 ArrayList<Integer> queue2 = queue.get(x); 32 queue2.add(anArray); 33 queue.set(x, queue2); 34 } 35 int count = 0; // Element counter; 36 // Collect queue elements; 37 for (int k = 0; k < 10; k++) { 38 while (queue.get(k).size() > 0) { 39 ArrayList<Integer> queue3 = queue.get(k); 40 array[count] = queue3.get(0); 41 queue3.remove(0); 42 count++; 43 } 44 } 45 } 46 System.out.println(Arrays.toString(array) + " radixSort"); 47}Copy the codeThe results of
支那
支那
Attached are all the sorting results above:
1 package com.test.sort;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 @SuppressWarnings("WeakerAccess")
7 public final class SortDemo {
8
9 // 排序原始数据
10 private static final int[] NUMBERS =
11 {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
12
13
14 public static void main(String[] args) {
15 insertSort(NUMBERS);
16 shellSort(NUMBERS);
17 selectSort(NUMBERS);
18 bubbleSort(NUMBERS);
19 heapSort(NUMBERS);
20 quickSort(NUMBERS);
21 mergingSort(NUMBERS);
22 radixSort(NUMBERS);
23 }
24
25
26 public static void insertSort(int[] array) {
27 for (int i = 1; i < array.length; i++) {
28 int temp = array[i];
29 int j = i - 1;
30 for (; j >= 0 && array[j] > temp; j--) {
31 //将大于temp的值整体后移一个单位
32 array[j + 1] = array[j];
33 }
34 array[j + 1] = temp;
35 }
36 System.out.println(Arrays.toString(array) + " insertSort");
37 }
38
39
40 public static void shellSort(int[] array) {
41 int i;
42 int j;
43 int temp;
44 int gap = 1;
45 int len = array.length;
46 while (gap < len / 3) {
47 gap = gap * 3 + 1;
48 }
49 for (; gap > 0; gap /= 3) {
50 for (i = gap; i < len; i++) {
51 temp = array[i];
52 for (j = i - gap; j >= 0 && array[j] > temp; j -= gap) {
53 array[j + gap] = array[j];
54 }
55 array[j + gap] = temp;
56 }
57 }
58 System.out.println(Arrays.toString(array) + " shellSort");
59 }
60
61 public static void selectSort(int[] array) {
62 int position = 0;
63 for (int i = 0; i < array.length; i++) {
64 int j = i + 1;
65 position = i;
66 int temp = array[i];
67 for (; j < array.length; j++) {
68 if (array[j] < temp) {
69 temp = array[j];
70 position = j;
71 }
72 }
73 array[position] = array[i];
74 array[i] = temp;
75 }
76 System.out.println(Arrays.toString(array) + " selectSort");
77 }
78
79
80 public static void bubbleSort(int[] array) {
81 int temp = 0;
82 for (int i = 0; i < array.length - 1; i++) {
83 for (int j = 0; j < array.length - 1 - i; j++) {
84 if (array[j] > array[j + 1]) {
85 temp = array[j];
86 array[j] = array[j + 1];
87 array[j + 1] = temp;
88 }
89 }
90 }
91 System.out.println(Arrays.toString(array) + " bubbleSort");
92 }
93
94
95 public static void heapSort(int[] array) {
96 /*
97 * 第一步：将数组堆化
98 * beginIndex = 第一个非叶子节点。
99 * 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
100 * 叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
101 */
102 int len = array.length - 1;
103 int beginIndex = (len - 1) >> 1;
104 for (int i = beginIndex; i >= 0; i--) {
105 maxHeapify(i, len, array);
106 }
107 /*
108 * 第二步：对堆化数据排序
109 * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
110 * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
111 * 直至未排序的堆长度为 0。
112 */
113 for (int i = len; i > 0; i--) {
114 swap(0, i, array);
115 maxHeapify(0, i - 1, array);
116 }
117 System.out.println(Arrays.toString(array) + " heapSort");
118 }
119
120 private static void swap(int i, int j, int[] arr) {
121 int temp = arr[i];
122 arr[i] = arr[j];
123 arr[j] = temp;
124 }
125
126 /**
127 * 调整索引为 index 处的数据，使其符合堆的特性。
128 *
129 * @param index 需要堆化处理的数据的索引
130 * @param len 未排序的堆（数组）的长度
131 */
132 private static void maxHeapify(int index, int len, int[] arr) {
133 int li = (index << 1) + 1; // 左子节点索引
134 int ri = li + 1; // 右子节点索引
135 int cMax = li; // 子节点值最大索引，默认左子节点。
136 if (li > len) {
137 return; // 左子节点索引超出计算范围，直接返回。
138 }
139 if (ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
140 {
141 cMax = ri;
142 }
143 if (arr[cMax] > arr[index]) {
144 swap(cMax, index, arr); // 如果父节点被子节点调换，
145 maxHeapify(cMax, len, arr); // 则需要继续判断换下后的父节点是否符合堆的特性。
146 }
147 }
148
149
150 public static void quickSort(int[] array) {
151 _quickSort(array, 0, array.length - 1);
152 System.out.println(Arrays.toString(array) + " quickSort");
153 }
154
155
156 private static int getMiddle(int[] list, int low, int high) {
157 int tmp = list[low]; //数组的第一个作为中轴
158 while (low < high) {
159 while (low < high && list[high] >= tmp) {
160 high--;
161 }
162
163
164 list[low] = list[high]; //比中轴小的记录移到低端
165 while (low < high && list[low] <= tmp) {
166 low++;
167 }
168
169
170 list[high] = list[low]; //比中轴大的记录移到高端
171 }
172 list[low] = tmp; //中轴记录到尾
173 return low; //返回中轴的位置
174 }
175
176
177 private static void _quickSort(int[] list, int low, int high) {
178 if (low < high) {
179 int middle = getMiddle(list, low, high); //将list数组进行一分为二
180 _quickSort(list, low, middle - 1); //对低字表进行递归排序
181 _quickSort(list, middle + 1, high); //对高字表进行递归排序
182 }
183 }
184
185
186 public static void mergingSort(int[] array) {
187 sort(array, 0, array.length - 1);
188 System.out.println(Arrays.toString(array) + " mergingSort");
189 }
190
191 private static void sort(int[] data, int left, int right) {
192 if (left < right) {
193 //找出中间索引
194 int center = (left + right) / 2;
195 //对左边数组进行递归
196 sort(data, left, center);
197 //对右边数组进行递归
198 sort(data, center + 1, right);
199 //合并
200 merge(data, left, center, right);
201 }
202 }
203
204 private static void merge(int[] data, int left, int center, int right) {
205 int[] tmpArr = new int[data.length];
206 int mid = center + 1;
207 //third记录中间数组的索引
208 int third = left;
209 int tmp = left;
210 while (left <= center && mid <= right) {
211 //从两个数组中取出最小的放入中间数组
212 if (data[left] <= data[mid]) {
213 tmpArr[third++] = data[left++];
214 } else {
215 tmpArr[third++] = data[mid++];
216 }
217 }
218
219 //剩余部分依次放入中间数组
220 while (mid <= right) {
221 tmpArr[third++] = data[mid++];
222 }
223
224 while (left <= center) {
225 tmpArr[third++] = data[left++];
226 }
227
228 //将中间数组中的内容复制回原数组
229 while (tmp <= right) {
230 data[tmp] = tmpArr[tmp++];
231 }
232 }
233
234
235 public static void radixSort(int[] array) {
236 //首先确定排序的趟数;
237 int max = array[0];
238 for (int i = 1; i < array.length; i++) {
239 if (array[i] > max) {
240 max = array[i];
241 }
242 }
243 int time = 0;
244 //判断位数;
245 while (max > 0) {
246 max /= 10;
247 time++;
248 }
249
250
251 //建立10个队列;
252 ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
253 for (int i = 0; i < 10; i++) {
254 ArrayList<Integer> queue1 = new ArrayList<>();
255 queue.add(queue1);
256 }
257
258
259 //进行time次分配和收集;
260 for (int i = 0; i < time; i++) {
261 //分配数组元素;
262 for (int anArray : array) {
263 //得到数字的第time+1位数;
264 int x = anArray % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
265 ArrayList<Integer> queue2 = queue.get(x);
266 queue2.add(anArray);
267 queue.set(x, queue2);
268 }
269 int count = 0;//元素计数器;
270 //收集队列元素;
271 for (int k = 0; k < 10; k++) {
272 while (queue.get(k).size() > 0) {
273 ArrayList<Integer> queue3 = queue.get(k);
274 array[count] = queue3.get(0);
275 queue3.remove(0);
276 count++;
277 }
278 }
279 }
280 System.out.println(Arrays.toString(array) + " radixSort");
281 }
282 }
Copy the code