八大排序
1. 选择排序
/***
* 选择排序
* @param arr 数组
*/
public 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 < arr.length; j++) {
minIndex = arr[j] > minIndex ? minIndex : arr[j];
}
//如果第二部分的最小值小于arr[i]的值就交换
//如果第二部分的最小值大于arr[i]的值，自己和自己交换
swap(arr,i,minIndex);
}
}
public static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = arr[i];
}2. 冒泡排序
/**
* 冒泡排序
* 第一种是正向控制次数
*
* @param arr
*/
public static void bubblingSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
swap(arr, j, j + 1);
}
}
}
/***
* 冒泡排序
* 第二中 反向控制次数
* @param arr
*/
public static void bubblingSort1(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);
}
}
}
}
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];
}//异或^满足：
//1. 0^N=N，N^N=0
//2. 满足交换律，结合律
//交换a和b的值
int a = a^b;//a = a^b;
int b = a^b;//b = a^b = a^b^b = a^0 = a;
int a = a^b;//a = a^b = a^b^a = a^a^b = 0^b = b;
异或例题：已知在一个数组中
(1) 只有一种数出现了奇数次，其他的都是偶数次，求这一种数
(2) 有两种数出现了奇数次，其他都是偶数次，求这两个种数
异或^满足：
0^N=N，N^N=0
满足交换律，结合律根据N^N=0，可以得出第一问
根据N^N=0，可以得出第二问最后的结果是e = a^b
/***
* 只有一种数出现了奇数次，其他的都是偶数次，求这一种数
* @param arr 数组
* @return 返回这个数
*/
public static int way(int[] arr) {
int e = 0;
for (int i : arr) {
e ^= i;
}
return e;
}
/***
* 有两种数出现了奇数次，其他都是偶数次，求这两个种数
* @param arr 数组
*/
public static void way1(int[] arr) {
int eor = 0;
for (int i : arr) {
eor ^= i;
}
//eor = a^b
//eor!=0
//eor的二进制某一位至少有一个1 ---> 要么是a的某一位，要么是b的某一位
// 所以下一行代码是抽取eor的二进制最右边的1
int rightOnly = eor & (~eor + 1);
int e1 = 0;
for (int i : arr) {
if ((i & e1) == 0) {
e1 ^= i;
}
}
int e2 = eor ^ e1;
System.out.println("e1--->" + e1 + "e2--->" + e2);
}3. 插入排序
/***
* 插入排序
* @param arr
*/
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//[0,0]
//[0,1]
//[0,2]
// ...
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}二分法的详解与扩展
在一个有序数组中，找某个数是否存在
在一个有序数组中，找>=某个数最左侧的位置
局部最小值问题：
给定一个无序数组，相邻的数并不相等，那么就会产生很多个局部最小的值，找到任意一个局部最小的值的位置返回（1）数组0位置：arr[0] < arr[1] --->arr[0]是局部最小值
（2）数组N-1位置：arr[N-1] < arr[N-2] --->arr[N-1]是局部最小值
（3）数组[1，N-2]范围：arr[i] < arr[i+1] && arr[i] < arr[i-1] ---> arr[i] 是局部最小值
图解：
（1）数组0位置：arr[0] < arr[1] --->arr[0]是局部最小值
（2）数组N-1位置：arr[N-1] < arr[N-2] --->arr[N-1]是局部最小值
（3）数组[1，N-2]范围：arr[i] < arr[i+1] && arr[i] < arr[i-1] ---> arr[i] 是局部最小值
二分法求解：
public static int way(int[] arr){
int N = arr.length;
if(arr==null||N == 0){
return -1;
}
//arr[0] < arr[1]，第一种情况
if(arr[0] < arr[1] || arr.length==1){
return 0;
}
//arr[N-1] < arr[N-2]，第二种情况
if(arr[N-1] < arr[N-2]){
return arr[N-1];
}
//i = (1,N-2)，第三种情况
int left = 1;
int right = N-2;
while(left <= right){
int mid = left + ((right-left) >> 1);
if(arr[mid] > arr[mid-1]){
right = mid-1;
}else if(arr[mid] > arr[mid+1]){
left = mid + 1;
}else{
//| | | |
//| | | | |
//l mid-1 mid mid+1 r
return mid;
}
}
return -1;
}剖析递归行为时间复杂度的估算
- master公式的使用：T(N) = a*T(N/b)+ O(N ^d)
- 使用条件：子问题规模都相等
a：子问题等量的情况下，被调用的次数
O(N^d) ：除去调用子问题之外，剩下过程的时间复杂度
- T(N/b)：子问题都是T(N/b)的子问题
> d ->复杂度为0(N^
例如：用递归方法找一个数组中的最大值
public static int way(int[] arr){
return process(arr,0,arr.length-1);
}
public static int process(int[]arr,int left, int right){
if(left == right){
return arr[left];
}
int mid = left + ((right-left)>>1);
int leftMax = process(arr,left,mid-1);
int rightMax = process(arr,mid+1,right);
return Math.max(leftMax,rightMax);
}a = 2，b = 2，d = 0
T(N) = 2*T(N/2) + O(1)
4. 归并排序
public static void way(int[] arr) {
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr, int left, int right) {
if (left == right) {
return;
}
int mid = left + ((right - left) >> 1);
//拆分
//左边---中间
process(arr, left, mid);
//中间---右边
process(arr, mid + 1, right);
//排序
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int i = 0;
int p1 = left;
int p2 = mid + 1;
//左右区间比较得到小的值放入help数值中
while (p1 <= mid && p2 <= right) {
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
//左区间可能有剩余
while (p1 <= mid) {
help[i++] = arr[p1++];
}
//右区间可能有剩余
while (p2 <= right) {
help[i++] = arr[p2++];
}
//返回给arr数组
for (i = 0; i < help.length; i++) {
arr[i + left] = help[i];
}
}归并排序符合master公式：，其中a = 2，b = 2，d = 2
归并排序的时间复杂度：，空间复杂度：
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
例子：[1,3,4,2,5]
- 1左边比1小的数，没有
- 3左边比3小的数，1
- 4左边比4小的数，1、3
- 2左边比2小的数，1
- 5左边比5小的数，1、3、4、2
所以小和为1+1+3+1+1+3+4+2=16
换一种解法：
- 1右边比1大的数：3，4，2，5
- 3右边比3大的数：4，5
- 4右边比4大的数：5
- 2右边比2大的数：5
- 5右边比5大的数：无
所以小和为：1*4+3*2+4*1+2*1 = 16
/**
* 小和数
*/
public static int way1(int[] arr) {
return process1(arr, 0, arr.length - 1);
}
public static int process1(int[] arr, int left, int right) {
if (left == right) {
return 0;
}
int mid = left + ((right - left) >> 1);
//拆分
//左边---中间
return process1(arr, left, mid) + process1(arr, mid + 1, right) + merge1(arr, left, mid, right);
}
public static int merge1(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int res = 0;
int i = 0;
int p1 = left;
int p2 = mid + 1;
//左右区间比较得到小的值放入help数值中
while (p1 <= mid && p2 <= right) {
res += arr[p1] < arr[p2] ? (right - p2 + 1) * arr[p1] : 0;
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
//左区间可能有剩余
while (p1 <= mid) {
help[i++] = arr[p1++];
}
//右区间可能有剩余
while (p2 <= right) {
help[i++] = arr[p2++];
}
//返回给arr数组
for (i = 0; i < help.length; i++) {
arr[i + left] = help[i];
}
return res;
}
逆序对问题
在一个数组中，左边的数如果比右边的数大，则折两个数构成一个逆序对，请打印所有逆序对
eg：[1,3,4,2,5]
- 1右边比1小的：无
- 3右边比3小的：2
- 4右边比4小的：2
- 5右边比5小的：无
所有逆序对：1+1=2
