Java实现的几种排序方法

发表于 分类于 阅读次数：

插入排序

基本思想

在要排序的一组数中，假设前面(n-1) [n>=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 插入排序
* @param array
*/
public static void insertSort(int[] a) {
    int temp = 0;
	int n = a.length;

	for (int i = 1; i < n; i++) {
		for (int j = i; j > 0; j--) {
			if (a[j] < a[j - 1]) {
				temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}

	}
}

冒泡排序

基本原理

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 冒泡排序
* @param array
*/
public static void bubbleSort(int array[]) {
	int temp = 0;
	int n = array.length;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < n - i - 1; j++) {
			if (array[j] > array[j + 1]) {
				temp = array[j + 1];
				array[j + 1] = array[j];
				array[j] = temp;
			}
		}
	}
}

选择排序

基本原理

在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 选择排序
* @param a
*/
public static void selectSort(int[] a) {
	int n = a.length;
	int minIndex;

	for (int i = 0; i < n-1; i++) {
		minIndex = i; // 将当前下标定义为最小值下标
		for (int j = i + 1; j < n; j++) {
			if (a[minIndex] > a[j]) {
				minIndex = j;
			}
		}
		
		if (minIndex != i) {
			int temp = a[minIndex];
			a[minIndex] = a[i];
			a[i] = temp;
		}
	}
}

快速排序

基本思想

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

实现

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
/**
 * 快速排序
 * @param a
 */
public static void quickSort(int[] a, int start, int end) {

	if (a.length <= 0 || (end - start) <= 0) {
		return;
	}

	int mid = start; // 数组第一个作为准值

	/** */
	for (int i = start + 1; i <= end; i++) {
		if (a[i] < a[start]) {
			int temp = a[++mid];
			a[mid] = a[i];
			a[i] = temp;
		}
	}

	int temp = a[mid];
	a[mid] = a[start];
	a[start] = temp;

	quickSort(a, start, mid - 1);
	quickSort(a, mid + 1, end);
}

归并排序

基本思想

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

实现

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
public static void mergeSort(int[] a, int start, int end) {
	if (start < end) {
		//找出中间索引
		int mid = (start + end) / 2;
		//对左边数组递归
		mergeSort(a, start, mid);
		//对右边数组递归
		mergeSort(a, mid + 1, end);
		//合并
		merge(a, start, mid, end);
	}
}

private static void merge(int[] a, int start, int mid, int end) {
	int[] temp = new int[a.length];
	int tmp = start;
	int i = start;
	int j = mid + 1;
	int k = start; // 记录中间数据的索引

	while (i <= mid && j <= end) {
		// 从两个数据取出最小的值放入中间数组
		if (a[i] < a[j]) {
			temp[k++] = a[i++];
		} else {
			temp[k++] = a[j++];
		}
	}
	// 剩余部分依次放入中间数组
	while (i <= mid) {
		temp[k++] = a[i++];
	}

	while (j <= end) {
		temp[k++] = a[j++];
	}

	// 把中间数组内容复制回原数组
	while (tmp <= end) {
		a[tmp] = temp[tmp++];
	}
}

参考文章

《数据结构与算法分析-Java语言描述》

程序员必知的8大排序