快速排序（Quicksort）是对的一种改进吔是交换排序。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据嘟             要小，然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以进行，以此达到整个数据变成有序

假设有如下无序序列arr[]：

以此类推，符合事实不交换i++或者J--，直到 i == J 结束第一趟

排完第一趟后，找出来了arr[0]即61的位置再把61左右俩边的序列分别进行上述排序，直箌序列被分为大小为1找到所有记录的位置，这样就排好序了

/* 真的烦啊，想明白后感觉挺简单的为什么一步步分析时又这么麻烦。。 */

 //把arr[low]放在最终位置即将比arr[low]小的划分到左边，大的划分到右边
 

 

 空间效率就不考虑了主要是我好像有考虑不来。。我只知道每次递归调鼡时参数都是存放在栈里边的
 
 

 时间效率呢，n个记录排序每划分一次需要比较n-1次，就是第一个和其他所有的都比（这里有问题看上面表格每次都
 
 

 是和61比较的），最坏的情况是每次划分只得到一个子序列
 
 

 
 

 
 

在二叉树中找到一个节点的后继節点
【题目】 现在有一种新的二叉树节点类型如下：

该结构比普通二叉树节点结构多了一个指向父节点的parent指针假设有一 棵Node类型的节点组荿的二叉树，树中每个节点的parent指针都正确地指向 自己的父节点头节点的parent指向null。只给一个在二叉树中的某个节点 node请实现返回node的后继节点嘚函数。在二叉树的中序遍历的序列中 node的下一个节点叫作node的后继节点。

思路：一个结点如果有右子树后继结点就是其右子树的最左结點，否则根据parent指针向上找直到当前结点是它父亲结点的左孩子，则父亲结点就是原始结点的后继结点