-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSort.java
More file actions
101 lines (94 loc) · 2.49 KB
/
Sort.java
File metadata and controls
101 lines (94 loc) · 2.49 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.Arrays;
import java.util.Random;
/**
* @author wenci
* @date: 2017/12/1
* @description:
*/
public class Sort {
static int[] arr = generateArray(8);
public static void main(String[] args) {
// bubbleSort(8);
fastSort();
}
private static void fastSort() {
System.out.println("初始数组为：\n" + Arrays.toString(arr));
qk(0, arr.length-1);
System.out.println("排序后数组为：\n" + Arrays.toString(arr));
}
/**
* 快速排序法
* @param start
* @param end
*/
private static void qk(int start, int end) {
if (start >= end) return;
int point = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] <= point && left < right) {
left++;
}
while (arr[right] >= point && left < right) {
right--;
}
if (left != right) {
swap(left, right);
}
}
if (arr[left] > arr[end]) {
swap(left, end);
}
qk(start, left);
qk(left + 1, end);
}
private static void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 冒泡排序法：数组两两比较，大的放后面
* @param length
*/
private static void bubbleSort(int length) {
int[] arr = generateArray(length);
System.out.println("初始数组为：\n" + Arrays.toString(arr));
for (int i=length-1; i>0; i--) {
for (int j=0; j<i; j++) {
if (arr[j] > arr[j+1]) {
arr[j] = arr[j] ^ arr[j+1];
arr[j+1] = arr[j+1] ^ arr[j];
arr[j] = arr[j] ^ arr[j+1];
}
}
}
System.out.println("排序后数组为：\n" + Arrays.toString(arr));
}
/**
* 选择排序法：每次将最后一个数为基准与前面的每个数比较，交换位置把大的放在后面。
* @param length
*/
private static void selectSort(int length) {
int[] arr = generateArray(length);
System.out.println("初始数组为：\n" + Arrays.toString(arr));
for (int i=length-1; i>0; i--) {
for (int j=0; j<i; j++) {
if (arr[i] < arr[j]) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
}
}
}
System.out.println("排序后数组为：\n" + Arrays.toString(arr));
}
private static int[] generateArray(int length) {
Random rand = new Random();
int[] arr = new int[length];
for (int i=0; i<length; i++) {
arr[i] = rand.nextInt(100);
}
return arr;
}
}