PENGLLRN | 有时低头看路，有时仰望星空
2019-03-14 | 算法 | UNLOCK

十大经典排序算法

约定

元素可排序

因为待排序的元素是任意类型的，如果定义每个元素之间的大小关系必须要是确定的，不能模棱两可。因此待排序的元素需要实现Java的Comparable接口中的compareTo()方法。

排序结果默认是从小到大。

元素的存储数据结构

  1. 固定数组

辅助方法

两个元素交换

两个元素的快速比较

基于上述约定，设计一个排序抽象类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public abstract class Sort<T extends Comparable<T>> {
    public abstract void sort(T[] nums);

    /**
     * 交换数组nums的两个位置的值
     */
    public void swap(T[] nums,int i, int j){
        T temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 比较两个数的大小，如果i大于j，则返回true
     */
    public boolean greater(T i, T j){
        return i.compareTo(j) > 0;
    }
}

数组特性

完全随机

排序算法的特性

时间复杂度、空间复杂度

最好、最坏情况，均摊情况

稳定性

1.选择排序

选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。

特点：选择排序需要约==N^2^/2== 次比较和约N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
Java实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class SelectSort{
	public void sort(int[] nums){
		if(nums == null || nums.length <= 1)
			return;
		for (int i = 0; i < nums.length; i++) {
			int min = i;
			for (int j = i + 1; j < nums.length; j++) {
				if(nums[j] < nums[min])
					min = j;
			}
			swap(nums, min, i);
		}
	}

	private void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

2.冒泡排序

从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。

时间复杂度：N^2^/2次比较，交换次数和逆序数有关，最坏情况每次比较都交换，即N^2^/2次交换。

它的运行时间与输入有关，可以提前终止，最好情况只需要执行N-1次比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class BubbleSort{
	public void sort(int[] nums){
		if(nums == null || nums.length <= 1)
			return;
		boolean isSort = false;
		for (int i = nums.length - 1; i>= 0 && !isSort; i--) {
			isSort = true;
			for (int j = 0; j < i; j++) {
				if(nums[j] > nums[j + 1]){
					swap(nums, j, j + 1);
					isSort = false;
				}
			}
		}
	}
}

3.插入排序

直接插入排序

每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。

直接插入排序基本思想：当插入第i（i>1）个元素时，前面的data[0],data[1]……data[i-1]已经排好序。这时用data[i]的排序码与data[i-1],data[i-2],……的排序码顺序进行比较，找到插入位置即将data[i]插入，原来位置上的元素向后顺序移动。

对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。

插入排序的复杂度取决于数组的初始顺序，如果数组已经部分有序了，逆序较少，那么插入排序会很快。

  • 平均情况下插入排序需要 ~N^2^/4 比较以及 ~N^2^/4 次交换；
  • 最坏的情况下需要 ~N^2^/2 比较以及 ~N^2^/2 次交换，最坏的情况是数组是倒序的；
  • 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。
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
class InsertSort{
	public void sort(int[] nums){
		if(nums == null || nums.length <= 1)
			return;
		for (int i = 1; i < nums.length; i++) {
			for (int j = i; j >= 0 && nums[j] > nums[j - 1]; j--) {
				swap(nums, j, j -1);
			}
		}
	}

	private void swap(int[] nums, int i,int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}

class InsertSortPlus{
	public void sort(int[] nums){
		if(nums == null || nums.length <= 1)
			return;
		for (int i = 1; i < nums.length; i++) {
			if(nums[i] >= nums[i])
				continue;
			int ex = binarySearch(nums, i, nums[i]);
			while(ex != i){
				swap(nums, ex, i);
				ex = binarySearch(nums, i, nums[i]);
			}
		}
	}

	private int binarySearch(int[] nums,int len, int val){
		int left = 0;
		int right = len;
		while(left < right){
			int mid = left + (right - left) / 2;
			if(val >= nums[mid])
				left = mid + 1;
			else
				right = mid;
		}
		return left;
	}

	private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

代码中使用了一个小技巧，将判断条件放到循环语句里面。

折半插入排序

折半插入排序基本思想：设元素序列data[0],data[1],……data[n-1]。其中data[0],data[1],……data[i-1]是已经排好序的元素。在插入data[i]时，利用折半搜索法寻找data[i]的插入位置。

因此折半插入排序的时间开销往往是直接插入排序开销的一半。

4.希尔排序

改进：对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。

方法：希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数gap（小于N）作为间隔将全部元素分为gap个子序列，所有距离为gap的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔gap，重复上述子序列划分和排序工作。直到最后取gap=1，将所有元素放在同一个子序列中排序为止。 由于开始时，gap的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期gap取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

关于希尔排序gap（间隔）的取法:
间隔gap的取法有各种方案。最初shell提出取increment=n/2向下取整，gap=gap/2向下取整，直到gap=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取gap=n/3向上取整，还有人提出都取奇数为好，也有人提出gap互质为好，应用不同的序列会使希尔排序算法的性能有很大的差异。

特点：希尔排序是一种不稳定的排序算法，因为相等的元素在排序前后顺序可能发生变化！
2

示例算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ShellSort<T extends Comparable<T>> extends Sort<T> {
    @Override
    public void sort(T[] nums) {
        int gap = 1;
        while (gap < nums.length / 3) { //gap向上取整，看了好几篇文章，这个初始gap取得都不一样
            gap = 3 * gap + 1;//1，4，13，40.....
        }

        while (gap >= 1) {
            for (int i = gap; i < nums.length; i++) {
                for (int j = i; j >= gap && greater(nums[j - gap], nums[j]); j -= gap) {
                    swap(nums, j - gap, j);
                }
            }
            gap = gap / 3;
        }
    }
}

希尔排序的时间复杂度很难确定，但其运行时间达不到平方级别，低于插入排序。后面几种高级排序算法也只会比希尔算法快两倍左右。

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
class HeapSort{
	public void sort(int[] nums){
		if(nums == null || nums.length <= 1)
			return;
		int len = nums.length;
		buildHeap(nums);
		for (int i = 0; i < nums.length - 1; i++) {
			swap(nums, 0 , --len);
			heapify(nums, 0, len);
		}
	}

	private void buildHeap(int[] nums){
		for (int i = nums.length / 2; i >= 0; i--) {
			heapify(nums, i, nums.length);
		}
	}

	private void heapify(int[] nums,int i,int len){
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		int maxChild = i;
		if(left < len && nums[maxChild] < nums[left]){
			maxChild = left;
		}
		if(right < len && nums[maxChild] < nums[left]){
			maxChild = right;
		}
		if(maxChild != i){
			swap(nums, i , maxChild);
			heapify(nums, maxChild, len);
		}
	}

	private void swap(int[] nums, int i,int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[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
30
31
32
33
34
35
36
37
38
class MergeSort{
	private int[] aux;

	public void sort(int[] nums){
		if(nums == null || nums.length <= 1)
			return;
		aux = new int[nums.length];
		sortCore(nums, 0 , nums.length - 1);
	}

	private void sortCore(int[] nums, int left, int right){
		if(right <= left)
			return;
		int mid = left + (right - left) / 2;
		sortCore(nums, left, mid);
		sortCore(nums, mid + 1, right);
		merge(nums, left, mid ,right);
	}

	private void merge(int[] nums, int left , int mid , int right){
		for (int i = left; i <= right; i++) {
			aux[i] = nums[i];
		}

		int i = left;
		int j = mid + 1;
		for (int k = left; k < right; k++) {
			if(i > mid)
				nums[k] = aux[j++];
			else if(j > right)
				nums[k] = aux[i++];
			else if(aux[i] <= aux[j])
				nums[k] = aux[i++];
			else
				nums[k] = aux[j++];
		}
	}
}

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

class QuickSort{
	public void sort(int[] nums){
		if(nums == nums || nums.length <= 1)
			return;
		sortCore(nums, 0, nums.length - 1);
	}

	private void sortCore(int[] nums,int left, int right){
		if(right <= left)
			return;
		int partition = partition(nums, left, right);
		sortCore(nums, left, partition - 1);
		sortCore(nums, partition + 1, right);
	}

	private void partition(int[] nums, int left, int right){
		int pivot = nums[left];
		int i = left;
		int j = right + 1;
		while(true){
			while(i < right && nums[++i] <= pivot);
			while(j > left && nums[--j] >= pivot);
			if(i >= j)
				break;
			swap(nums, i, j);
		}
		swap(nums, left, j);
		return j;
	}

	private void swap(int[] nums, int i, int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}

本文参考：

  1. 理解希尔排序的排序过程

  2. CyC2018/CS-Notes:算法-排序

  3. 公众号：五分钟学算法
面试 算法

评论加载中