0%

排序算法

发表于 更新于 分类于
本文字数： 阅读时长 ≈

去年就花了几百参加了左神的算法科，现在准备找工作，于是把之前的学习总结一下push上来，这个博客会继续维护，记录自己的学习路径。
先从简单的排序开始，下面总结一下几种不同的排序算法的java版本。

1，选择排序

选择排序的思想：从数组中选出一个数(一般是第一个数)，然后后面的数依次与arr[0]作比较，若后面的数大于第一个数不做交换，否则就交换两个数的位置，依次进行指导后面的数到数组末尾，这样就选出了最小的数并且它在第一个位置；下一轮比较开始选第二个数参与与后面的数的比较(对应的外层循环加1，)，依次类推，指导选出第二小的数位于第二个位置….，直到数组有序。选择排序算法时间复杂度是O(n^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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
   //选择排序的代码1(左程云左神算法初级课代码)
   public static void selectionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j < arr.length; j++) {
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		swap(arr, i, minIndex);
	}
}
   //选择排序的代码2
   public static void selectionSort_2(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) {
		for (int j = i + 1; j < arr.length; j++) {
			if (arr[j] < arr[i]) {
				swap(arr, i, j);
			}
		}
	}
}
   //交换两个位置上的数
public static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}
   //打印数组
public static void printArray(int[] arr) {
	if (arr == null) {
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}
   //主函数中测试代码：
public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] arr = {2,56,12,34,8,67,100};
	printArray(arr);
	selectionSort(arr);
	printArray(arr);
   }

自己写的是selectionSort_2，感觉这样稍微更好理解一点。

2，冒泡排序

冒泡排序，指每次选出最大的一个值往后沉。解释：第一次从数组中选出最大的那个值往后沉，以此类推，每一次都将这次排序的数中最大的值往后沉，知道最后有序。此后只写出主代码。
这就像数一个一个往后冒，因此得名冒泡排序。
方法一：

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int e = arr.length - 1; e > 0; e--) {
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
public static void bubbleSort_2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int j = 0; j < arr.length - 1; j++) {
			for (int i = 0; i < arr.length - j - 1; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
}

3，插入排序

类似于打牌的情形，我们拿牌后都会从左到右按从小到大的方式排序。它是假设第一个数已经排好序，然后后面的数依次作比较进行排序。

1
2
3
4
5
6
7
8
9
10
public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) {
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

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
28
29
30
31
32
33
34
35
public static void heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			heapInsert(arr, i);
		}
		int size = arr.length;
		swap(arr, 0, --size);
		while (size > 0) {
			heapify(arr, 0, size);
			swap(arr, 0, --size);
		}
	}

public static void heapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}

	public static void heapify(int[] arr, int index, int size) {
		int left = index * 2 + 1;
		while (left < size) {
			int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
			largest = arr[largest] > arr[index] ? largest : index;
			if (largest == index) {
				break;
			}
			swap(arr, largest, index);
			index = largest;
			left = index * 2 + 1;
		}
	}

1，heapInsert过程：这是建立大根堆，实际上这里是数组，不过我们常用数组来表示大根堆。建立大根堆的过程。heapInsert(arr, i);就是在0–>i位置实现大根堆的代码。每加入一个数，都计算它的下标，然后与父节点(这里没有树结构，但是我们通常都用数组表示树结构，所以可以根据数组的下标模拟树结构)的值比较，比父节点大就交换，把index设置为父节点的位置，然后继续这个操作，直到不满足条件了就结束。时间复杂度是O(log(1)+…+log(n-1)+logn)=O(n)，也就是O(n)。
2，heapfy过程：假设数组中有一个数变小了，记住它的位置(下标)，那调整数组让它成为大根堆的过程。这个过程就是heapfy的过程。找到该节点的左右孩子中较大的那个与它比较，若比这个变化后的节点值大，那么该值往下沉，与较大值交换。如果左右孩子中最大的点都不必index处的值大，说明已经不需要调整了，这时候break。
堆排序就是，先形成一个大根堆，然后堆顶元素和最后一个元素交换，这样数组的最后一个元素就是最大值，然后对于堆来讲大小减一，而我们用最后一个数与堆顶交换，这个数肯定不是最大的，所以我们继续heapfy的过程，再形成大根堆，再把最大值与最后位置的值交换，堆的大小减一；依次类推直到堆的大小为0。这样也就完成排序了。

5，快速排序

先讲荷兰国旗问题，荷兰国旗问题的引申，就是把一列数排成左边小于等于某个划分值，中间等于这个划分值，右边大于这个划分值。这就是快排partition的过程。
NetherlandsFlag主代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int[] partition(int[] arr, int l, int r, int p) {
		int less = l - 1;
		int more = r + 1;
		while (l < more) {
			if (arr[l] < p) {
				swap(arr, ++less, l++);
			} else if (arr[l] > p) {
				swap(arr, --more, l);
			} else {
				l++;
			}
		}
		return new int[] { less + 1, more - 1 };
}

l和r指的是从数组的l位置到数组的r位置进行partition的过程，p是指划分值。
举例：p = 5，arr = {4,6，7,3}。
步骤：
1，先设定一个小于区域，最初小于区域没有数，小于区域的最后一个位置是-1。
2，第一个数和p比较，4小于5，所以4和小于等于区域的下一个数交换，然后小于区域向右扩一个位置，在这里也就是4和4交换(因为4是第一个数)。
3，下一个数为6，大于5，所以跳到下一个数。
4，7大于5，跳到下一个数
5，3小于5，3和小于区域后一个数交换，数组变为：{4,3,6，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

public static void quickSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int l, int r) {
	if (l < r) {
		swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
		int[] p = partition(arr, l, r);
		quickSort(arr, l, p[0] - 1);
		quickSort(arr, p[1] + 1, r);
	}
}

public static int[] partition(int[] arr, int l, int r) {
	int less = l - 1;
	int more = r;
	while (l < more) {
		if (arr[l] < arr[r]) {
			swap(arr, ++less, l++);
		} else if (arr[l] > arr[r]) {
			swap(arr, --more, l);
		} else {
			l++;
		}
	}
	swap(arr, more, r);
	return new int[] { less + 1, more };
}

quickSort(arr, 0, arr.length - 1);这是指从arr数组的0位置到最后位置进行快排。quickSort代码：

1
2
3
4
5
6
7
8
9
public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
			//随机快排
			swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0] - 1);
			quickSort(arr, p[1] + 1, r);
		}
}

如上代码所示，经典快排分析

  • 1，选择最后的数作为划分值，然后用partition代码将数组划分为小于等于大于的三个区域
  • 2，递归调用quickSort，实际上是递归调用partition方法，也就是分别对步骤1产生的左右部分进行partition的过程(这里不包含等于部分)
  • 3，直到l小于r，递归终止
    随机快排
    随机快排实际上就是每次quickSort之前，都用数组的前面的所有数随机选一个与最后的数交换，swap(arr, l + (int) (Math.random() * (r - l + 1)), r);所以随机快排的划分值很均匀，随机快排比经典快排效率高，原因：经典快排划出来的区域很可能不是等规模的。经典快排的时间复杂度O(n^2),随机快排的时间复杂度长期期望为O(nlogn)。

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
30
31
32
33
34
35
public static void mergeSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		mergeSort(arr, 0, arr.length - 1);
}

	public static void mergeSort(int[] arr, int l, int r) {
		if (l == r) {
			return;
		}
		int mid = l + ((r - l) >> 1);
		mergeSort(arr, l, mid);
		mergeSort(arr, mid + 1, r);
		merge(arr, l, mid, r);
	}

	public static void merge(int[] arr, int l, int m, int r) {
		int[] help = new int[r - l + 1];
		int i = 0;
		int p1 = l;
		int p2 = m + 1;
		while (p1 <= m && p2 <= r) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while (p1 <= m) {
			help[i++] = arr[p1++];
		}
		while (p2 <= r) {
			help[i++] = arr[p2++];
		}
		for (i = 0; i < help.length; i++) {
			arr[l + i] = help[i];
		}
    }

7,桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void bucketSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		int max = Integer.MIN_VALUE;
		//找到数组最大值
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
		}
		int[] bucket = new int[max + 1];
		for (int i = 0; i < arr.length; i++) {
			bucket[arr[i]]++;
		}
		int i = 0;
		for (int j = 0; j < bucket.length; j++) {
			while (bucket[j]-- > 0) {
				arr[i++] = j;
			}
		}
}

桶排序思想：首先找到数组最大值，然后新建一个数组长度为最大值加1，也就是bucket数组，找到最大值后遍历数组，把原数组的数据放入bucket数组的下标中，也就是bucket[i]，每当有一个i加入bucket[i]的值就加1，遍历结束后，所有的数据已经加入桶中。最后遍历桶，如果bucket[i]– 大于0就说明这个桶有数据，然后排序arr[i++] = j(j是bucket数组的下标，实际上就是原数组的值)。

8，基数排序

1
2