排序算法总结 java实现

不同的排序算法源于不同的思想。虽然目标是一样的,却有不同的效率,各自的稳定性、是否是原址排序也是有所不同。这里做一个总结,并且附上java实现的代码。具体如下:

  • 基本概念
  • 插入排序
  • 冒泡排序
  • 选择排序
  • 归并排序
  • 堆排序
  • 快速排序

完整代码(包括测试用例): (https://github.com/FergusChen/AlgoCode)
包路径:main.sort

先说一些概念型的东西,用于描述排序算法:
原址排序:直接在原数组中排序,只需要常数个额外空间。
稳定排序:如果一个排序算法是稳定的,则序列中相同的元素原来有怎样的前后次序,排序后仍然是这样的前后次序。具体来说,对于序列[1,3,5,3,4], 排序后序列为[1,3,3,4,5],其中,原来在前面的3仍然在前面,保证两个3的前后次序,这样的排序算法就是稳定的。

插入排序

听到插入排序就想起来左手一副扑克牌,扑克牌的左半部分是已经排好序的,然后逐个抽取右半部分的牌,插入到左半部分的合适位置,直到整副牌都是排好序的。

插入排序就是这样的思想。初始化时左半部分只有1个元素,当然是排好序的啦。然后从右半部分的第1个元素开始,与左半部分已排好序的元素逐个比较,直到找到合适位置(插入后仍使左半部分有序),将该元素插入到此位置就可。

当然,插入的时候就涉及到元素的右移,即把待插入的位置右边的元素(直到待插入的元素)逐个右移,腾出1个元素空间,以存放待插入的元素。特别是当原数组是倒序的,则会有(n-1)!次元素右移,这样的话效率就会比较低。

由上可知,插入排序是原址排序,其最坏运行时间是O(n^2)。并且插入排序是稳定的,因为相等的元素并不右移,所以元素插入后仍然保证前后次序。当待排序数组元素较少,插入排序还是很好的选择。

下面以整型数组为例来实现插入排序,只是演示排序思想。对于自定义对象等的排序,常常可以实现comparable接口,从compareTo方法比较,思想都是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* ------插入排序------
* @param array 待排序数组
* test: (null), (1个元素的数组),(空数组),(5个无序整数数组),(6个有序整数数组)
*/
public static void insertSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
int curData = array[i];
int j = i - 1;
while(j >= 0 && curData < array[j]){
array[j + 1] = array[j];
j--;
}
array[j + 1] = curData;
}
}

冒泡排序

冒泡排序的名字就很形象:就好像从水底开始,相邻两个气泡互相比较,如果下面的比上面的大,就把两个气泡交换,直到最终把整个序列中最大的气泡换到顶部。接下来从下面开始,一步步把次大的气泡换到顶部…… 直到最后,就是一个升序的序列。

冒泡排序也是一种原址排序算法。冒泡排序是稳定的,因为冒泡排序是相邻两个元素交换次序,就算两个元素相等而且判断的条件是if(array[j] >= array[j+1]),那么该相同元素也会交换两次(动手试试就知道了)。但是通常比较时“>”的时候再交换位置。 冒泡排序是时间复杂度是O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 冒泡排序
* @param array 待排序数组
* test: (null), (1个元素的数组),(空数组),(5个无序整数数组),(6个有序整数数组)
*/
public static void bubbleSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}

选择排序

选择排序的思想也很简单,就是从序列中选出最小的元素,与序列第1个元素交换位置,然后从剩余元素中选出最小的,与序列第2个元素交换位置……直到序列就剩1个元素了,即是一个排好序的序列。
选择排序也是原址排序,但选择排序是不稳定的。这里可以举个例子说明,如序列[3,6,5,3,1],在第一趟选择将第1个3和结尾的1交换位置,这样就破坏了两个3的前后次序。选择排序的时间复杂度是O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 选择排序
* @param array 待排序数组
* test: (null), (1个元素的数组),(空数组),(5个无序整数数组),(6个无序整数数组)
* */
public static void selectSort(int[] array){
if(array == null || array.length <= 1){
return ;
}
for(int i = 0; i < array.length; i++){
int minIndex = i;
for(int j = i+1; j < array.length; j++){
if(array[j] < array[minIndex]){
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}

归并排序

归并排序的思想是“分治、合并”,其关键步骤是把两个有序的序列合并成1个有序序列。那么,有序的序列怎么形成呢?归并排序采用分治的策略,先对序列进行划分(递归),直到划分子序列只有1个元素,1个元素的序列当然是有序的啦,然后就可以将两个只含有1个元素的序列合并成1个含有两个元素的有序序列。总之,就是先划分,再回溯合并,这整个过程就是一个递归的过程。

归并排序的时间复杂度是O(nlgn),是一种稳定排序。归并排序需要将元素复制到临时数组,临时数组的长度为high - low + 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
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
/**
* 归并排序
*
* @param array 待排序数组
* @param low 待排序数组序列的最低位置
* @param high 待排序数组序列的最高位置
* test: (null), (1个元素的数组),(空数组),(5个无序整数数组),(6个无序整数数组)
*/
public static void mergeSort(int[] array, int low, int high) {
if (array == null || array.length <= 1) {
return;
}
int mid = (low + high) / 2;
if (low < high) {
mergeSort(array, low, mid);
mergeSort(array, mid + 1, high);
merge(array, low, mid, high);
}
}
/**
* 归并过程
* @param array 待合并的数组
* @param low 待合并数组序列的最低位置
* @param mid 待合并数组序列中划分两个有序序列的位置
* @param high 待合并数组序列的最高位置
* 将array中 low到high的元素归并到有序序列,其中,low到mid的序列是有序的,mid+1到high的序列是有序的。
* */
public static void merge(int[] array, int low, int mid, int high){
int[] tempArr = new int[high - low + 1];
int i = low; //i指向已排好序的左序列
int j = mid + 1; //j指向已排好序的右序列
int k = 0; //合并到新数组的指针
//合并过程
while(i <= mid && j <= high){
if(array[i] < array[j]){
tempArr[k++] = array[i++];
}else{
tempArr[k++] = array[j++];
}
}
//若左边有序序列有剩余元素,将剩余元素合并到tempArr中
while(i <= mid){
tempArr[k++] = array[i++];
}
//若右边有序序列有剩余元素,将剩余元素合并到tempArr中
while (j <= high){
tempArr[k++] = array[j++];
}
//用合并后的有序序列覆盖原数组中的左右两部分序列
for(k = 0; k < tempArr.length; k++){
array[k+low] = tempArr[k];
}
}

堆排序

堆排序涉及到一种比较有意思的数据结构——,对于其性质,可以回顾《算法导论》。简单来说,堆就是用数组实现的一颗近似的完全二叉树。最大堆可以保证每一个父结点都大于或等于其子结点。这样最大堆的根节点就是该数组的最大值。

堆排序使用最大堆,需要首先建堆,并且在交换根结点和最后一个结点之后,反复对堆维护。听起来很麻烦,但是因为每次维护堆的时间复杂度是O(lgn),建堆的时间复杂度是O(nlgn),则堆排序的时间复杂度仍然是O(nlgn)。堆排序是原址排序,但堆排序是不稳定的。

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
/**
* 堆排序
*
* @param array 待排序的堆
*/
public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
buildMaxHeap(array);
for (int i = array.length - 1; i >= 1; i--) {
exchangeElements(array, 0, i);
maxHeapify(array, i, 0);
}
}
/**
* 维护堆
* 在这个堆中,只有index位置的元素违背了最大堆的性质,调整该元素的位置,使index位置元素为结点为根的堆仍然是最大堆。
* 思想:index位置的元素与其左右孩子比较,将三个元素中的最大值与index位置的元素交换,然后递归地向下调整
*
* @param array 待维护的堆
* @param heapSize 堆的元素个数
* @param index 带调整的元素位置
*/
public static void maxHeapify(int[] array, int heapSize, int index) {
int left = index * 2 + 1;
int right = index * 2 + 2;
int largest = index;
if (left < heapSize && array[left] > array[index]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (largest != index) {
exchangeElements(array, index, largest);
maxHeapify(array, heapSize, largest);//递归地向下维护堆
}
}
/**
* 新建最大堆
* @param array 待建堆的数组
*/
public static void buildMaxHeap(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int mid = (array.length - 1) / 2;
for (int i = mid; i >= 0; i--) {
maxHeapify(array, array.length, i);
}
}

快速排序

快速排序也是使用“分治”的思想,但与归并排序不同的是,快速排序在分治的过程中进行处理次序,具体来说,对于数组A[low ... high],被划分为两个(可能为空)的子数组A[low ... p-1]A[p+1 ... high],使得A[low ... p-1]的元素都小于或等于A[p]A[p+1 ... high]的元素都大于A[p]。 然后再递归地划分A[low ... p-1]A[p+1 ... high]。当左右子序列划分都递归到1个元素时,整个序列都是有序的啦。

快速排序的平均时间复杂度为O(nlgn),最坏时间复杂度是O(n^2)。快速排序的实际性能是几个O(nlgn)中最好的,而且还是原址排序。但是快速排序并不是稳定的排序算法。因为会涉及到元素与主元的交换。举个例子,对于序列[2,3,4,6,6,7,9,5],以5为主元,当划分之后,元素5需要与第1个6交换位置,这样,就打破了两个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
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
/**
* 快速排序
* @param array 带排序的数组
* @param low 带排序数组的最低位置
* @param high 带排序的数组的最高位置
* test: (null), (1个元素的数组),(空数组),(5个无序整数数组),(6个无序整数数组)
*/
public static void quickSort(int[] array, int low, int high) {
if (array == null || array.length <= 1) {
return;
}
if (low < high) {
int p = randomPartition (array, low, high);
quickSort(array, low, p - 1);
quickSort(array, p + 1, high);
}
}
/**
* 随机选取数组中的一个数进行划分
* @param array 带划分的数组序列
* @param low 带划分数组序列的最低位置
* @param high 带划分数组序列的最高位置
* @return int 返回最后划分后,主元的位置 * */
public static int randomPartition(int[] array, int low, int high){
int i = (int)(low + Math.random()*(high - low + 1)); //产生low到high之间的随机数
int temp = array[high];
array[high] = array[i];
array[i] = temp;
return partition(array, low, high);
}
/**
* 划分数组
* 将array中low 到 high序列划分为两部分,并返回划分元的位置
* @param array 带划分的数组序列
* @param low 带划分数组序列的最低位置
* @param high 带划分数组序列的最高位置
* @return int 返回最后划分后,主元的位置
* */
public static int partition(int[] array, int low, int high) {
int key = array[high]; //主元,即用于划分的元素
int i = low - 1; //i指向 小于key的序列的尾部
//j来遍历整个序列,将小于key的元素放到i的左边
for (int j = low; j < high; j++) {
if (array[j] <= key) //不仅是小于key,连等于key的元素也交换,以保证划分过程是原址重排
i++;
//如果i == j 就无需交换了。
if(i != j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
//此时,i指向小于key的序列的尾部,则将key与i+1的元素交换,就将整个序列划分为A、B两个部分,其中A:小于或等于key的元素,B:大于key的元素。
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
//返回用于划分的主元的位置。
return i + 1;
}