快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

函数形参分别为待排序数组a，待排序数组的最左边数的下标left,待排序数组的最右边数的下标right。

当快排递归到待排数组是一些短数组的时候，由于短数组的个数很多，再加上这些短数组都需要递归到数组中只有一个数的情况才可以返回，这时候会不断的创建函数栈帧，然后导致时间复杂度降低。因为这些待排的短数组都是一个接近于有序的的数组，用直接插入来优化更为合适。
代码实现：

任何一个递归程序在执行的时候，都是操作系统底层开辟了一个栈，每执行一个函数调用，那么就将当前函数的栈帧压栈，如果当前函数内部存在递归调用，那么就继续压入新的该函数代表的栈帧，直到某个函数内部没有再进行递归调用，该函数计算完毕后，将其出栈，并将计算结果返回给下一层栈帧。所以我们可以尝试着自己手搓一个栈，来实现函数的非递归调用。

要点1：我们要明白函数栈桢中存放的是什么，存放的是数组区间
要点2：数组区间只有一个值或者不存在值得时候不入栈

思路：首先将数组得左右下标压入栈中，这里注意顺序，栈得性质得后入先出，所以先将right压入栈中，在将left压入栈中，接下来相当于创建了函数栈桢，然后开始调用函数，因为递归函数中是不断得调用同一个函数，但是函数栈桢中得数组区间不同，所以接下来要通过循环来反复调用单趟排序，并且在循环中重复定义数组区间得值，调用完单趟排序后将子区间压栈，要判断一下数组区间至少有两个元素。
代码实现：