[数据结构与算法]笔记 左程云算法基础（6.21更新至P4）

01 认识复杂度和简单排序算法

?#时间复杂度

常数操作举例：

属于常数操作：int a = arr[i];数组中，只是算了一个偏移量；加减乘除；位运算...

不属于常数操作：int b = list.get(i);链表中，只能遍历去找

当两个算法时间复杂度相等时，只能实际去运行来确定哪个算法更优

#选择排序

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到全部待排序的数据元素排完。

过程：看N眼，N次比较，1次swap；看N-1眼，N-1次比较，1次swap.......

看：N+N-1+N-2+...? 比较：N+N-1+N-2+...? ?swap:N次

=aN^2+bN+c

不要低阶项，只要高阶项，不要常系数==》O(n^2)

只需要开辟几个变量的额外空间==》O(1)

public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {//i~N-1
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {//i~N-1上找最小值下标
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			swap(arr, i, minIndex);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

void swap(int arr[], int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

void selectionSort(int arr[],int len) {
	if (arr[0] == NULL || len < 2) {
		return;
	}
	for (int i = 0; i < len - 1; i++) {//确定范围为 i~N-1
		int minIndex = i;
		for (int j = i + 1; j < len; j++) {//i~N-1上找最小值下标
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		swap(arr, i, minIndex);
	}
}

#冒泡排序

重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

public static void bubbleSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int e = arr.length - 1; e > 0; e--) {//规定范围 0~e
			for (int i = 0; i < e; i++) {
				if (arr[i] > arr[i + 1]) {
					swap(arr, i, i + 1);
				}
			}
		}
	}

    //交换arr的i和j位置上的值
	public static void swap(int[] arr, int i, int j) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

void swap(int arr[], int i, int j) {
	arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}

void bubbleSort(int arr[],int len) {
	if (arr == NULL || len < 2) {
		return;
	}
	for (int e = len - 1; e > 0; e--) {
		for (int i = 0; i < e; i++) {
			if (arr[i] > arr[i + 1]) {
				swap(arr, i, i + 1);
			}
		}
	}
}

#异或运算 ^

相同为0，不同为1：0^0=0????????0^1=1????????1^0=1????????1^1=0

可以理解为无进位相加

• 0^N=0 ????????N^N=0
• 满足交换律和结合律

//交换a和b的值（不用额外变量）

a=a^b;
b=a^b;
a=a^b;

但是前提是：a和b的内存地址不同，地址相同时会被洗成0

题目-数组中找奇数次出现的数

1 在一个数组中，只有一个数出现了奇数次，其他数出现偶数次，怎么找出这个数？

int eor =0； 把eor从数组头异或到数组尾，结束时eor就是出现了奇数次的数（偶次彼此消掉了）

public static void printOddTimesNum1(int[] arr) {
		int eor = 0;
		for (int cur : arr) {
			eor ^= cur;
		}
		System.out.println(eor);
	}

void printOddTimesNum1(int arr[],int len) {
	int eor = 0;
	for (int i = 0; i < len;i++) {
		eor ^= arr[i];
	}
	cout<<"数组中次数为奇数的数为:"<<eor;
}

异或运算的顺序无所谓的原因：因为异或运算可以看成无进位相加，结果中某一位的值只和所有数的这一位1出现的次数有关，和顺序无关

2 在一个数组中，两种数出现了奇数次，其他数出现偶数次，怎么找出这个数？

int eor =0；设出现奇数次数为a和b，把eor从数组头异或到数组尾，结束时eor就是a^b

所以eor=a^b? ? ?(a！=b? ?——》eor!=0)

eor一定在某一位（至少一位）不等于0 ，假设第X位为1，说明a和b在第X位不一样

int eor'=0；把eor’从数组头异或到数组尾，只异或数组中那些X位不为0的数，结束时eor'就是a或者b

?X位0的数不影响结果，只异或数组中那些X位不为0的数时，other2中1的个数为偶数次全消除，只剩a或b中一个，eor'只能碰到a或者b中一个，得到的结果就是另外一个

eor^eor'是a或b的另外一个

public static void printOddTimesNum2(int[] arr) {
		int eor = 0;
		for (int i=0;i<arr.length;i++) {
			eor^= arr[i];
		}
//eor=a^b
//eor!=0
//eor必然有一个位置是1

		int rightOne = eor & (~eor + 1);//提取出最右边的1

        int eorhasone=0;//eor'
		for (int cur : arr) {
			if ((cur & rightOne) != 0) {
				eorhasone ^= cur;
			}
		}
		System.out.println(eorhasone + " " + (eor ^ eorhasone));
	}

//提取最右边的1?
int rightOne = eor & (~eor + 1);

eor:         010100
~eor:        101011
~eor+1:      101100
eor&~eor+1:  000100

void printOddTimesNum2(int arr[],int len) {
	int eor = 0;
	for (int i = 0; i < len; i++) {
		eor ^= arr[i];
	}
	//eor=a^b
	//eor!=0
	//eor必然有一个位置是1

	int rightOne = eor & (~eor + 1);//提取出最右边的1

	int eorhasone = 0;//eor'
	for (int i = 0; i < len; i++) {
		if ((arr[i] & rightOne) != 0) {
			eorhasone ^= arr[i];
		}
	}
	int eor2 = eor ^ eorhasone;
	cout << "数组中出现奇数次数为：" << eorhasone << "和" << eor2;
}

#插入排序

对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增 1 的有序表 。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

插入排序的时间复杂度和数据状况有关

选择排序和冒泡排序和数据状况无关，不影响流程的进行

估计算法时间复杂度时，一律按照算法可能遇到的最差情况估计

public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
//0-0已经有序
//将0-i做到有序
		for (int i = 1; i < arr.length; i++) { //0-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) {
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

void swap(int arr[], int i, int j) {
	arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}

void insertionSort(int arr[],int len) {
	if (arr == NULL || len < 2) {
		return;
	}
	//0-0已经有序
	//将0-i做到有序
	for (int i = 1; i < len; i++) { //范围
		for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
			swap(arr, j, j + 1);
		}
	}
}

#二分法

题目-局部最小问题

arr数组中，无序，任何两个相邻数一定不相等；找一个局部最小的位置，能否时间复杂度好于O(n)?（局部最小定义：位置为0的数<位置为1的数 或 N-2<N-1 或者? i-1<i<i+1）

二分不一定需要有序

优化一个流程，优化的方向：1.数据状况特殊 2.问题特殊

#对数器

	// 和系统排序方法做对比
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	//生成随机数组
	public static int[] generateRandomArray(int maxSize, int maxValue) {
    //Math.random()          [0,1)所有小数，等概率返回一个
    //Math.random()*N        [0,N)所有小数，等概率返回一个
    //(int)Math.random()*N   [0,N-1]所有整数，等概率返回一个
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];//长度随机
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());//每个值随机
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	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();
	}

	// for test
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);//生成随机数组
			int[] arr2 = copyArray(arr1);
			bubbleSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {//判断两数组结果是否一样
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Wrong!");

		int[] arr = generateRandomArray(maxSize, maxValue);
		printArray(arr);
		bubbleSort(arr);
		printArray(arr);
	}

02 认识O(NlogN)的排序

#递归行为

题目-递归找数组上最大值

    public static int getMax(int[] arr) {
		return process(arr, 0, arr.length - 1);
	}

	public static int process(int[] arr, int L, int R) {
		if (L == R) {//范围中只有一个数，直接返回
			return arr[L];
		}
		int mid = L + ((R - L) >> 1);//找中点
		int leftMax = process(arr, L, mid);//找左侧最大值
		int rightMax = process(arr, mid + 1, R);//找右侧最大值
		return Math.max(leftMax, rightMax);
	}

master公式

?#归并排序

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

	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);//两侧merge在一起
	}

	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) {//p2越界了（只会有一个while运行）
			help[i++] = arr[p1++];
		}
		while (p2 <= r) {//p1越界了（只会有一个while运行）
			help[i++] = arr[p2++];
		}
		for (i = 0; i < help.length; i++) {//依次拷贝回去
			arr[l + i] = help[i];
		}
	}

归并排序比O(N^2)的排序好在哪：

O(N^2)的排序每一轮的比较是独立的，一轮遍历中有大量的比较，但只解决一个数。

归并排序每一次的比较信息是往下传递的，变成了整体有序的部分继续去和其他部分merge，没有浪费比较行为。

题目-小和问题

暴力求解：对每个i的左边都遍历一遍，O(n^2)

深度改写mergesort的思路：

把问题变成——求右边有多少个数比i位置的数大，小和中就产生多少个i位置的数

此问题中merge时左右组数值相等时，一定要先拷贝右侧数组中的数并且不产生小和

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

	public static int mergeSort(int[] arr, int l, int r) {//既要排好序，还要求小和
		if (l == r) {
			return 0;
		}
		int mid = l + ((r - l) >> 1);
		return mergeSort(arr, l, mid) //左侧排序求小和的数量
				+ mergeSort(arr, mid + 1, r) //右侧排序求小和的数量
				+ merge(arr, l, mid, r);//两侧merge时求小和的数量
	}

	public static int 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;
		int res = 0;
		while (p1 <= m && p2 <= r) {
//左侧小于右侧时产生小和
			res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
//左侧小于右侧时拷贝左侧，大于等于时拷贝右侧
			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];
		}
		return res;
	}

题目-逆序对问题

相当于求右边有多少个数比i位置的数小

题目-荷兰国旗问题

#快速排序

	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 };
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}