1 import java.util.Arrays;
2
3 /**
4 * Created by asus on 2019/9/4.
5 */
6 public class MyArraySort {
7 public static void main(String[] args) {
8 int[] data = {2,1,3,4,-1, 9 , 8};
9 MyArraySort m = new MyArraySort();
10 m.selectSort(data);
11 System.out.println(Arrays.toString(data));
12 }
13
14 private void swap(int[] data, int i, int j) {
15 int temp = data[i];
16 data[i] = data[j];
17 data[j] = temp;
18 }
19
20 //冒泡排序
21 private void bubbleSort(int[] data) {
22 int len = data.length;
23 if(len <= 1) return;
24
25 boolean isOrdered = true; //默认是有序的
26 for(int i = 0; i < len; i ++) {
27 if(i == 0 || !isOrdered ) { //但是第一次总得去排一排序
28 isOrdered = true; //默认是有序的
29 for(int j = 0; j < len - 1 - i; j ++) {
30 if(data[j] > data[j + 1]) {
31 swap(data,j, j + 1);
32 isOrdered = false;
33 }
34 }
35 }
36
37 if (isOrdered == true) break;
38
39 }
40 }
41
42
43 //选择排序
44 //扫描一遍，选一个最小的元素放置在首位
45 private void selectSort(int[] data) {
46 int len = data.length;
47 if(len <= 1) return;
48
49 for(int i = 0; i < len; i ++) {
50 int minIndex = i;
51 for(int j = i + 1; j < len; j ++) {
52 if(data[j] < data[i]) {
53 minIndex = j;
54 }
55 }
56 if(minIndex != i) swap(data, minIndex, i);
57 }
58 }
59
60
61 //插入排序
62 //当前这个数往前比较，如果比前面的数大，则插入后面一个位置，如果比前面的数小，则前面的数后移一位继续向前比较
63 private void insertSort(int[] data) {
64 int len = data.length;
65 if(len <= 1) return;
66
67 for(int i = 0; i < len; i ++) {
68 int cur = data[i];
69 for(int j = i - 1; j >= 0; j --) {
70 if(cur >= data[j]) {
71 data[j + 1] = cur;
72 break;
73 }else {
74 data[j + 1] = data[j];
75 if(j == 0) {
76 data[j] = cur;
77 }
78 }
79 }
80 }
81 }
82
83
84 //快速排序
85 private void quickSort(int[] data) {
86 int len = data.length;
87 if(len <= 1) return;
88
89 quickSortCore(data, 0, len - 1);
90
91
92
93 }
94
95 private void quickSortCore(int[] data, int st, int ed) {
96 if(ed > st) {
97 int index = partition(data, st, ed);
98
99 quickSortCore(data, st, index - 1);
100 quickSortCore(data, index + 1, ed);
101 }
102 }
103
104 private int partition(int[] data, int st, int ed) {
105 int piv = data[st];
106
107 while(st < ed) {
108 while(st < ed && data[ed] >= piv) ed --;
109 data[st] = data[ed];
110 while(st < ed && data[st] <= piv) st ++;
111 data[ed] = data[st];
112 }
113
114 data[st] = piv;
115 return st;
116 }
117
118 //归并排序
119 private void mergeSort(int[] data) {
120 int len = data.length;
121 if(len <= 1) return;
122
123 int[] temp = new int[len];
124
125 mergeSortCore(data, 0, len - 1, temp);
126
127
128
129 }
130
131 private void mergeSortCore(int[] data, int st, int ed, int[] temp) {
132 if(ed > st) {
133 int mid = st + (ed - st) / 2;
134 mergeSortCore(data, st, mid, temp);
135 mergeSortCore(data,mid + 1, ed, temp);
136 merge(data, st, mid, ed, temp);
137 }
138 }
139
140 private void merge(int[] data, int st, int mid, int ed, int[] temp) {
141 int i = st, j = mid + 1;
142
143 for(int k = st; k <= ed; k ++) {
144 temp[k] = data[k];
145 }
146
147 for(int k = st; k <= ed; k ++) {
148 if(i > mid) {
149 data[k] = temp[j ++];
150 }else if(j > ed) {
151 data[k] = temp[i ++];
152
153 }else if(temp[i] <= temp[j]) {
154 data[k] = temp[i ++];
155 }else {
156 data[k] = temp[j ++];
157 }
158 }
159 }
160
161
162 //堆排序
163 private void heapSort(int[] data) {
164 int len = data.length;
165 if(len <= 1) return;
166
167 //建堆
168 buildHeap(data);
169
170 //取出来最大元素并调整堆
171 for(int i = len - 1; i >= 0; i --) {
172 swap(data, 0, i);
173 adjustHeap(data, 0, i - 1);
174 }
175 }
176
177 private void buildHeap(int[] data) {
178 int len = data.length;
179 //从后一个非叶节点调整堆
180 for(int i = len / 2 - 1; i >= 0; i --) {
181 adjustHeap(data, i, len - 1);
182 }
183 }
184
185 private void adjustHeap(int[] data, int i, int lastPos) {
186 int l = i * 2 + 1;
187 int r = i * 2 + 2;
188 int max = i;
189
190 if(l <= lastPos && data[l] > data[max]) max = l;
191 if(r <= lastPos && data[r] > data[max]) max = r;
192
193 if(max != i) {
194 swap(data, max, i);
195 adjustHeap(data, max, lastPos);
196 }
197 }
198 }
