目录

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

11.1 排序算法的稳定性

11.2 常见的坑

11.3 工程上对排序的改进

12、链表

12.1 HashSet 和 HashMap

12.2 有序表

12.3 面试时链表解题的方法论

*12.4 关于链表的练习题

*

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

11.1 排序算法的稳定性

同样值的个体之间，如果不因为排序而改变相对次序，就是这个排序是有稳定性的；否则就没有。

误区：认为稳定性是随数据的差异会影响算法的时间空间复杂度【容易产生的认知】

不具备稳定性的排序： 选择排序、快速排序、堆排序

具备稳定性的排序： 冒泡排序、插入排序、归并排序、一切桶排序思想下的排序

总结：只要有跨度的交换，就会丧失稳定性。相邻交换的则不会。

不具有稳定性的排序算法：

选择排序

快速排序

堆排序更是无视稳定性，他只认识孩子和父亲，进行大跨度无序交换

具有稳定性的排序算法：

冒泡排序

插入排序

归并排序关键在于merge的时候，要先拷贝左边的数，而用归并解决小和问题的时候，要先拷贝右边的数，则丧失稳定性

目前没有找到时间复杂度0（N*logN），额外空间复杂度0（1），又稳定的排序。

11.2 常见的坑

1. 归并排序的额外空间复杂度可以变成0（1），但是非常难，不需要掌握，有兴趣可以搜“归并排序内部缓存法”

2. “原地归并排序”的帖子都是垃圾，会让归并排序的时间复杂度变成O（N~2）

3. 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01stable sort"

4. 所有的改进都不重要，因为目前没有找到时间复杂度0（N*logN），额外空间复杂度0（1），又稳定的排序。

5. 有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。

11.3 工程上对排序的改进

1）充分利用O（N*IogN）和0（N^2）排序各自的优势 2）稳定性的考虑

在快速排序中，当样本量小于60的时候，插入排序时间复杂度相当，当常数操作复杂度极低，因此可以将2种混合起来。

public class Test {    public static void quickSort(int[] arr, int 1, int r) { if(1 ==r){     return; } if (1 >r - 60) {//插入排序     在arr[1..r]插入排序     O（Nへ2）小样本量的时候，跑的快     return; } swap(arr, 1 + (int) (Math.random() * (r - 1 + 1)), r);//快速排序 int[] p = partition(arr, 1, r); quickSort(arr, 1, p[0] - 1); //‹ 区 quickSort(arr, p[1] + 1, r); // > 区    }}

大样本调度快选择 O（N*IogN)；小样本选择插入，跑得快 0（N^2)

12、链表

12.1 HashSet 和 HashMap

哈希表的简单介绍

1. 哈希表在使用层面上可以理解为一种集合结构

2. 如果只有key,没有伴随数据value,可以使用HashSet结构（C++中叫UnOrderedSet）

3. 如果既有key,又有伴随数据value,可以使用HashMap结构（C++中叫UnOrderedMap）

4. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事

5. 使用哈希表增（put）、删（remove）、改（put）和查（get）的操作，可以认为时间复杂度为0（1），但是常数时间比较大

6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小

7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小

12.2 有序表

有序表的简单介绍

1. 有序表在使用层面上可以理解为一种集合结构

2. 如果只有key,没有伴随数据value,可以使用TreeSet结构（C++中叫OrderedSet）

3. 如果既有key,又有伴随数据value,可以使用TreeMap结构（C++中叫OrderedMap)

4. 有无伴随数据，是TreeSet和TreeMap唯一的区别，底层的实际结构是一回事

5. 有序表和哈希表的区别是，有序表把key按照顺序组织起来，而哈希表完全不组织

6. 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现 不同

7. 放入有序表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小

8. 放入有序表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占 用是这个东西内存地址的大小

9. 不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复 杂度

12.3 面试时链表解题的方法论

1. 对于笔试，不用太在乎空间复杂度，一切为时间复杂度

2. 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法

重要技巧：

1. 额外数据结构记录（哈希表等）

2. 快慢指针

*12.4 关于链表的练习题

12.4.1 判断一个链表是否为回文结构

【题目】给定一个单链表的头节点head,请判断该链表是否为回文结构。 【例子】1->2->1,返回true;1->2->2->1,返回true;15->6->15,返回true；1->2->3,返回false。 【例子】如果链表长度为N，时间复杂度达到O（N），额外空间复杂度达到O（1）。

把链表扔到栈，然后弹出一个比对一个

优化算法1：只将链表的右半部分扔到栈中，然后对比（节省了一般的空间复杂度）

优化算法2：使用快慢指针，快指针结束的时候，慢指针走到中点。这个coding要练熟。

如果要使用低空间复杂度，使用改链表的方式，最后再恢复：

// need O(1) extra space    public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) {     return true; } Node n1 = head;//慢指针 Node n2 = head;//快指针 //快慢指针找末尾和中点 while (n2.next != null && n2.next.next != null) { // find mid node     n1 = n1.next; // n1 -> mid     n2 = n2.next.next; // n2 -> end } n2 = n1.next; // n2 -> right part first node n1.next = null; // mid.next -> null Node n3 = null;//用于记录n2原本的下一个node //右半部分逆序 while (n2 != null) { // right part convert     n3 = n2.next; // n3 -> save next node，保留未改变的链表     n2.next = n1; // next of right node convert，改变链表指向     //n1，n2两个指针完成改变指向操作后，同时右移，准备下一个元素的链表指向逆序     n1 = n2; // n1 move     n2 = n3; // n2 move } n3 = n1; // n3 -> save last node n2 = head;// n2 -> left first node boolean res = true; while (n1 != null && n2 != null) { // check palindrome     //每走一步，都验证     if (n1.value != n2.value) {  res = false;  break;     }     //n1，n2从中间开始走     n1 = n1.next; // left to mid     n2 = n2.next; // right to mid } n1 = n3.next; n3.next = null; //最后将逆序的链表变回来 while (n1 != null) { // recover list     n2 = n1.next;     n1.next = n3;     n3 = n1;     n1 = n2; } return res;    }​

12.4.2 将单向链表按某值划分成左边小、中间相等、右边大的形式

笔试：创建node数组，把链表的node烤进去，再做partition，快速排序，即归并的3.0版本。

面试：使用6个变量指针，小于区域的头和尾，等于区域的头和尾，大于区域的头和尾，最后将3个区域连起来的时候，要注意是否有区域为空。

  public static Node listPartition2(Node head, int pivot) { Node sH = null; // small head Node sT = null; // small tail Node eH = null; // equal head Node eT = null; // equal tail Node bH = null; // big head Node bT = null; // big tail Node next = null; // save next node // every node distributed to three lists while (head != null) {     next = head.next;     head.next = null;     if (head.value < pivot) {  if (sH == null) {      sH = head;      sT = head;  } else {      sT.next = head;      sT = head;  }     } else if (head.value == pivot) {  if (eH == null) {      eH = head;      eT = head;  } else {      eT.next = head;      eT = head;  }     } else {  if (bH == null) {      bH = head;      bT = head;  } else {      bT.next = head;      bT = head;  }     }     head = next; } // small and equal reconnect if (sT != null) {     sT.next = eH;     eT = eT == null ? sT : eT; } // all reconnect if (eT != null) {     eT.next = bH; } return sH != null ? sH : eH != null ? eH : bH;    }

  ​

12.4.3 复制含有随机指针节点的链表

做法1：第一次遍历旧链表，使用哈希map，key为旧链表，value为新链表，新链表只是单纯地串起来并拷贝int value值，rand没有设置；第二次遍历旧链表，调用key-value，设置rand node。

做法2：第一次遍历旧链表，不用哈希map，在旧map中，插入克隆node，拷贝int value值；第二次遍历链表，一对一对处理，设置rand node；第三次遍历，把旧节点删除。省去了hashmap的空间。