选择排序

  1. 排序原理
  • 如其名：每轮选择出最小的元素，与待排序区间最左边元素交换位置。
  • 待排序区间的左边是排好序的区间
  • 每轮能排好一个数，待排序区间长度每轮减小1
  1. 代码实现
    选择排序Java实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    import java.util.Arrays;

    public class Sort_SelectionSort {
    	public static void selectionSort(int[] arr) {
    		for(int i=0; i<arr.length-1; i++) {	// 寻找arr.length-1轮
    			int minIndex = i; 	// minIndex保存最小元素的位置，初始化为i，每轮排序后随着i++向右移1位
    			for(int j=i+1; j<arr.length; j++) {
    				minIndex = arr[j]<arr[minIndex]?j:minIndex;	// 更新最小元素的位置
    			}
    			swap(arr,i,minIndex);	// 每轮将最小的元素找到，将其与待排序的最左端元素交换
    		}
    	}
    	public static void swap(int[] arr, int i, int j) {	// 元素交换
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		selectionSort(array);
    		System.out.println(Arrays.toString(array));
    	}
    }
  2. 性能分析
    时间复杂度：O(N^2) ，空间复杂度：O(1)

冒泡排序

  1. 排序原理
  • 如其名：每轮从左至右依次将相邻元素比较，比较的这俩元素的顺序和期望顺序不一致时交换他俩位置，比较区间从左移到右，形似冒泡。
  • 冒泡排序每轮通过多个交换位置操作，最终确定一个最大值放在待排序区间的最右边。
  • 冒泡排序待排序区间右边是排好序的区间
  • 每轮排好一个数，待排序区间长度每轮减小1
  1. 代码实现
    冒泡排序Java实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    import java.util.Arrays;

    public class Sort_BubbleSort {
    	public static void bubbleSort(int[] arr) {
    		for(int i = arr.length-1; i > 0; i--) {	// 执行arr.length-1轮
    			for(int j = 0; j < i; j++) {	// 要排序的区间[j, i]
    				if(arr[j] > arr[j+1]) {
    					swap(arr, j, j+1);	// 相邻元素比较，如果左边元素比右边元素更大则交换俩元素位置
    				}
    			}
    		}
    	}
    	public static void swap(int[] arr, int i, int j) {	// 交换i,j位置的元素
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		bubbleSort(array);
    		System.out.println(Arrays.toString(array));
    	}
    }
  2. 性能分析
    时间复杂度：O(N^2) ，空间复杂度：O(1)

插入排序

  1. 排序原理
  • 如其名：从左至右依次对前i位完成排序，新加入的这1位就好像被插入到前i位中适合他的位置。
  • 每轮只给1位找到最合适的位置，这1位后面的数在本轮中既不移动，也不参与比较或运算。
  • 由于从左至右依次对前i位完成排序，因此不用多次重排，例如：先完成了前2位有序，则下一步要满足前三位有序就只需要将第三位与第二位比较，顺序不合适就交换继续往左比较插入到合适的位置就满足了前三位有序，若是顺序合适就直接满足了前三位有序，可以进行下一步操作了
  • 插入排序的时间复杂度与数据分布有关，原数据逆序时时间复杂度为 O(N^2)，原数据顺序时时间复杂度为 O(N)
  1. 代码实现
    插入排序Java实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    import java.util.Arrays;

    public class Sort_InsertSort {
    	public static void insertSort(int[] arr) {
    		for(int i = 1; i < arr.length; i++) {	// 从左至右依次对前i位完成排序，排序采用插入的方式
    			for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--) {	// 对要排序的端从最右边开始向左插入
    				swap(arr,j,j+1);
    			}
    		}
    	}
    	public static void swap(int[] arr, int i, int j) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		insertSort(array);
    		System.out.println(Arrays.toString(array));
    	}
    }
  2. 性能分析
    插入排序的时间复杂度与数据的分布有关，最差情况为 O(N^2) ，最好情况为 O(N) ，一般采用最差情况 O(N^2) 作为插入排序的时间复杂度估计，因此虽然和选择排序和冒泡排序时间复杂度都是 O(N^2) ，但实际运行时插入排序性能是更好一点的

归并排序

递归过程

递归是一种解决问题的思路，要完成递归过程要求以下几点特征：

  1. 要通过递归解决的问题是可分的，可将大问题拆分为多个可分的小问题
  2. 每一级递归中需要调用递归方法
  3. 递归方法中需要包含原子问题的解决办法
  4. 递归方法中需要包含大问题划分为小问题的步骤

例子，求数组最大值问题递归解决

递归求数组最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Recursion_getMax {	// 递归求数组最大值
	public static int recursionGetMax(int[] arr, int startIndex, int endIndex) {	// 求数组指定区间最大值
		if(startIndex==endIndex) {	// 原子问题的处理办法
			return arr[startIndex];
		}
		int mid = startIndex + ((endIndex-startIndex) >> 2);	// 问题拆解，求中点mid=start+(end-start)/2
		int leftMax = recursionGetMax(arr, startIndex, mid);	// 递归中调用递归
		int rightMax = recursionGetMax(arr, mid+1, endIndex);
		return Math.max(leftMax, rightMax);	// 最终的问题解决
	}
	
	public static void main(String[] args) {
		int[] array = {2,7,9,3,2,1,3,7,0,2};
		System.out.println(recursionGetMax(array,0,array.length-1));
	}
}

递归的过程其实是个二叉树遍历、压栈出栈的过程，当本级问题还有分支没求出来就将本级问题压栈，对下一级问题进行求解，下一级如果还有分支没有求出来就继续压栈，直到叶子节点求出答案后一步步出栈，一层层出嵌套，最终将原始问题求解出来。因此递归中要实现原子问题的求解，原始问题到原子问题的划分方法，每级中调用递归方法。

上面递归求数组最大值中中间值mid用 mid = start + ((end-start) >> 2) 的方式其实相当于 mid=start+(end-start)/2 ，而采用此方式是为了避免直接使用 mid=(start+end)/2 当 start , end 值过大时可能造成的溢出问题。

归并排序原理和实现

  1. 排序原理
  • 归并排序主要使用了递归的思路
  • 排序过程就是将要排序的部分划分为等分的左右两段，分别对两段进行归并排序，构成递归基本要求中的分段
  • 在每级递归将排好序的两段合并，构成递归基本要求中的问题求解
  • 同时还要定义原子问题的处理方式

  1. 代码实现

    归并排序Java实现
    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
    import java.util.Arrays;

    public class Sort_MergeSort {
    	public static void mergeSort(int[] arr, int L, int R) {	// 归并排序，数组arr从L到R区间
    		if(L==R) {
    			return;
    		}
    		int M = L + ((R-L)>>2);	// 中间index，二分归并排序
    		mergeSort(arr, L, M);
    		mergeSort(arr, M+1, R);
    		merge(arr, L, M, R);	// 排好序的左边和排好序的右边合并
    	}
    	
    	public static void merge(int[] arr, int L, int M, int R) {	// 排好序的左边和排好序的右边合并
    		int len = R-L+1;
    		int[] temp = new int[len]; 	// 辅助数组，长度同要排序的区间长度
    		int i = 0;	// 辅助数组中的指针，指向要放置的位置
    		int leftPointer = L;	// 定义一个左指针起始时指向左边区间起点
    		int rightPointer = M+1; 	// 定义一个右指针起始时指向右边区间起点
    		while(leftPointer<=M && rightPointer<=R) {	// 指针都没有超出两边区间时哪边小那边放在辅助数组里，并且指针后移
    			temp[i++] = (arr[leftPointer] <= arr[rightPointer]) ? arr[leftPointer++] : arr[rightPointer++];
    		}
    		while(rightPointer<=R) {	// 左边指针超界了说明左边区间已经放置完成了，则将右侧区间依次放入辅助数组
    			temp[i++] = arr[rightPointer++];
    		}
    		while(leftPointer<=M) {	// 右边指针超界了说明右边区间已经放置完成了，则将左侧区间依次放入辅助数组
    			temp[i++] = arr[leftPointer++];
    		}
    		// 将辅助数组赋值给原数组待排序区间
    		for(i=0; i<len; i++) {
    			arr[i+L] = temp[i];
    		}
    	}
    	
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		mergeSort(array, 0 , array.length-1);
    		System.out.println(Arrays.toString(array));
    	}
    }

  2. 性能分析
    归并排序采用递归的方式完成，时间复杂度应按照递归时间复杂度计算方法来计算，为 O(N*logN)，空间复杂度是 O(N)，因为在将排好序的两段合并时利用了与待排序部分等长的辅助数组

拓展-小数求和

题目：一个数组中，一个元素左边所有比该元素小的元素称为该元素的小数，每个元素的小数求和成为该数组的小数和，要求设计一个求数组小数和的方法。
解决思路：当然可以采用遍历的方式对每个元素求小数和，最后汇总，我们在这里思考如何利用归并思想来解决此题目降低时间复杂度，这里我提供两种思路

  1. 利用归并排序中的递归思想
  2. 利用归并排序中的排序和递归思想
    下面是我自己的实现代码，两种实现方式的代码差别仅在于 merge() 部分实现方式不同，下面代码中 merge1() 对应思路1， merge2() 对应思路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
    51
    52
    53
    54
    55
    56
    57
    58
    import java.util.Arrays;

    public class Merge_smallNum {	// 求小数和
    	public static int smallNum(int[] arr,int L, int R) {
    		if(L==R) {	// 叶子节点处理
    			return 0;
    		}
    		int M = L+((R-L)>>2);	// 中点
    //		return smallNum(arr, L, M)+smallNum(arr, M+1, R)+merge1(arr, L, M, R);	// 在归并过程中通过遍历完成小数求和
    		return smallNum(arr, L, M)+smallNum(arr, M+1, R)+merge2(arr, L, M, R);	// 在归并过程中通过下标完成小数求和
    		
    	}
    	// merge1通过在归并过程中遍历求和，merge2通过在归并过程中同时进行排序并用下标计算小数求和
    	public static int merge1(int[] arr, int L, int M, int R) {	// 左右两部分无序，通过遍历方式
    		int temp = 0;
    		int pl= L;
    		int pr = M+1;
    		while(pr<=R) {
    			while(pl<=M) {
    				temp += (arr[pl]<arr[pr]) ? arr[pl] : 0;	// 注意此处要严格 < ，而不是归并排序中<或<=的情况
    				pl++;	
    			}
    			pr++;
    			pl=L;
    		}
    		return temp;
    	}
    	public static int merge2(int[] arr, int L, int M, int R) {	// 左右两部分有序，通过下标
    		int temp = 0;
    		int helper[] = new int[R-L+1];	// 用来归并排序的辅助数组
    		int i = 0;
    		int pl = L;		// 左指针指向左区间最左边
    		int pr = M+1;	// 右指针指向有区间最左边
    		while(pl<=M && pr<=R) {
                // helper[i++] = (arr[pl] <= arr[pr]) ? arr[pl++] : arr[pr++];	// 原归并排序的内容
    			// 注意此处要严格 < ，而不是归并排序中<或<=的情况
    			temp += (arr[pl] < arr[pr]) ? arr[pl]*(R-pr+1) : 0;
    			helper[i++] = (arr[pl] < arr[pr]) ? arr[pl++] : arr[pr++];
    		}
    		while(pl<=M) {
    			helper[i++] = arr[pl++];
    		}
    		while(pr<=R) {
    			helper[i++] = arr[pr++];
    		}
    		for(i=0; i<helper.length; i++) {
    			arr[i+L] = helper[i];
    		}
    		return temp;
    		
    	}
    	
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		System.out.println(smallNum(array, 0, array.length-1));
    		System.out.println(Arrays.toString(array));
    	}
    }
    思路1利用了归并排序中的递归思想，并没有对数组进行排序，只是在递归部分将原来的排序改成了小数求和
    思路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
import java.util.Arrays;

public class Merge_InversePair {
	public static void inversePair(int[] arr, int L, int R) {
		if(L==R) {	// 原子问题的处理
			return;
		}
		int M = L + ((R-L)>>2);	// 中间点
		inversePair(arr, L, M);
		inversePair(arr, M+1, R);
		merge(arr, L, M, R);
	}
	
	public static void merge(int[] arr, int L, int M, int R) {
		int[] helper = new int[R-L+1];	// 归并的辅助数组
		int i = 0;
		int pl = L;
		int pr = M+1;
		while(pl <= M && pr <= R) {
			if(arr[pl] > arr[pr]) {
				for(int j=0; j<(R-pr+1);j++) {
					System.out.println("<"+arr[pl]+"-"+arr[pr+j]+">");
				}
			}
			helper[i++] = (arr[pl] > arr[pr]) ? arr[pl++] : arr[pr++];
		}
		while(pl<=M) {
			helper[i++] = arr[pl++];
		}
		while(pr<=R) {
			helper[i++] = arr[pr++];
		}
		for(i = 0; i<helper.length; i++) {
			arr[L+i] = helper[i];
		}
	}
	
	public static void main(String[] args) {
		int[] array = {2,7,9,3,2,1,3,7,0,2};
		inversePair(array, 0, array.length-1);
		System.out.println(Arrays.toString(array));
	}
}

快速排序

快速排序，常称为快排，在介绍快排之前，先通过荷兰国旗问题引入一种排序思路

荷兰国旗问题

荷兰国旗问题1.0：给一个阈值，将数组中数按照左边数都小于或等于阈值，右边数都大于阈值重新排列，要求时间复杂度O(N)
荷兰国旗问题2.0：给一个阈值，将数组中数划分为三部分，从左至右依次为小于区，等于区，大于区，要求时间复杂度O(N)
这里提供一种荷兰国旗问题的求解思路：将数组看成三部分，小于区在左，大于区在右，中间是等于区，用两个指针分别指向小于区的最右端，大于区的最左端，如此便能将三个区域定位并划分，然后用第三个指针指向要检验的数，从最左边开始依次向右，根据比较结果将元素分配到对应区域，下面是一种实现方式：

荷兰国旗问题
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
import java.util.Arrays;

public class DutchFlagProblem {
	// 简化荷兰国旗问题，要求阈值左边是小于或等于阈值，右边是大于阈值即可
	public static void dutchFlag1(int[] arr, int threshold) {	
		int pl = 0;	// 定义一个指向小于等于区域的指针，起始为区间最左侧
		int pr = arr.length-1;	// 定义一个大于区域的指针，起始为区间最右侧
		while(pl<pr) {	// 当pl=pr时就将数组中所有元素都和阈值比较过了，因此这里不取到等号
			if(arr[pl]<=threshold) {	// 比较元素满足小于等于阈值
				pl++;	// 落在小于等于区域时，直接将小于等于区域指针后移
			}
			else {	// 比较元素满足大于阈值
				swap(arr, pl, pr);	// 落在大于区域时，将大于区域指针同当前元素交换位置
				pr--;	// 让大于区域指针前移,原来的大于区域指针指向的位置已经被大于阈值的元素占据
			}
		}
	}
	// 原版的荷兰国旗问题，与简化版差别在于要求等于阈值的元素要位于小于区域和大于区域的中间
	public static void dutchFlag2(int[] arr, int threshold) {
		int pl = 0;
		int pr = arr.length-1;
		int equalCount = 0;
		while(pl<pr-equalCount) {
			if(arr[pl]<threshold) {
				pl++;
			}
			else if(arr[pl] == threshold) {
				swap(arr, pl, pr-equalCount++);
			}else {	// 实现方式上完整的荷兰国旗问题同简化版相比多了相等区域，因此当出现大于阈值时，要通过两次swap完成
				swap(arr, pr, pr-equalCount);	// 第一次swap将相等区域最右端的元素前移到相等区域最左端，给新的大于区域留出位置
				swap(arr, pl, pr--);	// 大于元素放置在刚留出的位置
			}
		}
		while(pl == pr-equalCount) {	// 这里多加个判断是为了避免两次交换时将pl位置的元素转移了
			if(arr[pl]>threshold) {
				int temp = arr[pl];
				swap(arr, pr, pr-equalCount);
				arr[pr] = temp;
			}	
			pl++;
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static void main(String[] args) {
		int[] array = {2,7,9,3,2,1,3,7,0,2};
		int threshold = 7;
		dutchFlag1(array, threshold);
//		dutchFlag2(array, threshold);
		System.out.println(Arrays.toString(array));
	}
}

快排原理和实现

在解决 荷兰国旗问题 后我们看到了根据阈值划分数组的方法，那如果将此过程放在递归中，每一层递归中对区间进行大小划分，能否实现一种排序？
基于此思路实现的就是快速排序，快速排序中不再是指定一个阈值，而是采用数组的最后一个元素作为阈值，此元素不参与排序，在其余部分排好序后直接与大于区域第一位交换位置即可，快速排序也有多种实现方式

  1. 每个区间只划分为小于等于区和大于区两个部分
    快排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
    import java.util.Arrays;

    public class Sort_quickSort_1 {
    	public static void quickSort(int[] arr, int L, int R) {
    		if(L>=R) {
    			return;
    		}
    		int thresholdLine = partition(arr, L, R);	// 一次partition将数组根据阈值分为左右两侧
    		quickSort(arr, L, thresholdLine);
    		quickSort(arr, thresholdLine+1, R);
    	}
    	
    	// partition部分将数组分为小于等于区域和大于区域
    	public static int partition(int[] arr, int L, int R) {
    		int threshold = arr[R];	// 以区间最后一位为threshold,partition结束后与大于区域第一位交换位置
    		int pointerSmall = L-1;	// pointerSmall指向小于区域第一个元素位置
    		int pointer = L;	// pointer指向当前要比较的元素位置
    		while(pointer < R) {	// threshold所在的最后一个元素不要参与比较,partition后会直接与大于区域第一个元素交换位置
    			if(arr[pointer] <= threshold) {
    				swap(arr, pointer++, ++pointerSmall);	// 小于等于时与小于区域的下一个元素交换位置，指针后移
    			}
    			else {
    				pointer++;	// 当前位置比threshold大时pointer直接后移
    			}
    		}
    		swap(arr, R, pointerSmall+1);	// 数组最后一位即阈值与小于区域右边第一位交换位置
    		return pointerSmall;	// 返回小于区域的右边界
    	}
    	
    	public static void swap(int[] arr, int i, int j	) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		quickSort(array, 0, array.length-1);
    		System.out.println(Arrays.toString(array));
    	}
    }
    方式1只需要两个指针，一个指向小于等于区域最右端，另一个指向当前要检查的位置，小于等于区会推着大于区往后走
  2. 每个区间划分为小于区、等于区和大于区三部分
    快排2.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
    import java.util.Arrays;

    public class Sort_quickSort_2 {
    	public static void quickSort(int[] arr, int L, int R) {
    		if(L>=R) {
    			return;
    		}
    		int[] thresholdLine = partition(arr, L, R);	// 一次partition将数组根据阈值分为左中右三部分
    		quickSort(arr, L, thresholdLine[0]);
    		quickSort(arr, thresholdLine[1], R);
    	}
    	
    	// partition部分将数组分为小于区域、等于区域和大于区域
    	public static int[] partition(int[] arr, int L, int R) {
    		int threshold = arr[R];	// 以区间最后一位为threshold,partition结束后与大于区域第一位交换位置
    		int pointerSmall = L-1;	// pointerSmall指向小于区域最右端
    		int pointerBig = R;	// pointerBig指向大于区域的最左端,因为使用最后一位作为threshold,因此初始化为R,而不是R+1
    		int pointer = L;	// pointer指向当前要比较的元素位置
    		while(pointer < pointerBig) {	// threshold所在的最后一个元素不要参与比较,partition后会直接与大于区域第一个元素交换位置
    			if(arr[pointer] < threshold) {
    				swap(arr, pointer++, ++pointerSmall);	// 小于等于时与小于区域的下一个元素交换位置，指针后移
    			}
    			else if(arr[pointer] > threshold){
    				swap(arr, pointer, --pointerBig);// 当前位置比threshold大时pointer位置与pointerBig位置交换，pointerBig前移
    			}
    			else {
    				pointer++;
    			}
    		}
    		swap(arr, R, pointerBig);	// 数组最后一位即阈值与小于区域右边第一位交换位置
    		int[] ret = {pointerSmall, pointerBig};
    		return ret;	// 返回小于区域的右边界
    	}
    	
    	public static void swap(int[] arr, int i, int j	) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		quickSort(array, 0, array.length-1);
    		System.out.println(Arrays.toString(array));
    	}
    }

    方式2划分为三部分，就需要三个指针了，一个指向小于区最右位置，一个指向大于区最左位置，一个指向要检查的位置
  3. 在划分为三部分的基础上，选择随机元素作为阈值
    快排3.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
    import java.util.Arrays;

    public class Sort_quickSort_3 {
    	public static void quickSort(int[] arr, int L, int R) {
    		if(L>=R) {
    			return;
    		}
    		int randomThre = (int)(Math.random()*(R-L+1)+L);
    		swap(arr, randomThre, R);	// 将随机的位置与最后一位交换，partition按照原来采用最后一位为threshold不变
    		int[] thresholdLine = partition(arr, L, R);	// 一次partition将数组根据阈值分为左中右三部分
    		quickSort(arr, L, thresholdLine[0]);
    		quickSort(arr, thresholdLine[1], R);
    	}
    	
    	// partition部分将数组分为小于区域、等于区域和大于区域
    	public static int[] partition(int[] arr, int L, int R) {
    		int threshold = arr[R];	// 以区间最后一位为threshold,partition结束后与大于区域第一位交换位置
    		int pointerSmall = L-1;	// pointerSmall指向小于区域最右端
    		int pointerBig = R;	// pointerBig指向大于区域的最左端,因为使用最后一位作为threshold,因此初始化为R,而不是R+1
    		int pointer = L;	// pointer指向当前要比较的元素位置
    		while(pointer < pointerBig) {	// threshold所在的最后一个元素不要参与比较,partition后会直接与大于区域第一个元素交换位置
    			if(arr[pointer] < threshold) {
    				swap(arr, pointer++, ++pointerSmall);	// 小于等于时与小于区域的下一个元素交换位置，指针后移
    			}
    			else if(arr[pointer] > threshold){
    				swap(arr, pointer, --pointerBig);// 当前位置比threshold大时pointer位置与pointerBig位置交换，pointerBig前移
    			}
    			else {
    				pointer++;
    			}
    		}
    		swap(arr, R, pointerBig);	// 数组最后一位即阈值与小于区域右边第一位交换位置
    		int[] ret = {pointerSmall, pointerBig};
    		return ret;	// 返回小于区域的右边界
    	}
    	
    	public static void swap(int[] arr, int i, int j	) {
    		int temp = arr[i];
    		arr[i] = arr[j];
    		arr[j] = temp;
    	}
    	
    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		quickSort(array, 0, array.length-1);
    		System.out.println(Arrays.toString(array));
    	}
    }

    方式3是在方式2的基础上进行修改，partition 部分直接不变，只在选择阈值时变成随机选择一位，将此位与最后元素交换位置，其余处理同方式2相同

快排时间复杂度

快排三种实现方式中，方式1和方式2都存在最差情况-逆序或顺序时时间复杂度为O(N^2)，而方式3随机选择阈值平均时间复杂度O(N*logN)，三种方式空间复杂度都是O(logN)

堆排序

堆结构

先了解堆结构，堆其实是一棵完全二叉树，他的每个节点都是所在子树的最大值
[完全二叉树] 定义：

  1. 除最后一层外，每层节点都被填满，即都具有左右子树
  2. 最后一层可以不满，但如果这一层具有子节点，则必须先填满左节点才能填右节点
    我们用数组存储二叉树来举例：
    非完全二叉树结构(不满足先左后右)：
    非完全二叉树举例
    1
    2
    3
    4
    5
    6
    7
    8
    数组: [0,1,2,3,4,5]
    非完全二叉树:
               0
              /\
             1  2
            /\   \
           3 4    5

    完全二叉树结构:
    完全二叉树举例
    1
    2
    3
    4
    5
    6
    7
    8
    数组: [0,1,2,3,4,5]    [0,1,2,3,4]     [0,1,2,3,4,5,6]
    完全二叉树: 
                0               0                0
               /\              /\               /\
              1  2            1  2             1  2
             /\ /            /\               /\  /\
            3 4 5           3  4             3 4  5 6

使用数组来作为堆结构时，如何表示父子节点对应关系？
如上图所示顺序对应数组的下标即可，同时有下面的下标计算方式表示父子节点对应关系：

  1. 当前节点下标为 i，则左子节点下标为 2*i+1，右子节点下标为 2*i+2
  2. 当前节点下标为 i，则父节点下标为 (i-1)/2
    tips: (i-1)/2 结果取整，因此通过左右节点下标计算父节点下标的方法一样
    要设计一个堆结构，就必须包含多个操作堆的方法

上浮

以大顶堆为例，每个节点都是所在子树的最大值，当要修改或插入元素时就可能涉及上浮操作，即当前节点比父节点大则交换两者位置，直到不满足比父节点大或没有父节点(到达堆顶)时停止

上浮
1
2
3
4
5
6
7
// 上浮
public static void heapInsert(int[] arr, int index, int heapSize) {
    while(arr[index] > arr[(index-1)/2]) {	// 当本节点大于父节点交换位置
        swap(arr, index, (index-1)/2);
        index = (index-1)/2;	// 更新位置
    }
}

下沉

以大顶堆为例，当要修改或插入元素时可能涉及下沉操作，即当前节点比孩子节点小时与孩子节点交换位置，直到不满足比孩子小或没有孩子节点为止

下沉
1
2
3
4
5
6
7
8
9
10
11
12
13
// 下沉
public static void heapify(int[] arr, int index, int heapSize) {
    while(2*index+1 < heapSize) {	// 有孩子时才能进行heapify
        // 记录大孩子位置有右孩子且比左孩子大时maxChild为右孩子，否则为左孩子
        int maxChild = ((2*index+2 < heapSize) && (arr[2*index+1] < arr[2*index+2])) ? 2*index+2 : 2*index+1;	
        maxChild = arr[index] > arr[maxChild] ? index : maxChild;	// 本节点与大孩子比出谁更大
        if(maxChild == index) {
            break;
        }
        swap(arr, index, maxChild);	// 当前节点比大孩子小则交换位置下沉
        index = maxChild;	// 更新位置
    }
}

堆排序原理和实现

在掌握堆结构后实现堆排序就非常简单，将数组中元素添加进堆中，逐一弹出最值并更新堆，弹出的值就能构成有序数组，例如下面的从小到大的堆排序：

堆排序示例
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
import java.util.Arrays;

public class Sort_HeapSort {
	
	// 堆排序
	public static void heapSort(int[] arr) {
		int heapSize = arr.length;	// 堆的大小
		// 倒序对每个元素heapify完成数组到大顶堆的转换，实际上叶子节点的heapify是没有操作的
		for(int i = heapSize-1; i >= 0;i--) {
			heapify(arr, i, arr.length);
		}
		swap(arr, --heapSize, 0);	// 保存堆顶元素即最大值，到数组末尾
		while(heapSize > 0) {
			heapify(arr, 0, heapSize);	// 更新堆，产生新的最大值在堆顶
			swap(arr, --heapSize, 0);	// 将堆末尾元素移到堆顶后，堆缩小
		}
		
	}
	
	// 上浮
	public static void heapInsert(int[] arr, int index, int heapSize) {
		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 heapSize) {
		while(2*index+1 < heapSize) {	// 有孩子时才能进行heapify
			// 记录大孩子位置有右孩子且比左孩子大时maxChild为右孩子，否则为左孩子
			int maxChild = ((2*index+2 < heapSize) && (arr[2*index+1] < arr[2*index+2])) ? 2*index+2 : 2*index+1;	
			maxChild = arr[index] > arr[maxChild] ? index : maxChild;	// 本节点与大孩子比出谁更大
			if(maxChild == index) {
				break;
			}
			swap(arr, index, maxChild);	// 当前节点比大孩子小则交换位置下沉
			index = maxChild;	// 更新位置
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void main(String[] args) {
		int[] array = {2,7,9,3,2,1,3,7,0,2};
		heapSort(array);
		System.out.println(Arrays.toString(array));
	}
}

PriorityQueue

PriorityQueue 是java语言中提供的一种容器，其实现方式就是堆，对外提供添加元素的 add() 方法和弹出堆顶元素的 poll() 方法等。
PriorityQueue 默认创建的是小顶堆，通过 add() 方法添加新元素后会更新堆，维护小顶堆的排列。
在功能需求简单的场景就可以利用编程语言自带的堆结构，当有特定的自带数据结构无法解决的需求时再自定义堆结构。
各个不同编程语言中基本都有这种自带的数据结构，如果没有使用的时候就必须自定义堆结构了。
例如在下面场景中就可以不自定义堆结构，而是直接使用现成的PriorityQueue解决问题：
题目： 已知未排序的数组中每个元素到正确位置的距离最大为k,对这样的数组采用一个合适的排序算法

自带堆结构的使用
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
import java.util.Arrays;
import java.util.PriorityQueue;

public class Heap_SortedDistanceK {
	// 已知未排序的数组中每个元素到正确位置的距离最大为k,对这样的数组采用一个合适的排序算法
	public static void heapSort(int[] arr, int k) {
		// 没有特殊需求可直接使用java中提供的优先队列结构，优先队列的底层实现就是堆
		PriorityQueue<Integer> heap = new PriorityQueue<Integer>();	// 默认为小顶堆
		int index = 0;
		for(; index < Math.min(arr.length, k); index++) {	// 将前k个数放入堆中
			heap.add(arr[index]);
		}
		int i = 0;
		for(; index<arr.length; index++, i++) {
			heap.add(arr[index]);	// 小顶堆大小维持在k+1保证一定能找到一个真实最小的元素
			arr[i] = heap.poll();	// 将选出的最小值放在滑动窗口最前端后，窗口向后滑动
		}
		while(!heap.isEmpty()) {
			arr[i++] = heap.poll();
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void main(String[] args) {
		int[] array = {2,7,9,3,2,1,3,7,0,2};
		heapSort(array, 8);
		System.out.println(Arrays.toString(array));
	}
}

其他排序

之前介绍的排序算法都是基于比较的排序算法，也存在不基于比较的排序算法，这类排序方法一般都需要根据数据状况定制排序算法，例如计数排序、基数排序

计数排序

  1. 排序原理：遍历数据，统计出现的频率保存在对应位的数组中
  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
    import java.util.Arrays;

    public class Sort_CountSort {
    	// 计数排序
    	public static void countSort(int[] arr) {
    		int maxNum = Integer.MIN_VALUE;
    		int minNum = Integer.MAX_VALUE;
    		// 找到数组中最大的和最小的值
    		for(int i = 0; i < arr.length; i++) {
    			maxNum = Math.max(maxNum, arr[i]);
    			minNum = Math.min(minNum, arr[i]);
    		}
    		if(maxNum == minNum) {	// 数组中数全部相等
    			return;
    		}
    		int[] helper = new int[maxNum-minNum+1];	// 辅助数组,用于统计词频
    		// 词频统计
    		for(int i = 0; i < arr.length; i++) {
    			helper[arr[i]-minNum]++;
    		}
    		// 输出
    		int index = 0;
    		for(int i = 0; i < helper.length; i++) {
    			for(int j = 0; j < helper[i]; j++) {
    				arr[index++] = i+minNum;
    			}
    		}
    	}

    	public static void main(String[] args) {
    		int[] array = {2,7,9,3,2,1,3,7,0,2};
    		countSort(array);
    		System.out.println(Arrays.toString(array));
    	}
    }

基数排序

  1. 排序原理：基数排序是利用基数数量的桶依次统计每个位的词频，对每个位单独排序的排序方式，步骤如下：

    1. 找到要排序的数中最大值
    2. 得到最大值的位数，作为入桶出通的次数
    3. 对所有数的个位统计出现的频率
    4. 将统计的结果数组变成累加数组
    5. 从右向左根据累加数组将原数组分配到辅助数组中
    6. 进行完步骤3后辅助数组中就是按个位排好序的数组，辅助数组替换原数组
    7. 依次对十位、百位等进行1~4步骤

  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
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    import java.util.Arrays;

    public class Sort_RadixSort {

    	public static void radixSort(int[] arr) {
    		if(arr==null || arr.length==1) {
    			return;
    		}
    		int radix = 10;	// 十进制基数就是10，8进制基数就是8	
    		int maxWidth = getWidth(arr, radix);	// 得到所有数中最大值的位数,即入桶出通的次数
    		int[] helper = new int[arr.length];	// 辅助数组长度与原数组相同,负责保存每轮入桶出桶后的新顺序结果
    		for(int i = 0; i < maxWidth; i++) {	// 进行maxWidth次入桶和maxWidth次出桶
    			int[] bucket = new int[radix];	// bucket桶的大小与基数相同,用来统计数字出现频率
    			// 遍历数组统计本位的词频，入桶
    			for(int j = 0; j < arr.length; j++) {	
    				bucket[getBitValue(arr[j], radix, i)]++;	// 例：count[2]=3 表示所有数中此位为2的有3个
    			}
    			// 将词频数组变成词频累计数组
    			for(int j = 1; j < arr.length; j++) {	
    				bucket[j] = bucket[j] + bucket[j-1];	// 例：count[2]=3 表示所有数中此位小于等于2的数有3个
    			}
    			// 出桶,从右向左依次进行
    			int currentBit = 0;
    			for(int j = arr.length-1; j >= 0; j--) {	
    				currentBit = getBitValue(arr[j], radix, i);	// 当前数的当前位
    				helper[bucket[currentBit]-1] = arr[j];	// count[currentBit]表示所有数中这个位比currentBit小的数有多少个
    				bucket[currentBit]--;	// 更新count[]
    			}
    			// 从左向右依次更新
    			for(int j = 0; j<helper.length; j++) {
    				arr[j] = helper[j];	// 将辅助数组中的数倒出来就是排好的顺序
    			}
    		}
    	}
    	
    	// 得到数组中最大值的位数
    	public static int getWidth(int[] arr, int radix) {
    		int maxNum = Integer.MIN_VALUE;
    		for(int i=0; i<arr.length; i++) {
    			maxNum = Math.max(maxNum, arr[i]);	// 得到数组最大值
    		}
    		// 计算最大值的位数
    		int j = 0;
    		while(maxNum!=0) {
    			j++;
    			maxNum = maxNum/radix;
    		}
    		return j;
    	}
    	
    	// 得到指定数某位的值
    	// digit为0,1,2...分别代表个位、十位、百位...
    	public static int getBitValue(int num, int radix, int digit) {
    		int value = 0;
    		while(digit-- >= 0) {
    			value = num % radix;
    			num = num / radix;
    		}
    		return value;
    	}
    	
    	public static void main(String[] args) {
    		int[] array = {2,17,9,311,2,21,324,73,0,2};
    		radixSort(array);
    		System.out.println(Arrays.toString(array));
    	}
    }

异或运算

异或运算，运算符号 ^ ，在交换元素位置时能发挥的作用
异或运算的定义：

  • 两个数异或，不同为1，相同为0
  • 异或运算可理解为无进位的相加
    异或运算的性质：
  • 0^N=N, N^N=0
  • 异或具备交换律和结合律

异或运算实现swap()

根据上面异或运算的性质就可以得到交换元素位置函数 swap() 可以用下面代码实现：

异或运算实现两元素交换位置
1
2
3
4
5
public static void swap(int[] arr, int i, int j){
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];   // 此时实现了 arr[j] = arr[i]
    arr[i] = arr[i] ^ arr[j];   // 此时实现了 arr[i] = arr[j]
}

异或实现的 swap() 看着逼格满满，但是要注意此种方式不能将两个内存指向相同的元素交换位置，否则会将原来的数据洗成 0，例如数组中不能将 arr[1] 和 arr[1] 交换，因此使用此方法的前提就是保证参数 i 和 j 不相等。这是一种很取巧的方法，因为有限制条件所以一般不建议这样做

异或运算找到奇数次数

这样一个题目用异或运算可以更快速得到解答

  1. 题目1：数组 arr[] 中一个数出现了奇数次，其他数都出现了偶数次，找到出现奇数次的数，要求时间复杂度 O(N) ，空间复杂度 O(1).
    异或运算找到出现奇数次的数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public class OrOperation {
    	public static void findOddTimesNum(int[] arr) {
    		int temp = 0;
    		for(int item : arr) {
    			temp ^= item;	// 将数组中所有元素异或
    		}
    		System.out.println(temp);
    	}
    	public static void main(String[] args) {
    		int[] array = {1,2,1,5,2,6,7,2,7,6,2,2,2};	// 一个数出现奇数次，其他数都各出现偶数次
    		findOddTimesNum(array);
    	}
    }
    分析：出现偶数次的数异或结果为 0，0^N = N，因此将数组中所有元素异或就能得到出现奇数次的那个数
  2. 题目2：数组 arr[] 中两个数各自出现了奇数次，其他数都出现了偶数次，找到所有出现奇数次的数，要求时间复杂度 O(N) ，空间复杂度 O(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
    public class OrOperation {
    	public static void findOddTimesTwoNums(int[] arr) {
    		// 将数组中所有元素异或，得到两个出现奇数次的数a、b的异或结果a^b
    		int temp = 0;
    		for(int item : arr) {
    			temp ^= item;
    		}
    		// a不等于b，否则就不是出现奇数次了，因此a^b结果必不为0
    		// a和b至少有一位是不同的
    		// 找到a^b结果中最右边为1的位，例如10010最右边的位的位置就是00010，使用`00010&N`就能提取出数N的那个位的值
    		// filter就是上述的位置提取器
    		int filter = temp & (~temp + 1);
    		// 将a^b的结果与那一位也为1的数异或，得到的结果aORb就是a或者b
    		int aORb = 0;
    		for(int item : arr) {
    			if((item & filter) == 0) {	// item同filter与运算后结果等于0说明筛选的位为0
    				aORb ^= item;
    			}
    		}
    		// 将a^b的结果temp与aORb的结果异或就得到了另一个出现奇数次的数
    		int anotherNum = temp ^ aORb;
    		System.out.println(aORb+" "+anotherNum);
    	}
    	public static void main(String[] args) {
    		int[] array2 = {1,2,1,5,2,6,2,7,6,2,7,7};	// 一个数出现奇数次，其他数都各出现偶数次
    		findOddTimesTwoNums(array2);
    	}
    }
    分析：要找出两个出现奇数次的数难点在于如何将 a 、 b 从 a^b 中分离出来，上述方法中利用了以下几点：
  3. a、b两数不相等，因此a^b不为0，必有一个位为 1
  4. a^b为 1的那个位上a、b的值不相等，因此arr中所有那个位为1的数异或的结果就是a或者b
  5. 将 a^b 的值与a或者b的值异或就能得到另一个数的值

排序算法的稳定性

同样值的个体不因为排序而改变原来的次序称此排序算法具有稳定性
具有稳定性的排序算法：冒泡、插入、归并、一切桶排序思想下的排序
不具有稳定性的排序算法：选择排序，快速排序，堆排序
具有稳定性的算法能保证在二次排序时在排序的内部保留一次排序的顺序，举个例子：
给班级学生按照年龄排序后再根据班级排序，如果采用的是具有稳定性的算法，则排序的结果中同一班级的学生会以年龄排序，达到了保留一次排序的效果

总结

排序算法 时间复杂度 额外空间复杂度 稳定性
选择排序 O(N^2) O(1) ×
冒泡排序 O(N^2) O(1) √
插入排序 O(N^2) O(1) √
归并排序 O(N*logN) O(N) √
快速(随机)排序 O(N*logN) O(logN) ×
堆排序 O(N*logN) O(1) ×

一般我们都采用快速(随机)排序算法，它的时间复杂度经过实际验证是归并排序、快速(随机)排序、堆排序中常数项最小的一种排序算法；
如果对空间复杂度要求比较严格就采用堆排序，空间复杂度只有O(1)；
如果对排序算法的稳定性有要求就采用归并排序，在保证时间复杂度为O(N*logN)的同时还具有稳定性；
可以说这三种排序算法各有优势和缺陷，实际使用中应根据场合选择。
目前还没有找到基于比较的排序算法时间复杂度小于O(N*logN)。
目前还没有找到时间复杂度O(N*logN)额外空间复杂度O(1)，又稳定的排序算法。

工程上的改进

综合排序

综合排序就是排序算法的拼装，充分利用各个排序算法的优势，在不同场景中将几种排序算法结合使用，例如：
进行快速排序时，在数据规模较大时采用快速排序，利用快速排序时间复杂度低的优势，而在小样本时采用插入排序的方式，利用数据规模小时插入排序花费时间更短的优势，从而达到总体的时间消耗较少，例如：在快速排序中加入判断，在大区间仍采用快速排序来调度，而当待排序区间被划分到尺寸小于给定的threshold时，在小区间排序上改用插入排序

稳定性

对不同的应用场景选择不同稳定性的算法，以Java中自带的Arrays.sort()为例，其底层实现是两种方式：

  • 当待排序数据是基础数据类型，那么稳定性就对这个数据排序没什么用，这时候Arrays.sort()方法就会采用没有稳定性而常数时间复杂度更低的快速排序算法；
  • 当待排序数据是非基础数据类型，则排序算法的稳定性可能会被用到，为保险起见Arrays.sort()方法就会采用具有稳定性而时间复杂度相比快排更高一点的归并排序；