【华为面试手撕代码】

先说思路，然后写代码

常用的排序算法

1.冒泡排序

1.设置循环次数。
2.设置开始比较的位数，和结束的位数。
3.两两比较，将最小的放到前面去。
重复2、3步，直到循环次数完毕。

int temp;//定义一个临时变量
for(int i=0;i<arr.length-1;i++){
   //冒泡趟数
    for(int j=0;j<arr.length-i-1;j++){
   //从第一个比到n-1-i
        if(arr[j+1]<arr[j]){
   //若前面比后面大，则交换
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.选择排序

1.首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
3.重复第二步，直到所有元素均排序完毕。

/* 选择排序 */
void SelectionSort(int arr[], int length)
{
   
    int index, temp;
	for (int i = 0; i < length; i++)
	{
   
        index = i;//未排序序列中最小元素
		for (int j = i + 1; j < length; j++)
		{
   
			if (arr[j] < arr[index])
				index = j;
		}
		if (index != i)
		{
   
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.插入排序

将数组R划分成两个子区间R[1．．i-1]（已排好序的有序区）和R[i．．n]（当前未排序的部分，可称无序区）。插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1．．i-1]中适当的位置上，使R[1．．i]变为新的有序区

public voidInsertSort () {
   
	int i,j,temp;
	for(i=1;i<array.length;i++) {
   // R[i．．n]（当前未排序的部分，可称无序区）
		temp=array[i];
		for(j=i-1;j>=0;j--) {
   // R[1．．i-1]（已排好序的有序区）
			if(temp>array[j]) {
   
				break;
			}else {
   
				array[j+1]=array[j];//往后挪，腾位置
			}
		}
		array[j+1]=temp;//插入数据
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.快排排序

先从右往左找到一个小于基准数的数，再从左往右找到一个大于基准数的数，交换他们.重复，当ij相遇时把此时这个数和基准数交换，再分别处理左右两边的数字.
== 先从右往左找,再从左往右找==

public static void quickSort(int[] arr,int low,int high){
   
    int i,j,temp,t;
    if(low>high) return;
    i=low;
    j=high;
    temp = arr[low];//temp就是基准位
    while (i<j) {
   
        while (temp<=arr[j]&&i<j) {
   
            j--;
        }//先看右边，依次往左递减   
        while (temp>=arr[i]&&i<j) {
   
            i++;
        }//再看左边，依次往右递增
        if (i<j) {
   //如果满足条件则交换
            t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
        }
    }
    arr[low] = arr[i];//最后将基准为与i和j相等位置的数字交换
    arr[i] = temp;
    quickSort(arr, low, j-1);//递归调用左半数组
    quickSort(arr, j+1, high);//递归调用右半数组
}    
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

5.归并排序

假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2(或者是1)的有序子序列，再两两归并。如此重复，直到得到一个长度为n的有序序列为止。

private static void sort(int[] array, int left, int right) {
   
	if (left == right) {
   
		return;
	}
	int mid = left + ((right - left)/2);
	sort(array, left, mid); // 对左侧子序列进行递归排序
	sort(array, mid + 1, right); // 对右侧子序列进行递归排序
	merge(array, left, mid, right); // 合并
}

private static void merge(int[] array, int left, int mid, int right) {
   
	int[] temp = new int[right - left + 1];
	int i = 0;
	int p1 = left;
	int p2 = mid + 1;
	// 比较左右两部分的元素，哪个小，把那个元素填入temp中
	while (p1 <= mid && p2 <= right) {
   
		temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
	}
	// 上面的循环退出后，把剩余元素依次填入temp（以下两个while只有一个会执行）
	while (p1 <= mid) {
   
		temp[i++] = array[p1++];
	}
	while (p2 <= right) {
   
		temp[i++] = array[p2++];
	}
	// 把最终的排序的结果复制给原数组
	for (i = 0; i < temp.length; i++) {
   
		array[left + i] = temp[i];
	}
}
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

6.堆排序

可以将堆看做是一个完全二叉树。并且，每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。

堆排序(Heap Sort)是利用堆进行排序的方法。其基本思想为：将待排序列构造成一个大顶堆(或小顶堆)，整个序列的最大值(或最小值)就是堆顶的根结点，将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值(或最小值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值(或次小值)，如此反复执行，最终得到一个有序序列。

图解

a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

作者：尼小摩
链接：https://www.jianshu.com/p/a161b991fa82
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

public class HeapSort {
   
    public static void main(String []args){
   
        int []arr = {
   7,6,7,11,5,12,3,0,1};
        System.out.println("排序前："+Arrays.toString(arr));
        sort(arr);
        System.out.println("排序前："+Arrays.toString(arr));
    }
    public static void sort(int []arr){
   
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
   
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
   
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
    }
    //调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
    public static void adjustHeap(int []arr,int i,int length){
   
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){
   //从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){
   //如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){
   //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
   
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
    public static void swap(int []arr,int a ,int b){
   
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
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

Java 的sort基于什么实现

（快排），全都是快排吗（不知道）

排序算法原理，何为稳定不稳定，快排是否稳定

查找

二分查找

时间复杂度（logn）

复盘笔试题

笔试题的思路（说说上次笔试第二题为啥没全对？？（答：估摸着边界没处理好）

3.寻找重复的子树

题目：
给定一棵二叉树 root，返回所有重复的子树。
对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
如果两棵树具有相同的结构和相同的结点值，则它们是重复的

思路
序列化二叉树。

   1
  / \
 2   3
    / \
   4   5
1
2
3
4
5

序列化结果为 1,2,#,#,3,4,#,#,5,#,#。每棵不同子树的序列化结果都是唯一的。

算法
使用深度优先搜索，其中递归函数返回当前子树的序列化结果。把每个节点开始的子树序列化结果保存在 mapmap 中，然后判断是否存在重复的子树。

class Solution {
   
    Map<String, Integer>
1
2