Fork me on GitHub

七种内部排序的代码实现

七种内部排序算法的代码实现(Java):

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 快排排序
  5. 归并排序
  6. 希尔排序
  7. 堆排序

1. 冒泡排序

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
public class 手写冒泡排序 {
public static void main(String[] args) {
int[] a = {2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a, 0, a.length - 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
}

private static void sorts(int[] a, int head, int tail) {
for (int i = head; i <= tail; ++i) {
for (int j = tail; j > i; --j) {
if (a[j] < a[j - 1]) {
swap(a,j-1,j);
}
}
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

2. 选择排序

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

public class 手写选择排序 {
public static void main(String[] args) {
int[] a = {2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a,0,a.length-1);
for(int i =0;i<a.length;++i){
System.out.print(a[i]+" ");
}
System.out.println();
}

private static void sorts(int[] a, int head, int tail) {
for(int i =head;i<=tail;++i){
int min = a[i];
int minIndex = i;
for(int j = i;j<=tail;++j){
if(a[j]<min){
min = a[j];
minIndex = j;
}
}
swap(a,i,minIndex);
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

3. 插入排序

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

public class 手写插入排序 {
public static void main(String[] args) {
int[] a = {2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a, 0, a.length - 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
}

private static void sorts(int[] a, int head, int tail) {
for (int i = head + 1; i <= tail; ++i) {
for (int j = i; j > head && a[j] < a[j - 1]; --j) {
swap(a, j, j - 1);
}
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

4. 快排排序

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

public class 手写快排 {
public static void main(String[] args) {
int[] a = {2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a, 0, a.length - 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
}

private static void sorts(int[] a, int head, int tail) {
if (head > tail) return;
int temp = a[head];
int i = head, j = tail;
while (i < j) {
while (a[j] > temp && i < j) j--;
a[i] = a[j];
while (a[i] < temp && i < j) i++;
a[j] = a[i];
}
a[i] = temp;
sorts(a, head, i - 1);
sorts(a, i + 1, tail);
}
}

5. 归并排序

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
public class 手写归并排序 {
public static void main(String[] args) {
int[] a = {2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a, 0, a.length - 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
}

private static void sorts(int[] a, int head, int tail) {
if (head >= tail) return;
int mid = (head + tail) / 2;
if(head + 1 == tail){
if(a[head]>a[tail]) swap(a,head,tail);
return;
}
sorts(a,0,mid);
sorts(a,mid+1,tail);
merge(a,head,mid,tail);
}

private static void merge(int[] a, int head, int mid,int tail) {
int len = tail - head +1;
int[] b = new int[len];
int i =head,j=mid+1;
int index = 0;
while(i<=mid && j<=tail){
if(a[i]<a[j]){
b[index++] = a[i++];
}else{
b[index++] = a[j++];
}
}
while(i<=mid){
b[index++] = a[i++];
}
while(j<=tail){
b[index++] = a[j++];
}
index = 0;
for(int t = head;t<=tail;++t){
a[t] = b[index++];
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

6. 希尔排序

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

public class 手写shell排序 {
public static void main(String[] args) {
int[] a = {2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a, 0, a.length - 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
}

private static void sorts(int[] a, int head, int tail) {
int len = tail - head + 1;
for (int step = len / 2; step > 0; step /= 2) {
for (int i = head + step; i <= tail; ++i) {
for (int j = i; j >= head+step && a[j] < a[j - step]; j -= step) {
swap(a, j, j - step);
}
}
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}

7. 堆排序

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

public class 手写堆排序 {
public static void main(String[] args) {
int[] a = {-1, 2, 4, 3, 8, 9, 1, 7, 5, 0, 6};
sorts(a, 1, a.length - 1);
for (int i = 1; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
System.out.println();
}

/*
堆的存储就从脚标 1 开始,low 参数就是摆设,从来都是 1
*/
private static void sorts(int[] a, int low, int high) {
// 建一个最大堆
createHeap(a, low, high);

for (int i = high; i > low; --i) {
// 移动堆顶元素到数组的 i 处
swap(a, low, i);
// 向下调整
downAdjust(a, low, i - 1);
}

}

/*
新建一个最大堆
*/
private static void createHeap(int[] a, int low, int high) {
for (int i = high / 2; i >= 1; --i) {
downAdjust(a, low, high);
}
}

/*
最大堆向下调整
*/
private static void downAdjust(int[] a, int low, int high) {
int i = low, j = low * 2;
while (j <= high) {
if (j + 1 <= high) {
j = a[j + 1] > a[j] ? j + 1 : j; // j 设为较大的孩子结点
}
if (a[i] < a[j]) {
swap(a, i, j);
i = j;
j = 2 * j;
} else {
break;
}
}
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
-------------The End-------------