Fork me on GitHub

七种内部排序的代码实现

Posted on | Edited on | In | Views:

七种内部排序算法的代码实现（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
27
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
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 + 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
27

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
53
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
29

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
62

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-------------