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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
<!-- more -->
import java.util.Arrays;
public class Sort {
//快速排序
private static int partition(int[] arr, int low, int hight) {
int pivotkey = arr[low];
while (low < hight) {
while (low < hight && pivotkey <= arr[hight])
--hight;
int temp1 = arr[low];
arr[low]=arr[hight];
arr[hight]=temp1;
//arr[low] = arr[hight];
while (low < hight && pivotkey >= arr[low])
++low;
int temp2 = arr[low];
arr[low]=arr[hight];
arr[hight]=temp2;
//arr[hight] = arr[low];
}
return low;
}
//快速排序
public static void qSort(int[] arr, int low, int hight) {
if (low < hight) {
int pivotkey = partition(arr, low, hight);
qSort(arr, low, pivotkey - 1);
qSort(arr, pivotkey + 1, hight);
}
}
//插入排序
public static int[] insertOrder(int a[]){
for (int i = 1; i < a.length; i++) {
int k = a[i];
int j;
for (j = i - 1; j >= 0 && k < a[j]; j--) {
a[j + 1] = a[j];
}
a[j + 1] = k;
//System.out.println(Arrays.toString(a));
}
return a;
}
//冒泡排序
public static int[] maopao(int[] a){
for(int i=0;i<a.length-1;i++){//i 代表伦次
for(int j=0;j<a.length-i-1;j++){//j和j+1代表相邻元素
if(a[j]>a[j+1]){
int temp = a[j];
a[j]= a[j+1];
a[j+1]=temp;
}
}
//System.out.println(Arrays.toString(a));
//Arrays.sort(a);
}
return a;
}
//选择排序
public int[] selectOrder(int arr[] ) {
for (int i = 0; i <arr.length; i++) {
int max = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < max) {
int temp = arr[j];
arr[j] = max;
max = temp;
arr[i] = max;
}
}
}
return arr;
}
// 二分查找
public void binarySearch() {
int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
int start = 0;
int end = b.length - 1;
int mid;
int target = 1;
while (true) {
mid = ((end + start) / 2);
if (b[mid] == target) {
System.out.println(mid);
break;
}
if (target < b[mid]) {
end = mid;
}
if (target > b[mid]) {
start = mid + 1;
}
}
}
public static void main(String args[]) {
int Arr[] = { 10, 30, 20, 50, 90, 80, 60, 40, 70 };
System.out.println(Arrays.toString(Arr));
qSort(Arr, 0, Arr.length -1);
System.out.println(Arrays.toString(Arr));
}
}
希尔排序:
算法思想
它是对插入插入排序的改进
搜索维基百科可知
希尔排序，也称递减增量排序算法
假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]
，我们分别以步长为5，3，1进行排序（希尔排序最后的步长一定是1）
步长为5，我们可以得到如下数据，
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后 按照列排序
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
-最后以1步长进行排序（此时就是简单的插入排序了）。
public static void shellPass(Integer[] array, int d) {
for (int i = d; i < array.length; i++) {
int temp = array[i];
int j = i - d;
while (j >= 0 && array[j] > temp) {
array[j + d] = array[j];
j -= d;
}
array[j + d] = temp;
}
}
public static void shellSort(Integer[] data) {
int increment = 12;
do {
increment = increment / 3 + 1;
shellPass(data, increment);
} while (increment > 1);
}
|
