谈谈几个常用的排序算法

发表于 | 分类于 ， | | 阅读次数

最近在读<>时,了解到了很多常用的排序算法,故写一篇读书笔记记录下这些排序算法的思路和实现.

冒泡排序

冒泡排序是一种非常简单的初级排序算法,它每次比较相邻的两个元素,如果顺序错误就进行交换.由于最小的元素是经由不断交换慢慢浮到顶端的,所以叫做冒泡排序.

冒泡排序对n个元素需要O(n^2)次的比较次数,所以它对规模较大的数组进行排序是效率低下的.

运行过程

  1. 比较相邻的两个元素,如果第二个元素小于第一个元素,则进行交换(降序则相反).
  1. 对每一对相邻元素作同样的工作,从开始第一对直到最后一对.完成后,最后的元素将是最大的元素.
  1. 针对所有的元素重复以上步骤,除了最后一个元素.
  1. 持续地对每次越来越少的元素重复以上步骤,直到整个数组有序(即没有任何一对元素需要比较).

代码实现

1
2
3
4
5
6
7
8
9
10
   // less与exch函数见完整代码
public static void sort(Comparable[] a) {
	for (int i = 0; i < a.length - 1; i++) {
		for (int j = 0; j < a.length - 1 - i; j++) {
			if (less(a[j + 1], a[j])) {
				exch(a, j, j + 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/**
 * Bubble Sort
 * 
 * @author SylvanasSun
 *
 */
public class Bubble {
	// This class should not be instantiated.
	private Bubble() {
	}
	/**
	 * Rearranges the array in ascending order, using the natural order.
	 * 
	 * @param a
	 *            a the array to be sorted
	 */
	public static void sort(Comparable[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - 1 - i; j++) {
				if (less(a[j + 1], a[j])) {
					exch(a, j, j + 1);
				}
			}
		}
	}
	/**
	 * Rearranges the array in ascending order, using a comparator.
	 * 
	 * @param a
	 *            a the arry to be sorted
	 * @param comparator
	 *            comparator the comparator specifying the order
	 */
	public static void sort(Object[] a, Comparator comparator) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 0; j < a.length - 1 - i; j++) {
				if (less(comparator, a[j + 1], a[j])) {
					exch(a, j, j + 1);
				}
			}
		}
	}
	// a < b ?
	private static boolean less(Comparable a, Comparable b) {
		return a.compareTo(b) < 0;
	}
	// a < b ?
	private static boolean less(Comparator comparator, Object a, Object b) {
		return comparator.compare(a, b) < 0;
	}
	// exchange a[i] and a[j]
	private static void exch(Object[] a, int i, int j) {
		Object temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	// print array elements to console
	public static void print(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
	// test
	public static void main(String[] args) {
		String[] s = new Scanner(System.in).nextLine().split("\\s+");
		Bubble.sort(s);
		Bubble.print(s);
	}
}

选择排序

选择排序也是一种非常简单直观的初级排序算法,它的思想是不断地选择剩余元素之中的最小者.

它有以下两个特点.

  1. 运行时间与输入模型无关 在选择排序中,为了找出最小元素而扫描一遍数组并不能为下一轮扫描提供什么信息,即使输入是一个已经有序的数组或者是主键全部相等的数组和一个元素随机排列无序的数组所用的排序时间是一样长的.
  1. 数据移动是最少的 如果元素处于正确的位置上,则它不会被移动.选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换.

运行过程

  1. 首先,找到数组中最小的那个元素
  1. 其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素则它就和自己交换)
  1. 再次,在剩下的元素中找到最小的元素,将它与数组第二个元素交换位置.如此往复,直到整个数组有序.

代码实现

1
2
3
4
5
6
7
8
9
10
public static void sort(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			int min = i; // the smallest element index
			for (int j = i + 1; j < a.length; j++) {
				if (less(a[j], a[min]))
					min = j;
				exch(a, i, min);
			}
		}
	}

插入排序

插入排序与选择排序一样,当前索引左边的所有元素都是有序的,但它们的最终位置并不是确定的.它构建了一个有序序列,对于未排序的元素,在有序序列中从后向前扫描,找到相应的位置并插入.

插入排序所需的时间取决于输入模型中元素的初始顺序.当输入模型是一个部分有序的数组时,插入排序的效率会高很多.

因此插入排序对于部分有序的数组十分高效,也很适合小规模的数组.

运行过程

  1. 从第一个元素开始,该元素可以认为已是有序的
  1. 取出下一个元素,在有序序列中从后向前进行扫描
  1. 如果该元素(已排序)大于新元素,则将该元素移到下一位置(右移)
  1. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  1. 将新元素插入到该位置后
  1. 重复步骤2~5

代码实现

1
2
3
4
5
6
7
8
public static void sort(Comparable[] a) {
		for (int i = 0; i < a.length; i++) {
			// a[i] insert to a[i-1]、a[i-2]、a[i-3]...
			for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
				exch(a, j, j - 1);
			}
		}
	}

优化

插入排序还有很多可以优化的地方,这里例举两个案例.

  • 采用二分查找法来减少比较操作的次数.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    public static void sort(Comparable[] a) {
    	int length = a.length;
    	for (int i = 1; i < length; i++) {
    		// binary search to determine index j at which to insert a[i]
    		Comparable v = a[i];
    		int lo = 0, hi = i;
    		while (lo < hi) {
    			int mid = lo + (hi - lo) / 2;
    			if (less(v, a[mid]))
    				hi = mid;
    			else
    				lo = mid + 1;
    		}
    		// insertion sort with "half exchanges"
    		// (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
    		for (int j = i; j > lo; --j)
    			a[j] = a[j - 1];
    		a[lo] = v;
    	}
    }
  • 在内循环中将较大的元素都向右移动而不总是交换两个元素(访问数组的次数能够减半)
    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 static void sort(Comparable[] a) {
    	int length = a.length;
    	// put smallest element in position to serve as sentinel
    	int exchanges = 0;
    	for (int i = length - 1; i > 0; i--) {
    		if (less(a[i], a[i - 1])) {
    			exch(a, i, i - 1);
    			exchanges++;
    		}
    	}
    	if (exchanges == 0)
    		return;
    	// insertion sort with half-exchanges
    	for (int i = 2; i < length; i++) {
    		Comparable v = a[i];
    		int j = i;
    		while (less(v, a[j - 1])) {
    			a[j] = a[j - 1];
    			j--;
    		}
    		a[j] = v;
    	}
    }

希尔排序

希尔排序,也称递减增量排序算法,它是基于插入排序的一种更高效的改进版本.

由于插入排序对于大规模乱序数组效率并不高,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端.

而希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序.

希尔排序的思想是使数组中任意间隔为h的元素都是有序的,可以说一个h有序的数组就是h个互相独立的有序数组编织在一起组成的一个数组.

以23, 10, 4, 1的步长序列进行希尔排序

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void sort(Comparable[] a) {
		int h = 1;
		while (h < a.length / 3) {
			// h sequence 1,4,13,40,121,364,1093,...
			h = h * 3 + 1;
		}
		while (h >= 1) {
			for (int i = h; i < a.length; i++) {
				// a[i] insert to a[i-h],a[i-2*h],a[i-3*h]...
				for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
					exch(a, j, j - h);
				}
			}
			h = h / 3;
		}
	}

归并排序

归并排序是分治算法的典型应用.所谓归并即是将两个有序的数组归并成一个更大的有序数组.

它有一个主要的缺点就是它需要额外的空间(辅助数组)并且所需的额外空间和N成正比.

合并过程

  1. 申请空间,使其大小为两个已有序序列之和,该空间用于存放合并后的序列
  1. 声明两个指针,最初位置分别为两个有序序列的起始位置
  1. 比较两个指针所指向的元素,选择相对小的元素放入合并空间中,并移动指针到下一个位置
  1. 重复步骤3直到某一指针到达序列尾部
  1. 将另一序列剩下的所有元素直接放入合并序列尾

自顶向下的归并排序

自顶向下即是从顶部化整为零地递归解决问题.

例如:要对数组a[lo..hi]进行排序,需要先将它切分为a[lo..mid]与a[mid+1..hi]两部分,分别通过递归调用将它们单独排序,最后将有序的子数组归并为最终的排序结果.

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
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
	private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
		// copy a[] to aux[]
		for (int k = lo; k <= hi; k++) {
			aux[k] = a[k];
		}
		// merge back to a[]
		int i = lo, j = mid + 1;
		for (int k = lo; k <= hi; k++) {
			if (i > mid) {
				a[k] = aux[j++];
			} else if (j > hi) {
				a[k] = aux[i++];
			} else if (less(aux[j], aux[i])) {
				a[k] = aux[j++];
			} else {
				a[k] = aux[i++];
			}
		}
	}
	
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
	private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
		if (hi <= lo)
			return;
		int mid = lo + (hi - lo) / 2;
		sort(a, aux, lo, mid);
		sort(a, aux, mid + 1, hi);
		merge(a, aux, lo, mid, hi);
	}

自底向上的归并排序

自底向上则是循序渐进地解决问题.

实现思路是先归并那些微型数组,然后再成对归并得到的子数组,直到将整个数组归并在一起.

可以先进行两两归并(每个元素想象成一个大小为1的数组),然后进行四四归并(将两个大小为2的数组归并成一个有四个元素的数组),然后是八八归并…..(一直下去)在每一轮归并中,最后一次归并的第二个子数组可能比第一个子数组要小,如果不是的话所有归并中两个数组大小都应该一致.

1
2
3
4
5
6
7
8
9
10
11
12
//merge函数与自顶向下中的一致
public static void sort(Comparable[] a) {
		int N = a.length;
		Comparable[] aux = new Comparable[N];
		for (int len = 1; len < N; len *= 2) {
			for (int lo = 0; lo < N - len; lo += len + len) {
				int mid = lo + len - 1;
				int hi = Math.min(lo + len + len - 1, N - 1);
				merge(a, aux, lo, mid, hi);
			}
		}
	}

优化

  • 如果数组很小,那么频繁的递归调用效率会很差,所以可以使用插入排序(或选择排序等)来处理小规模的子数组.

    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
    private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
    	int i = lo, j = mid + 1;
    	for (int k = lo; k <= hi; k++) {
    		if (i > mid) {
    			dst[k] = src[j++];
    		} else if (j > hi) {
    			dst[k] = src[i++];
    		} else if (less(src[j], src[i])) {
    			dst[k] = src[j++];
    		} else {
    			dst[k] = src[i++];
    		}
    	}
    }
    private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
    	// if (hi <= lo) return;
    	if (hi <= lo + CUTOFF) {
    		insertionSort(dst, lo, hi);
    		return;
    	}
    	int mid = lo + (hi - lo) / 2;
    	sort(dst, src, lo, mid);
    	sort(dst, src, mid + 1, hi);
    	// using System.arraycopy() is a bit faster than the above loop
    	if (!less(src[mid + 1], src[mid])) {
    		System.arraycopy(src, lo, dst, lo, hi - lo + 1);
    		return;
    	}
    	merge(src, dst, lo, mid, hi);
    }
    // using insertion sort handle small array
    private static void insertionSort(Comparable[] a, int lo, int hi) {
    	for (int i = lo; i <= hi; i++) {
    		for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
    			exch(a, j, j - 1);
    		}
    	}
    }
    public static void sort(Comparable[] a) {
    	Comparable[] aux = a.clone();
    	sort(aux, a, 0, a.length - 1);
    }

快速排序

快速排序又称划分交换排序,它也是一种分治的排序算法.

快速排序有一个潜在的缺点,在切分不平衡时这个程序可能会极为低效,所以需要在快速排序前将数组随机排序来避免这种情况.

它将一个数组切分成两个子数组,将两部分独立地排序.它与归并排序不同的地方在于:

  • 归并排序将数组分成两个子数组分别排序,最终将有序的子数组归并以致整个数组排序.
  • 快速排序将数组排序的方式则是当两个子数组都有序时,整个数组也就是有序的了.
  • 在归并排序中,递归调用发生在处理整个数组之前;而在快速排序中,递归调用发生在处理整个数组之后.
  • 在归并排序中,一个数组会被等分为两半,而在快速排序中,切分的位置取决于数组的内容.

运行过程

  1. 先从数列中挑选出一个基准,可以为a[lo],它是被确认为排定的元素.
  1. 从数组的左端(左指针)开始向右扫描直到找到一个大于等于基准的元素.
  1. 从数组的右端(右指针)开始向左扫描直到找到一个小于等于基准的元素.
  1. 这两个元素即是没有排定的,交换它们的位置(保证了左指针i的左侧元素都不大于基准,右指针j的右侧元素都不小于基准).
  1. .当两个指针相遇时,将基准和左子数组最右侧的元素(a[j])交换然后返回j即可.

代码实现

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
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
	// and return the index j.
	private static int partition(Comparable[] a, int lo, int hi) {
		int i = lo; // left point
		int j = hi + 1; // right point
		Comparable v = a[lo]; // partition element
		while (true) {
			// scan left point
			while (less(a[++i], v)) {
				if (i == hi)
					break;
			}
			// scan right point
			while (less(v, a[--j])) {
				if (j == lo)
					break;
			}
			// check if point cross
			if (i >= j)
				break;
			exch(a, i, j);
		}
		// put partition element v to a[j]
		exch(a, lo, j);
		// now a[lo..j-1] <= a[j] <= a[j+1..hi]
		return j;
	}
	
	private static void sort(Comparable[] a, int lo, int hi) {
		if (hi <= lo)
			return;
		int j = partition(a, lo, hi);
		sort(a, lo, j - 1);
		sort(a, j + 1, hi);
	}
	
	public static void sort(Comparable[] a) {
		shuffle(a);
		sort(a, 0, a.length - 1);
	}
	
	// random sort an array
	private static void shuffle(Object[] a) {
		if (a == null)
			throw new IllegalArgumentException("array is null.");
		Random random = new Random();
		int N = a.length;
		for (int i = 0; i < N; i++) {
			int j = i + random.nextInt(N - i);
			Object temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}

三向切分的快速排序

当存在大量重复元素的情况下,快速排序的递归性会使元素全部重复的子数组经常出现,这就有很大的改进潜力,将当前快速排序从线性对数级别的性能提升至线性级别.

一个简单的思路是将数组切分为三部分,分别对应小于、等于、大于切分元素的数组元素.

在实现中,维护一个左指针lt使得a[lo..lt-1]的元素都小于基准,右指针gt使得a[gt+1..hi]中的元素都大于基准,一个指针i使得a[lt..i-1]中的元素都等于基准,a[i..gt]中的元素都还未确定.

  1. a[i]小于基准,将a[lt]和a[i]交换,lt++&i++.
  1. a[i]大于基准,将a[gt]和a[i]交换,gt–.
  1. a[i]等于基准,i++.

以上操作都会保证数组元素不变且缩小gt-i的值(这样循环才会结束).除非和切分元素相等,其他元素都会被交换.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// quicksort the subarray a[lo .. hi] using 3-way partitioning
	private static void sort(Comparable[] a, int lo, int hi) {
		if (hi <= lo)
			return;
		int lt = lo, i = lo + 1, gt = hi;
		Comparable v = a[lo]; // partition element
		// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
		while (i <= gt) {
			int cmp = a[i].compareTo(v);
			if (cmp < 0) {
				exch(a, i++, lt++);
			} else if (cmp > 0) {
				exch(a, i, gt--);
			} else {
				i++;
			}
		}
		sort(a, lo, lt - 1);
		sort(a, gt + 1, hi);
	}

堆排序

堆排序是基于堆的优先队列实现的一种排序算法.

优先队列

优先队列是一种支持删除最大(最小)元素和插入元素的数据结构,它的内部是有序的,任意优先队列都可以变成一种排序方法.

堆

堆是一种数据结构,它通常可以被看作为一棵树的数组对象.将根节点作为最大数的叫做最大堆,反之,将根节点作为最小数的叫做最小堆.

堆是一个近似完全二叉树的结构,同时又满足了堆的性质:每个元素都要保证大于(小于)等于它的子节点的元素.

在一个堆中,根据根节点的索引位置不同,计算父节点与子节点位置的算法也不同.

  • 当数组起始位置为0时,位置k的节点的父节点为(k - 1)/2,它的两个子节点为2k+1,2k+2.
  • 当数组起始位置为1时(即不使用索引0),位置k的节点的父节点为k/2,它的两个子节点为2k,2k+1.

为了保证堆有序,需要支持两个操作用于打破堆的状态,然后再遍历堆并按照要求将堆的状态恢复,这个过程叫做堆的有序化.

  • 由下至上的堆有序化(上浮) : 如果堆的有序状态因为某个节点变得比它的父节点更大而被打破时,那么就需要通过交换它和它的父节点来修复堆,将这个节点不断向上移动直到遇到了一个更大的父节点.(如果是最小堆,比较的逻辑相反).

    1
    2
    3
    4
    5
    6
    7
    // 在本文中,均不使用数组的0索引
     private void swim(int k) {
         while (k > 1 && less(k/2, k)) {
             exch(a,k, k/2);
             k = k/2;
          }
       }

  • 由上至下的堆有序化(下沉) : 如果堆的有序状态因为某个节点变得比它的两个子节点或是其中之一更小了而被打破时,需要通过将它和它的两个子节点中的较大者交换来修复堆,将这个节点向下移动直到它的子节点都比它更小或是到达了堆的底部.(如果是最小堆,比较的逻辑想法)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // n为数组长度
    private void sink(int k) {
         while (2*k <= n) {
             int j = 2*k;
             if (j < n && less(j, j+1)) j++;
             if (!less(a[k],a[j])) break;
             exch(a,k, j);
             k = j;
         }
     }

运行过程

堆排序可以分为两个阶段.

  1. 堆的构造阶段,将原始数组重新组织安排进一个堆中.从右至左用sink()函数,构造子堆,数组的每个位置都已经是一个子堆的根节点.只需要扫描数组中的一半元素,因为我们可以跳过大小为1的子堆.最后在位置1上调用sink()函数,结束扫描.
  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
public static void sort(Comparable[] a) {
		int N = a.length;
		// construction max heap
		for (int k = N / 2; k >= 1; k--) {
			sink(a, k, N);
		}
		// sink sort
		while (N > 1) {
			// the biggest element (root) swap smallest element then heap shrink
			exch(a, 1, N--);
			// new root element sink
			sink(a, 1, N);
		}
	}
	
	private static void sink(Comparable[] pq, int k, int n) {
		while (2 * k <= n) {
			int j = 2 * k;
			if (j < n && less(pq, j, j + 1))
				j++;
			if (!less(pq, k, j))
				break;
			exch(pq, k, j);
			k = j;
		}
	}
	private static boolean less(Comparable[] pq, int i, int j) {
		return pq[i - 1].compareTo(pq[j - 1]) < 0;
	}
	private static void exch(Object[] pq, int i, int j) {
		Object swap = pq[i - 1];
		pq[i - 1] = pq[j - 1];
		pq[j - 1] = swap;
	}

总结

名称 是否稳定 是否为原地排序 时间复杂度 空间复杂度 备注
冒泡排序 是 是 O(N^2) O(1) （无序区，有序区）。从无序区通过交换找出最大元素放到有序区前端。
选择排序 否 是 O(N^2) O(1) （有序区，无序区）。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
插入排序 是 是 介入N和N^2之间 O(1) （有序区，无序区）。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。
希尔排序 否 是 O(N log^2 N) O(1) 每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1。
快速排序 否 是 O(N log N) O(logN) （小数，基准元素，大数）。在区间中随机挑选一个元素作基准，将小于基准的元素放在基准之前，大于基准的元素放在基准之后，再分别对小数区与大数区进行排序。
三向快速排序 否 是 介于N和NlogN之间 O(logN) 对含有大量重复元素的输入数据效率较高。
归并排序 是 否 O(N log N) O(N) 把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。
堆排序 否 是 O(N log N) O(1) （最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。

在大多数实际情况中,快速排序是最佳选择.如果稳定性很重要而空间又不是问题的情况下,归并排序可能是最好的.但是在运行时间至关重要的任何排序应用中应该认真地考虑使用快速排序.

在JDK中,Arrays.sort()选择了根据不同的参数类型,来使用不同的排序算法.如果是原始数据类型则使用三向切分的快速排序,对引用类型则使用归并排序.

end

  • Email : sylvanassun_xtz@163.com
  • 文中的完整实现代码见我的GitHub & Gist
分享