认识复杂度与排序算法笔记

文章目录

• • 1、时间复杂度
  • 2、选择排序
  • 3、冒泡排序
  • 4、异或运算
  • 5、插入排序
  • 6、二分法
  • 7、剖析递归行为和递归行为时间复杂度的估算
  • 8、归并排序
  • 9、快速排序
  • 10、堆
  • 11、比较器的使用
  • 12、基数排序（不基于比较的排序）
  • 13、排序算法的稳定性及其汇总

1、时间复杂度

2、选择排序

每一次循环把最小值放到对应的位置上

pubic static void selectionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j < arrr.length; j++) {
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		swap(arr,i,minIndex);
	}
}

时间复杂度 O(N²) 空间复杂度O(1)

3、冒泡排序

两两对比，把大的往后移，每一趟循环下来把大的放在了后面

pubic static void bubbleSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int e = arr.length - 1; e > 0; e--) {
		for (int i = 0; i < e; i++) {
			if (arr[i] > arr[i+1]) {
				swap(arr,i,i+1);
			}
		}		
	}
}

时间复杂度 O(N²) 空间复杂度O(1)

4、异或运算

定义：相同为0，不同为1，还可以理解为无进位相加
位运算比算数运算快多了

如果要用异或交换两个数，那么这两个数在内存中的位置一定不能相同，无论这两个值相不相等，如果相等，就会把数变成0了。

例题1：一个数组中，只有一种数出现了奇数次，其他数出现了偶数次，找到出现奇数次的数，要求时间复杂度O（N），空间复杂度O（1）

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

例题2：有两种数出现了奇数次，其他出现了偶数次，怎样找到这两种数
思路：

public static void printOddTimesNum2(int[] arr) {
	int eor = 0;
	for (int curNum : arr) {
		eor ^= curNum;
	}
	// eor = a ^ b;
	// eor != 0
	// eor必然有一个位置上是1
	int rightOne = eor & (~eor + 1); // 提取出最后边的1
	int onlyOne = 0;
	for (int cur : arr) {
		if ((cur & rightOne) == 0) { // (cur & rightOne) == 1
			onlyOne ^= cur;
		}
	}
	System.out.println(onlyOne + " " + (eor ^ onlyOne));
}

5、插入排序

做到0 ~ 0有序，0 ~ 1有序，0 ~ 2有序，0 ~ 3有序 … 0 ~ N有序
插入排序与数据状况有关系

public static void insertionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	// 0 ~ 0 有序
	// 0 ~ 1 有序
	for (int i = 1; i < arr.length - 1; i++) {
		for (int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--) {
			swap(arr,j,j+1);
		}		
	}
}

时间复杂度 O(N²) 空间复杂度O(1)

6、二分法

例1：有序数组中，找某个数的存在

例2：在一个有序数组中，找>=某个数最左侧的位置

例3：局部最小值问题

7、剖析递归行为和递归行为时间复杂度的估算

8、归并排序

先让左侧排好序，再让右侧排好序，最后再让整体有序（新开辟一个空间对左右侧进行比较）

public static void mergeSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	process(arr,0,arr.length-1);
}
public static void process(int[] arr,int L,int R) {
	if (L == R) {
		return;
	}
	int mid = L + ((R - L) >> 1);
	process(arr,L,mid);
	process(arr,mid+1,R);
	merge(arr,L,mid,R);
}
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) {
		help[i++] = arr[p1++];
	}
	while (p2 <= R) {
		help[i++] = arr[p2++];
	}
	for (i = 0; i < help.length; i++) {
		arr[L + i] = help[i];
	}
}

根据maser公式：T（N） = 2 * O(N/2) + O(N)
时间复杂度O（N*㏒N）空间复杂度O（N）

1. 小和问题代码实现：
   相等时候一定要先拷贝右组的数据

public static int smallSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	return process(arr,0,arr.length-1);
}
// arr[L..R]既要排好序，也要求小和
public static int process(int[] arr,int L,int R) {
	if (L == R) {
		return 0;
	}
	int mid = L + ((R - L) >> 1);
	return process(arr,L,mid)
	 		+ process(arr,mid+1,R)
	 		+ merge(arr,L,mid,R);
}
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;
}

2. 逆序对问题
   力扣原题

public int reversePairs(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        return process(nums,0,nums.length-1);
    }

    public int process(int[] nums,int L,int R) {
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(nums,L,mid)
                + process(nums,mid + 1,R)
                + merge(nums,L,mid,R);
    }

    public int merge(int[] nums,int L,int M,int R) {
        int[] help = new int[R - L + 1];
        int p1 = L;
        int p2 = M + 1;
        int i = 0;
        int res = 0;
        while (p1 <= M && p2 <= R) {
            res += nums[p1] > nums[p2] ? (M - p1 + 1) : 0;
            help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
        }
        while (p1 <= M) {
            help[i++] = nums[p1++];
        }
        while(p2 <= R) {
            help[i++] = nums[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            nums[L + j] = help[j];
        }
        return res;
    }

9、快速排序

先看荷兰国旗问题

1. 给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O（1），时间复杂度O（N）
   

2. 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O（1），时间复杂度O（N）
   

快排1.0

快排2.0，2.0版本比1.0版本要稍快一点

但是不管是1.0还是2.0版本，时间复杂度都是O（N^2），原因是划分值打得很偏，可能只有左侧或者只有右侧部分，这时候时间复杂度就会退化

快排3.0版本，随机算一个数作为划分值，好情况和坏情况就是一个概率时间

我习惯的写法

public void quickSort(int []nums,int begin,int end) {
        if (begin < end) {
            int index = getIndex(nums,begin,end);
            quickSort(nums,begin,index-1);
            quickSort(nums,index+1,end);
        }
    }

private static int getIndex(int[] nums,int low,int high) {
	    int temp = nums[low];
	    while (low < high) {
	        while (low < high && nums[high] > temp) {
	            high--;
	        }
	        nums[low] = nums[high];
	        while (low < high && nums[low] <= temp) {
	            low++;
	        }
	        nums[high] = nums[low];
	    }
	    nums[low] = temp;
	    return low;
	}

时间复杂度O（N*logN），空间复杂度O（N）

10、堆

大根堆

调整大根堆

// 某个数现在处在index位置，往上继续移动
public static void heapInsert(int[] arr,int index) {
	while (arr[index] > arr[index - 1] / 2) {
		swap(arr,index,(index - 1) / 2);
		index = (index - 1) / 2;
	}
}

返回并删除最大值（根节点），把最后一个节点拷贝到头结点，然后从头结点开始，跟它的左右孩子的最大值进行比较

// 某个数现在处在index位置，往下继续移动
public static void heapify(int[] arr,int index,int heapSize) {
	int left = 2 * index +1;
	while (left < heapSize) {
		int largest = left + 1 < heapSize && arr[left] < arr[left + 1] 
						? left + 1 : left;
		largest = arr[index] > arr[largest] ? index : lardest;
		if (largest == index) {
			break;
		}
		swap(arr,largest,index);
		index = largest;
		left = 2 * index +1;;
	}
}

堆排序，先让数组整体形成一个大根堆，然后让堆的根节点与最后一个节点进行交换，heapSize–，这样就把最大值放在了数组的最后面，依次执行这个过程，当heapSize==0，最后数组有序。

时间复杂度 O（N*logN），空间复杂度O（1）

public static void heapSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length; i++) { // O（N）
		heapInsert(arr,i); // O（logN）
	}
	swap(arr,0,--heapSize);
	while (heapSize > 0) { // O（N）
		heapify(arr,0,heapSize); // O（logN）
		swap(arr,0,--heapSize); // O（1）
	}
}

例题：

public void sortedArrDistanceLessK(int[] arr,int k) {
	// 默认小根堆
	PriorityQueue heap = new PriorityQueue<>();
	int index = 0;
	for (; index <= Math.min(arr.length,k); index++) {
		heap.add(arr[index]);
	}
	int i = 0;
	for (; index < arr.length; i++, index++) {
		heap.add(arr[index]);
		arr[i] = heap.pop();
	}
	while (!heap.isEmpty()) {
		arr[i++] = heap.pop();
	}
}

11、比较器的使用

12、基数排序（不基于比较的排序）

先按个位数的数字进桶，然后从左往右依次倒出，然后再按十位数的数字进桶，依此类推，最后一定会排好序。

public static void radixSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	radixSort(arr,0,arr.length - 1,maxbits(arr));
}
public static int maxbits(int[] arr) {
	int max = Integer.MIN_VALUE;
	for (int i = 0; i < arr.length; i++) {
		max = Math.max(max,arr[i]);
	}
	int res = 0;
	while (max != 0) {
		res++;
		max /= 10;
	}
	return res;
}
public static void radixSort(int[] arr,int L,int R,int digit) {
	final int radix = 10;
	int i = 0, j = 0;
	// 有多少个数准备多少个辅助空间
	int[] bucket = new int[R - L + 1];
	for (int d = 1; d <= digit; d++) { // 有多少位就进出几次
		// 10个空间
		// count[0] 当前位(d位)是0的数字有多少个
		// count[1] 当前位(d位)是(0和1)的数字有多少个
		// count[2] 当前位(d位)是(0、1和2)的数字有多少个
		// count[1] 当前位(d位)是(0~i)的数字有多少个
		int[] count = new int[radix]; // count[0...9]
		for (i = L; i <= R; i++) {
			j = getDigit(arr[i],d);
			count[j]++;
		}
		for (i = 1; i < radix; i++) {
			count[i] = count[i] + count[i - 1];
		}
		for (i = R; i >= L; i--) {
			j = getDigit(arr[i],d);
			bucket[count[j] - 1] = arr[i];
			count[j]--;
		}
		for (i = L, j = 0; i <= R; i++,j++) {
			arr[i] = bucket[j];
		}
	}
}
public static int getDigit(int x,int d) {
	return ((x / ((int) Math.pow(10,d - 1))) % 10);
}

13、排序算法的稳定性及其汇总

（1）可以根据样本数量充分利用排序算法O（N*logN）和O（N^2）的优势。能用快排的时候就用快排，但是不稳定。

（2）稳定性的考虑
Arrays.sort( )在基础类型的时候使用快速排序，非基础类型使用归并排序，因为非基础类型它会考虑排序后的稳定性问题。