boolean flag = false;

int temp = numbers[j];

flag = true;

}

if (!flag) {

break;

package com.chen.algorithm.sort.study;

public class InsertSort2 {

private void sort(int[] array) {

int leftIndex;

for (int i = 1; i < array.length - 1; i++) {

int temp = array[i];

leftIndex = i - 1;

while (leftIndex >= 0 && temp < array[leftIndex]) {

array[leftIndex + 1] = array[leftIndex];

leftIndex--;

}

array[leftIndex + 1] = temp;

}

}

}

- 单链表反转

- 链表中环的检测

- 两个有序的链表合并

- 删除链表倒数第 n 个结点

- 求链表的中间结点

leetcode上关于栈的题目大家可以先做20,155,232,844,224,682,496.

总结：

一、几种经典排序算法及其时间复杂度级别

冒泡、插入、选择 O(n^2) 基于比较

快排、归并 O(nlogn) 基于比较

计数、基数、桶 O(n) 不基于比较

二、如何分析一个排序算法？

1.学习排序算法的思路？明确原理、掌握实现以及分析性能。

2.如何分析排序算法性能？从执行效率、内存消耗以及稳定性3个方面分析排序算法的性能。

3.执行效率：从以下3个方面来衡量

1）最好情况、最坏情况、平均情况时间复杂度

2）时间复杂度的系数、常数、低阶：排序的数据量比较小时考虑

3）比较次数和交换（或移动）次数

4.内存消耗：通过空间复杂度来衡量。针对排序算法的空间复杂度，引入原地排序的概念，原地排序算法就是指空间复杂度为O(1)的排序算法。

5.稳定性：如果待排序的序列中存在值等的元素，经过排序之后，相等元素之间原有的先后顺序不变，就说明这个排序算法时稳定的。

三、冒泡排序

1.排序原理

1）冒泡排序只会操作相邻的两个数据。

2）对相邻两个数据进行比较，看是否满足大小关系要求，若不满足让它俩互换。

3）一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。

4）优化：若某次冒泡不存在数据交换，则说明已经达到完全有序，所以终止冒泡。

2.代码实现（见下一条留言）

3.性能分析

1）执行效率：最小时间复杂度、最大时间复杂度、平均时间复杂度

最小时间复杂度：数据完全有序时，只需进行一次冒泡操作即可，时间复杂度是O(n)。

最大时间复杂度：数据倒序排序时，需要n次冒泡操作，时间复杂度是O(n^2)。

平均时间复杂度：通过有序度和逆序度来分析。

什么是有序度？

有序度是数组中具有有序关系的元素对的个数，比如[2,4,3,1,5,6]这组数据的有序度就是11，分别是[2,4][2,3][2,5][2,6][4,5][4,6][3,5][3,6][1,5][1,6][5,6]。同理，对于一个倒序数组，比如[6,5,4,3,2,1]，有序度是0；对于一个完全有序的数组，比如[1,2,3,4,5,6]，有序度为n*(n-1)/2，也就是15，完全有序的情况称为满有序度。

什么是逆序度？逆序度的定义正好和有序度相反。核心公式：逆序度=满有序度-有序度。

排序过程，就是有序度增加，逆序度减少的过程，最后达到满有序度，就说明排序完成了。

冒泡排序包含两个操作原子，即比较和交换，每交换一次，有序度加1。不管算法如何改进，交换的次数总是确定的，即逆序度。

对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏的情况初始有序度为0，所以要进行n*(n-1)/2交换。最好情况下，初始状态有序度是n*(n-1)/2，就不需要进行交互。我们可以取个中间值n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。

换句话说，平均情况下，需要n*(n-1)/4次交换操作，比较操作可定比交换操作多，而复杂度的上限是O(n^2)，所以平均情况时间复杂度就是O(n^2)。

以上的分析并不严格，但很实用，这就够了。

2）空间复杂度：每次交换仅需1个临时变量，故空间复杂度为O(1)，是原地排序算法。

3）算法稳定性：如果两个值相等，就不会交换位置，故是稳定排序算法。

四、插入排序

1.算法原理

首先，我们将数组中的数据分为2个区间，即已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间中的元素一直有序。重复这个过程，直到未排序中元素为空，算法结束。

2.代码实现（见下一条留言）

3.性能分析

1）时间复杂度：最好、最坏、平均情况

如果要排序的数组已经是有序的，我们并不需要搬移任何数据。只需要遍历一遍数组即可，所以时间复杂度是O(n)。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，因此时间复杂度是O(n^2)。而在一个数组中插入一个元素的平均时间复杂都是O(n)，插入排序需要n次插入，所以平均时间复杂度是O(n^2)。

2）空间复杂度：从上面的代码可以看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，是原地排序算法。

3）算法稳定性：在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现的元素的后面，这样就保持原有的顺序不变，所以是稳定的。

文章结构：

数组看起来简单基础，但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号，而不是从1开始的问题，进入主题。

1. 数组如何实现随机访问

1） 数组是一种线性数据结构，用连续的存储空间存储相同类型数据

I） 线性表：数组、链表、队列、栈 非线性表：树 图

II） 连续的内存空间、相同的数据，所以数组可以随机访问，但对数组进行删除插入，为了保证数组的连续性，就要做大量的数据搬移工作

a) 数组如何实现下标随机访问。

引入数组再内存种的分配图，得出寻址公式

b) 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组，用二分查找，时间复杂度也是O（logn）。

正确表述：数组支持随机访问，根据下标随机访问的时间复杂度为O（1）

2. 低效的插入和删除

1） 插入：从最好O(1) 最坏O(n) 平均O(n)

2） 插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。作者举例说明

3） 删除：从最好O(1) 最坏O(n) 平均O(n)

4） 多次删除集中在一起，提高删除效率

记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

3. 警惕数组的访问越界问题

用C语言循环越界访问的例子说明访问越界的bug。此例在《C陷阱与缺陷》出现过，很惭愧，看过但是现在也只有一丢丢印象。翻了下书，替作者加上一句话：如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存，那么内存中的i将会被置为0，则为死循环永远出不去。

4. 容器能否完全替代数组

相比于数字，java中的ArrayList封装了数组的很多操作，并支持动态扩容。一旦超过村塾容量，扩容时比较耗内存，因为涉及到内存申请和数据搬移。

数组适合的场景：

1） Java ArrayList 的使用涉及装箱拆箱，有一定的性能损耗，如果特别管柱性能，可以考虑数组

2） 若数据大小事先已知，并且涉及的数据操作非常简单，可以使用数组

3） 表示多维数组时，数组往往更加直观。

4） 业务开发容器即可，底层开发，如网络框架，性能优化。选择数组。

5. 解答开篇问题

1） 从偏移角度理解a[0] 0为偏移量，如果从1计数，会多出K-1。增加cpu负担。为什么循环要写成for(int i = 0;i<3;i++) 而不是for(int i = 0 ;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据，而后者 2-0+1个数据，多出1个加法运算，很恼火。

2） 也有一定的历史原因

如何优雅的写出链表代码？6大学习技巧

一、理解指针或引用的含义

1.含义：将某个变量（对象）赋值给指针（引用），实际上就是就是将这个变量（对象）的地址赋值给指针（引用）。

2.示例：

p—>next = q; 表示p节点的后继指针存储了q节点的内存地址。

p—>next = p—>next—>next; 表示p节点的后继指针存储了p节点的下下个节点的内存地址。

二、警惕指针丢失和内存泄漏（单链表）

1.插入节点

在节点a和节点b之间插入节点x，b是a的下一节点，，p指针指向节点a，则造成指针丢失和内存泄漏的代码：p—>next = x;x—>next = p—>next; 显然这会导致x节点的后继指针指向自身。

正确的写法是2句代码交换顺序，即：x—>next = p—>next; p—>next = x;

2.删除节点

在节点a和节点b之间删除节点b，b是a的下一节点，p指针指向节点a：p—>next = p—>next—>next;

三、利用“哨兵”简化实现难度

1.什么是“哨兵”？

链表中的“哨兵”节点是解决边界问题的，不参与业务逻辑。如果我们引入“哨兵”节点，则不管链表是否为空，head指针都会指向这个“哨兵”节点。我们把这种有“哨兵”节点的链表称为带头链表，相反，没有“哨兵”节点的链表就称为不带头链表。

2.未引入“哨兵”的情况

如果在p节点后插入一个节点，只需2行代码即可搞定：

new_node—>next = p—>next;

p—>next = new_node;

但，若向空链表中插入一个节点，则代码如下：

if(head == null){

head = new_node;

}

如果要删除节点p的后继节点，只需1行代码即可搞定：

p—>next = p—>next—>next;

但，若是删除链表的最有一个节点（链表中只剩下这个节点），则代码如下：

if(head—>next == null){

head = null;

}

从上面的情况可以看出，针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理。这样代码就会显得很繁琐，所以引入“哨兵”节点来解决这个问题。

3.引入“哨兵”的情况

“哨兵”节点不存储数据，无论链表是否为空，head指针都会指向它，作为链表的头结点始终存在。这样，插入第一个节点和插入其他节点，删除最后一个节点和删除其他节点都可以统一为相同的代码实现逻辑了。

4.“哨兵”还有哪些应用场景？

这个知识有限，暂时想不出来呀！但总结起来，哨兵最大的作用就是简化边界条件的处理。

四、重点留意边界条件处理

经常用来检查链表是否正确的边界4个边界条件：

1.如果链表为空时，代码是否能正常工作？

2.如果链表只包含一个节点时，代码是否能正常工作？

3.如果链表只包含两个节点时，代码是否能正常工作？

4.代码逻辑在处理头尾节点时是否能正常工作？

五、举例画图，辅助思考

核心思想：释放脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。

六、多写多练，没有捷径

5个常见的链表操作：

1.单链表反转

2.链表中环的检测

3.两个有序链表合并

4.删除链表倒数第n个节点

5.求链表的中间节点

一、什么是栈？

1.后进者先出，先进者后出，这就是典型的“栈”结构。

2.从栈的操作特性来看，是一种“操作受限”的线性表，只允许在端插入和删除数据。

二、为什么需要栈？

1.栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现。

2.但，任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。

3.所以，当某个数据集合只涉及在某端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构。

三、如何实现栈？

1.栈的API

public class Stack<Item> {

//压栈

public void push(Item item){}

//弹栈

public Item pop(){}

//是否为空

public boolean isEmpty(){}

//栈中数据的数量

public int size(){}

//返回栈中最近添加的元素而不删除它

public Item peek(){}

}

2.数组实现（自动扩容）

时间复杂度分析：根据均摊复杂度的定义，可以得数组实现（自动扩容）符合大多数情况是O(1)级别复杂度，个别情况是O(n)级别复杂度，比如自动扩容时，会进行完整数据的拷贝。

空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

实现代码：（见另一条留言）

3.链表实现

时间复杂度分析：压栈和弹栈的时间复杂度均为O(1)级别，因为只需更改单个节点的索引即可。

空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量存储空间，所以O(1)级别。我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。

实现代码：（见另一条留言）

四、栈的应用

1.栈在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量。每进入一个函数，就会将其中的临时变量作为栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

2.栈在表达式求值中的应用（比如：34+13*9+44-12/3）

利用两个栈，其中一个用来保存操作数，另一个用来保存运算符。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较，若比运算符栈顶元素优先级高，就将当前运算符压入栈，若比运算符栈顶元素的优先级低或者相同，从运算符栈中取出栈顶运算符，从操作数栈顶取出2个操作数，然后进行计算，把计算完的结果压入操作数栈，继续比较。

3.栈在括号匹配中的应用（比如：{}{[()]()}）

用栈保存为匹配的左括号，从左到右一次扫描字符串，当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号，如果能匹配上，则继续扫描剩下的字符串。如果扫描过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明未匹配的左括号为非法格式。

4.如何实现浏览器的前进后退功能？

我们使用两个栈X和Y，我们把首次浏览的页面依次压如栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据一次放入Y栈。当点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，说明没有页面可以继续后退浏览了。当Y栈没有数据，那就说明没有页面可以点击前进浏览了。

五、思考

1. 我们在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？

答：因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。

正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。

2.我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？

答：JVM里面的栈和我们这里说的是一回事，被称为方法栈。和前面函数调用的作用是一致的，用来存储方法中的局部变量。