数据结构之栈（三）：顺序栈实现
顺序栈的实现和使用数组实现原理一样，都是预先申请一段连续的地址块作为数据域，通过栈顶下标或指针移动完成压栈、出栈等操作。不同的是，使用指针的顺序栈支持栈满时扩容操作，原理更倾向于vector的实现。
顺序栈初始化时申请一块固定大小内存空间保存数据，栈顶指针在内存区域来回移动：
分类 数据结构和算法 下的文章
数据结构之栈（二）：链式栈实现
链栈的原理和链表的原理一样，通过一个next指针把一个个的节点链起来：
初始时，栈底指针和栈顶指针都为空，每插入一个节点，栈顶指针改变，当前插入节点的next指针指向之前的栈顶元素。
数据结构之栈（一）：使用数组实现栈
栈是一种“先进后出”的数据结构，最先进入栈的元素位于栈的底端，最后进入的位于顶端。
其主要的接口函数为：
pop(): 弹出顶端元素size(): 返回栈容量empty(): 判断栈是否为空push(T data): 添加元素到栈顶top(): 返回顶端元素
排序算法之冒泡排序
一、原理
原理很简单， 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。 冒泡排序是一种稳定的排序算法。
冒泡排序不管在什么情况下，时间复杂度都是O($n^2$)。
对比插入排序来说，在平均的情况下，插入排序性能是冒泡排序的两倍。
图例：
以数组[54, 15, 34, 82, 15, 46, 85, 43]为例：
第一次循环先比较54和15，54大于15，交换两个元素：
比较54和34，54大于34，交换两个元素：
比较54和82，54不大于82，不交换：
比较82和15，82大于15，交换两个元素：
按照相同的方式一直对比，直到最后，85被移动到最后：
此时完成一轮冒泡排序，接下来将剩下的元素再次执行同样的操作即可完成对整个数组的遍历。
二、代码实现
2.1 C++实现
template<typename T>
void bubble_sort(vector<T> &data) {
int i, j;
// i的作用是控制遍历次数，n个元素的数组一共要执行n-1轮冒泡
for (i = 0; i < data.size() - 1; i++) {
// j从第二个元素开始，每次和前面的元素对比
for (j = 1; j < data.size() - i; j++) {
if (data[j] < data[j - 1]) {
// 如果当前元素小于前一个元素，交换两个元素
swap(data[j - 1], data[j]);
}
}
}
}2.2 python实现
def bubble_sort(data):
size = len(data)
for i in range(0, size - 1):
for j in range(size - 1, i, -1):
if data[j] < data[j - 1]:
data[j - 1], data[j] = data[j], data[j - 1]三、冒泡排序的优化
当对第x个数据排序时，冒泡排序每次都会遍历剩下的n-x个元素，即使整个序列已经有序。
因此可以在这一个层面进行优化，如果序列已经有序了，则后面的排序就无需进行了，可以添加一个标记字段来处理这个问题。
template<typename T>
void bubble_sort(vector<T> &data) {
int i, j;
bool again = true;
for (i = 0; again && i < data.size() - 1; i++) {
// 每开始新一轮冒泡，把标记置为false。
again = false;
for (j = 1; j < data.size() - i; j++) {
if (data[j] < data[j - 1]) {
swap(data[j - 1], data[j]);
// 只有出现了逆序，才把标记置为true
again = true;
}
}
}
}排序算法之快速排序
一、原理
选择排序的原理是分治，把排序序列切分成若干个小组后分别排序。每次排序都以随机的一个元素作为哨兵（一般都以排序区间的中间元素或者首元素作为哨兵），比他大的元素都放到右边，比它小的都放到左边。然后分别对该元素左边和右边的元素再法排序，直到所有的元素都是有序状态。
具体的排序过程描述为：
- 选取一个哨兵元素temp，设置两个指针low和high分别从数组的两端开始遍历。
- high指针从右到左遍历，当遇到A[high] < temp的时候，设置A[low]的值为A[high]。
- low指针从左到右遍历，当遇到A[low] > temp的时候，设置A[high]的值为A[low]。
- 重复执行2、3步，直到low和high相遇，设置low元素的值为temp。此时low左边的元素都小于temp，low右边的元素都大于temp。再分别对左右子区间的元素分别排序。
图例：
以数组[54, 15, 34, 82, 15, 46, 85, 43]为例，初始状态时设置low指针指向第一个元素，high指针指向最后一个元素，temp为第一个元素的值54：
遍历high指针，从右到左找到第一个小于54的元素43，赋值给low：
遍历low指针，从左到右找到第一个大于54的元素82，赋值给high：
遍历high指针，从右到左找到一个小于54的元素46，赋值给low：
遍历low指针，继续寻找第一个大于54的元素。但是直到遇见high指针，都没有找到再比54大的元素，把temp值赋值给low：
此时第一轮排序完成，54左边的元素都比它小，右边的元素都比它大。因此按照这个操作，继续对左边和右边的区间再执行相同的操作，多次排序即可完成整个数组的排序。
复杂度分析：
最坏的情况下，数组无序，快速排序和冒泡排序差不多。
- 时间复杂度：最坏情况下，时间复杂度为O($n^2$)；最好的情况和平均情况下算法复杂度为O($n\log(n)$)。
- 空间复杂度：最坏情况下，空间复杂度为O($n$)；平均情况下空间复杂度为O($\log(n)$)。
二、代码实现
快排的写法多样，以下实现了C++和Python两种语言的快速排序算法实现。
其中C++选取的哨兵是数组第一个元素，python选取的哨兵是数组中间元素。
2.1 C++实现
以区间中点作为排序标杆：
/*
* 快速排序算法实现，对[left, right)部分的数组排序。
* @data 待排序数组
* @left 左区间，包含该下标元素
* @right 右区间，不包含该下标元素
*/
template<typename T>
void quick_sort(vector<T> &data, int left, int right) {
int i = left, j = right - 1;
T temp;
if (right <= left) {
return;
}
temp = data[i];
while (i < j) {
// 从右到左遍历找到一个比temp大的
while (i < j && data[j] >= temp) {
j--;
}
if (i < j && data[j] < temp) {
data[i] = data[j];
}
// 从左到右遍历找到一个比temp小的
while (i < j && data[i] <= temp) {
i++;
}
if (i < j && data[i] > temp) {
data[j] = data[i];
}
}
data[i] = temp;
// 排序的区间是左闭右开
quick_sort(data, left, i);
quick_sort(data, i + 1, right);
}2.2 python
以区间中点元素作为标杆：
import math
def quick_sort(data, left, right):
"""
快速排序算法，对[left, right)区间的元素排序
:param data: 待排序数组
:param left: 待排序数组的左区间，包含对对该下标元素排序
:param right: 待排序数组的右区间，不包含对该下标元素排序
:return:
"""
i, j = left, right - 1
if i >= j:
return
# 选择区间中点元素作为哨兵
mid = math.floor((i + j) / 2)
temp = data[mid]
data[i], data[mid] = data[mid], data[i]
while i < j:
while i < j and data[j] >= temp:
j -= 1
if i < j and data[j] < temp:
data[i] = data[j]
while i < j and data[i] <= temp:
i += 1
if i < j and data[i] > temp:
data[j] = data[i]
data[i] = temp
quick_sort(data, left, i)
quick_sort(data, i + 1, right)2.3 golang实现快速排序
2020-02-29刷leetcode添加，使用数组中间元素作为哨兵。排序边界是[left, right]
/*
* 快速排序，对[left, right]区间内的元素排序
* @nums 排序数组
* @left 左边界
* @right 右边界，包含该下标元素
*/
func doQuickSort(nums []int, left, right int) {
i, j := left, right
if left >= right {
return
}
// 取中间元素作为哨兵
mid := (i + j) / 2
x := nums[mid]
nums[mid], nums[i] = nums[i], nums[mid]
for i < j {
for nums[j] >= x && i < j {
j -= 1
}
if i < j && nums[j] < x {
nums[i] = nums[j]
}
for nums[i] <= x && i < j {
i += 1
}
if i < j && nums[i] > x {
nums[j] = nums[i]
}
}
nums[i] = x
doQuickSort(nums, left, i-1)
doQuickSort(nums, i+1, right)
}
func quickSort(nums []int) []int {
doQuickSort(nums, 0, len(nums)-1)
return nums
}排序算法之选择排序
一、原理
选择排序（Selection sort）是一种简单直观的排序算法，它的工作原理是：从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
选择排序无论在最坏或是最好的情况，时间复杂度都是O($n^2$)
排序逻辑：
for i in (i, n-1)
min = data[i]
for j in (j, n)
如果min>data[j]，标记当前位置，重新设置min，继续循环
把最小的元素min和data[i]替换图解
以序列[3, 1, 5, 4, 7]为例，执行第一趟排序时，找到的最小元素是1，把它放到最前面和3对换：
第二趟排序，未排序数组为[3, 5, 4, 7]，此时数组内最小的元素是3，刚好就是当前数组最开头的位置，因此无需替换，继续下一趟排序。
第三趟排序，未排序数组为[5, 4, 7]，此时数组内最小的元素是4，放到最前面和5对换：
执行完第三趟排序后，数组就已经有序了。但是对计算机而言却并不知情，它还会继续判断后面的[5, 7]，但是刚好每次排序的时候，他们就处于应该在的位置。
二、代码实现
2.1 C++实现
template <typename T>
void select_sort(vector<T> &v) {
size_t i, j;
// 记录最小的下标
T min_idx;
if (v.size() < 2)
return;
// 只用执行n-1趟排序
for (i = 0; i < v.size() - 1; i++) {
min_idx = i;
// 找到最小的下标
for (j = i + 1; j < v.size(); j++) {
if (v[j] < v[min_idx])
min_idx = j;
}
// 替换最小的
if (min_idx != i) {
my_swap(v[i], v[min_idx]);
}
}
}2.2 python实现
def select_sort(data):
size = len(data)
for i in range(size - 1):
k = i
for j in range(i + 1, size):
if data[j] < data[k]:
k = j
if k != i:
data[k], data[i] = data[i], data[k]2.3 c语言实现
int select_sort(int* data, unsigned int len) {
unsigned int i, j, min;
for (i = 0; i < len - 2; i++) {
min = i;
for (j = i + 1; j < len - 2; j++) {
if (data[j] < data[i])
min = j;
}
if (min != i)
swap(data[min], data[i]);
}
}排序算法之插入排序
一、原理
从排序序列的第二个元素开始，依次往前面查询，直到找到一个合适的位置就把它插进去。
每个元素在交换完成之后[0, n]都是一个有序序列，它的时间复杂度为O(n^2)。
最好的情况下，序列有序，时间复杂度为O(n)。
最坏的情况下，序列逆序，时间复杂度为O(n^2)。随机的情况下平均时间复杂度接近于最坏的情况。
排序逻辑：
for i in (1, n-1)
使用data[i]前向查找，找到一个合适的位置插入