快速排序(Quick Sort)是对冒泡排序的一种改进，基本思想是选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中一部分的值都小于枢轴，另一部分都大于枢轴。然后继续对这两部分继续进行排序，从而使整个序列达到有序。
递归实现：
void QuickSort(int* array,int left,int right)
{
	assert(array);
	if(left >= right)//表示已经完成一个组
	{
		return;
	}
	int index = PartSort(array,left,right);//枢轴的位置
	QuickSort(array,left,index - 1);
	QuickSort(array,index + 1,right);
}

PartSort()函数是进行一次快排的算法。

对于快速排序的一次排序，有很多种算法，我这里列举三种。
左右指针法
选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴。
设置两个变量left = 0;right = N - 1;
从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。

当left >= right时，一趟快速排序就完成了，这时将Key和array[left]的值进行一次交换。

一次快排的结果:4   1  3  0  2  5  8  6  7  9
基于这种思想，可以写出代码：
int PartSort(int* array,int left,int right)
{
	int& key = array[right];
	while(left < right)
	{
		while(left < right && array[left] <= key)
		{
			++left;
		}
		while(left < right && array[right] >= key)
		{
			--right;
		}
		swap(array[left],array[right]);
	}
	swap(array[left],key);
	return left;
}

问题：下面的代码为什么还要判断left < right？
while(left < right && array[left] <= key)

key是整段序列最后一个，right是key前一个位置，如果array[right]这个位置的值和key相等，满足array[left] <= key，然后++left,这时候left会走到key的下标处。
###挖坑法
选取一个关键字(key)作为枢轴，一般取整组记录的第一个数/最后一个，这里采用选取序列最后一个数为枢轴，也是初始的坑位。
设置两个变量left = 0;right = N - 1;
从left一直向后走，直到找到一个大于key的值，然后将该数放入坑中，坑位变成了array[left]。
right一直向前走，直到找到一个小于key的值，然后将该数放入坑中，坑位变成了array[right]。
重复3和4的步骤，直到left和right相遇，然后将key放入最后一个坑位。

当left >= right时，将key放入最后一个坑，就完成了一次排序。

注意，left走的时候right是不动的，反之亦然。因为left先走，所有最后一个坑肯定在array[right]。
写出代码：
int PartSort(int* array,int left,int right)
{
	int key = array[right];
	while(left < right)
	{
		while(left < right && array[left] <= key)
		{
			++left;
		}
		array[right] = array[left];
		while(left < right && array[right] >= key)
		{
			--right;
		}
		array[left] = array[right];	 
	}
	array[right] = key;
	return right;
}

###前后指针法
定义变量cur指向序列的开头，定义变量pre指向cur的前一个位置。
当array[cur]  < key时，cur和pre同时往后走，如果array[cur]>key，cur往后走，pre留在大于key的数值前一个位置。
当array[cur]再次 < key时，交换array[cur]和array[pre]。
通俗一点就是，在没找到大于key值前，pre永远紧跟cur，遇到大的两者之间机会拉开差距，中间差的肯定是连续的大于key的值，当再次遇到小于key的值时，交换两个下标对应的值就好了。
带着这种思想，看着图示应该就能理解了。

下面是实现代码：
int PartSort(int* array,int left,int right)
{
	if(left < right){
		int key = array[right];
		int cur = left;
		int pre = cur - 1;
		while(cur < right)
		{
			while(array[cur] < key && ++pre != cur)//如果找到小于key的值，并且cur和pre之间有距离时则进行交换。注意两个条件的先后位置不能更换，可以参照评论中的解释
			{
				swap(array[cur],array[pre]);
			}
			++cur;
		}
		swap(array[++pre],array[right]);
		return pre;
	}
	return -1;
}

最后的前后指针法思路有点绕，多思考一下就好了。它最大的特点就是，左右指针法和挖坑法只能针对顺序序列进行排序，如果是对一个链表进行排序， 就无用武之地了。
所以记住了，前后指针这个特点！
###快速排序的优化
首先快排的思想是找一个枢轴，然后以枢轴为中介线，一遍都小于它，另一边都大于它，然后对两段区间继续划分，那么枢轴的选取就很关键。
1、三数取中法

上面的代码思想都是直接拿序列的最后一个值作为枢轴，如果最后这个值刚好是整段序列最大或者最小的值，那么这次划分就是没意义的。

所以当序列是正序或者逆序时，每次选到的枢轴都是没有起到划分的作用。快排的效率会极速退化。
所以可以每次在选枢轴时，在序列的第一，中间，最后三个值里面选一个中间值出来作为枢轴，保证每次划分接近均等。
2、直接插入

由于是递归程序，每一次递归都要开辟栈帧，当递归到序列里的值不是很多时，我们可以采用直接插入排序来完成，从而避免这些栈帧的消耗。
整个代码：
//三数取中
int GetMid(int* array,int left,int right)
{
    assert(array);
    int mid = left + ((right - left)>>1);
    if(array[left] <= array[right])
    {
        if(array[mid] <  array[left])
            return left;
        else if(array[mid] > array[right])
            return right;
        else
            return mid;
    }
    else
    {
        if(array[mid] < array[right])
            return right;
        else if(array[mid] > array[left])
            return left;
        else
            return mid;
    }

}

//左右指针法
int PartSort1(int* array,int left,int right)
{
    assert(array);
    int mid = GetMid(array,left,right);
    swap(array[mid],array[right]);
    
    int& key = array[right];
    while(left < right)
    {
        while(left < right && array[left] <= key)//因为有可能有相同的值，防止越界，所以加上left < right
            ++left;
        while(left < right && array[right] >= key)
            --right;

        swap(array[left],array[right]);
    }

    swap(array[left],key);
    return left;
}

//挖坑法
int PartSort2(int* array,int left,int right)
{
    assert(array);
    int mid = GetMid(array,left,right);
    swap(array[mid],array[right]);
    
    int key = array[right];
    while(left < right)
    {
        while(left < right && array[left] <= key)
            ++left;
        array[right] = array[left];
       
        while(left < right && array[right] >= key)
            --right;
        array[left] = array[right];
    }
    array[right] = key;
    return right;
}

//前后指针法
int PartSort3(int* array,int left,int right)
{
    assert(array);
    int mid = GetMid(array,left,right);
	swap(array[mid],array[right]);
    if(left < right){
	    int key = array[right];
	    int cur = left;
	    int pre = left - 1;
	    while(cur < right)
	    {
	         while(array[cur] < key && ++pre != cur)
	         {
	             swap(array[cur],array[pre]);
	         }
	            ++cur;
	    }
	        swap(array[++pre],array[right]);
	        return pre;
	}
	return -1;
}

void QuickSort(int* array,int left,int right)
{
    assert(array);
    if(left >= right)
        return;

	//当序列较短时，采用直接插入
    if((right - left) <= 5)
    InsertSort(array,right-left+1);
    
    int index = PartSort3(array,left,right);
    QuickSort(array,left,index-1);
    QuickSort(array,index+1,right);
}

int main()
{
	int array[] = {4,1,7,6,9,2,8,0,3,5};
	QuickSort(array,0,sizeof(array)/sizeof(array[0]) -1);//因为传的是区间，所以这里要 - 1；
}

非递归实现
递归的算法主要是在划分子区间，如果要非递归实现快排，只要使用一个栈来保存区间就可以了。

一般将递归程序改成非递归首先想到的就是使用栈，因为递归本身就是一个压栈的过程。
void QuickSortNotR(int* array,int left,int right)
{
	assert(array);
	stack<int> s;
	s.push(left);
	s.push(right);//后入的right，所以要先拿right
	while(!s.empty)//栈不为空
	{
		int right = s.top();
		s.pop();
		int left = s.top();
		s.pop();
		
		int index = PartSort(array,left,right);
		if((index - 1) > left)//左子序列
		{
			s.push(left);
			s.push(index - 1);
		}
		if((index + 1) < right)//右子序列
		{
			s.push(index + 1);
			s.push(right);
		}
	}
}

上面就是关于快速排序的一些知识点，如果哪里有错误，还望指出。

python中使用递归实现斐波那契数列
python中使用递归实现斐波那契数列
先来了解一下
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。*
使用递归返回前n项的斐波那契数列：
func_1(n-2)+func_1(n-1)此代码为本节代码的主要代码
def func_1(n):

if n == 0:

return 0

elif n == 1 or n == 2:

return 1

else:

return func_1(n-2)+func_1(n-1)

假设n取4

return func_1(2)+func_1(3)

func_1(2)带入函数则返回1，func_1(3)带入函数则返回 func_1(3-2)+func_1(3-1)即为 func_1(1)+func_1(2) ，带入函数为1+1 所以得出结论func_1(4) =func_1(2)+func_1(3)=func_1(2)+func_1(1)+func_1(2)=3

刚才的递推函数只能返回第n各值，要想返回前n项值，得在外围建个函数将得出的值一一添加进去
代码实现：

def func(a):

def func_1(n):

if n == 0:

return 0

elif n == 1 or n == 2:

return 1

else:

return func_1(n-2)+func_1(n-1)

list_1 = []

for i in range(a):

list_1.append(func_1(i))

return list_1
print(func(20))


祝大家Python学习顺利！

本文并非我所写，是复制的该链接中的内容；

最近学习二叉树，想编程实现递归和非递归的实现方式；

递归的方式就不说了，因为大家的递归程序都一样；但是对于非递归的实现方式，

根据这几天的查阅资料已看到差不多近10种不同的遍历二叉树的非递归实现方式，其中本文是个人觉得在前中后序三种遍历方式中，代码最统一的一种方法；

1：本文链接源于：https://www.jianshu.com/p/49c8cfd07410

2：在这里向大家推荐另外一种也是很强大的统一的实现方式，实现过程真的挺强大的，当然这也是别人的，我只是在这里总结一下，方便大家学习，该链接为：http://drinkjava2.iteye.com/blog/2353983

 

 

上面第一个链接中的内容如下：

解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序，中序，后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来，可是在手生时写出非递归遍历恐非易事。正因为并非易事，所以网上出现无数的介绍二叉树非递归遍历方法的文章。可是大家需要的真是那些非递归遍历代码和讲述吗？代码早在学数据结构时就看懂了，理解了，可为什么我们一而再再而三地忘记非递归遍历方法，却始终记住了递归遍历方法？

三种递归遍历对遍历的描述，思路非常简洁，最重要的是三种方法完全统一，大大减轻了我们理解的负担。而我们常接触到那三种非递归遍历方法，除了都使用栈，具体实现各有差异，导致了理解的模糊。本文给出了一种统一的三大非递归遍历的实现思想。

三种递归遍历


//前序遍历
void preorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        path.push_back(root->val);
        preorder(root->left, path);
        preorder(root->right, path);
    }
}



//中序遍历
void inorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        inorder(root->left, path);
        path.push_back(root->val);
        inorder(root->right, path);
    }
}



//后续遍历
void postorder(TreeNode *root, vector<int> &path)
{
    if(root != NULL)
    {
        postorder(root->left, path);
        postorder(root->right, path);
        path.push_back(root->val);
    }
}


由上可见，递归的算法实现思路和代码风格非常统一，关于“递归”的理解可见我的《人脑理解递归》。

教科书上的非递归遍历


//非递归前序遍历
void preorderTraversal(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != NULL || !s.empty())
    {
        while(p != NULL)
        {
            path.push_back(p->val);
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}



//非递归中序遍历
void inorderTraversal(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    TreeNode *p = root;
    while(p != NULL || !s.empty())
    {
        while(p != NULL)
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty())
        {
            p = s.top();
            path.push_back(p->val);
            s.pop();
            p = p->right;
        }
    }
}



//非递归后序遍历-迭代
void postorderTraversal(TreeNode *root, vector<int> &path)
{
    stack<TempNode *> s;
    TreeNode *p = root;
    TempNode *temp;
    while(p != NULL || !s.empty())
    {
        while(p != NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点
        {
            TreeNode *tempNode = new TreeNode;
            tempNode->btnode = p;
            tempNode->isFirst = true;
            s.push(tempNode);
            p = p->left;
        }
        if(!s.empty())
        {
            temp = s.top();
            s.pop();
            if(temp->isFirst == true)   //表示是第一次出现在栈顶
            {
                temp->isFirst = false;
                s.push(temp);
                p = temp->btnode->right;
            }
            else  //第二次出现在栈顶
            {
                path.push_back(temp->btnode->val);
                p = NULL;
            }
        }
    }
}


看了上面教科书的三种非递归遍历方法，不难发现，后序遍历的实现的复杂程度明显高于前序遍历和中序遍历，前序遍历和中序遍历看似实现风格一样，但是实际上前者是在指针迭代时访问结点值，后者是在栈顶访问结点值，实现思路也是有本质区别的。而这三种方法最大的缺点就是都使用嵌套循环，大大增加了理解的复杂度。

更简单的非递归遍历二叉树的方法

这里我给出统一的实现思路和代码风格的方法，完成对二叉树的三种非递归遍历。


//更简单的非递归前序遍历
void preorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
            s.push(make_pair(root, true));
        }
    }
}



//更简单的非递归中序遍历
void inorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root->right, false));
            s.push(make_pair(root, true));
            s.push(make_pair(root->left, false));
        }
    }
}



//更简单的非递归后序遍历
void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack< pair<TreeNode *, bool> > s;
    s.push(make_pair(root, false));
    bool visited;
    while(!s.empty())
    {
        root = s.top().first;
        visited = s.top().second;
        s.pop();
        if(root == NULL)
            continue;
        if(visited)
        {
            path.push_back(root->val);
        }
        else
        {
            s.push(make_pair(root, true));
            s.push(make_pair(root->right, false));
            s.push(make_pair(root->left, false));
        }
    }
}


以上三种遍历实现代码行数一模一样，如同递归遍历一样，只有三行核心代码的先后顺序有区别。为什么能产生这样的效果？下面我将会介绍。

有重合元素的局部有序一定能导致整体有序

这就是我得以统一三种更简单的非递归遍历方法的基本思想：有重合元素的局部有序一定能导致整体有序。

如下这段序列，局部2 3 4和局部1 2 3都是有序的，但是不能由此保证整体有序。



Image Title

 

而下面这段序列，局部2 3 4,4 5 6,6 8 10都是有序的，而且相邻局部都有一个重合元素，所以保证了序列整体也是有序的。



Image Title

 

应用于二叉树

基于这种思想，我就构思三种非递归遍历的统一思想：不管是前序，中序，后序，只要我能保证对每个结点而言，该结点，其左子结点，其右子结点都满足以前序/中序/后序的访问顺序,整个二叉树的这种三结点局部有序一定能保证整体以前序/中序/后序访问，因为相邻的局部必有重合的结点，即一个局部的“根”结点是另外一个局部的“子”结点。

如下图，对二叉树而言，将每个框内结点集都看做一个局部，那么局部有A,A B C,B D E,D,E,C F,F,并且可以发现每个结点元素都是相邻的两个局部的重合结点。发觉这个是非常关键的，因为知道了重合结点，就可以对一个局部排好序后，通过取出一个重合结点过渡到与之相邻的局部进行新的局部排序。我们可以用栈来保证局部的顺序（排在顺序前面的后入栈，排在后面的先入栈，保证这个局部元素出栈的顺序一定正确），然后通过栈顶元素(重合元素)过渡到对新局部的排序，对新局部的排序会导致该重合结点再次入栈，所以当栈顶出现已完成过渡使命的结点时，就可以彻底出栈输出了（而这个输出可以保证该结点在它过渡的那个局部一定就是排在最前面的），而新栈顶元素将会继续完成新局部的过渡。当所有结点都完成了过渡使命时，就全部出栈了，这时我敢保证所有局部元素都是有序出栈，而相邻局部必有重合元素则保证了整体的输出一定是有序的。这种思想的好处是将算法与顺序分离，定义何种顺序并不影响算法，算法只做这么一件事：将栈顶元素取出，使以此元素为“根”结点的局部有序入栈，但若此前已通过该结点将其局部入栈，则直接出栈输出即可。



Image Title

 

从实现的程序中可以看到：三种非递归遍历唯一不同的就是局部入栈的三行代码的先后顺序。所以不管是根->左->右,左->根->右,左->右->根,甚至是根->右->左,右->根->左,右->左->根定义的新顺序，算法实现都无变化，除了改变局部入栈顺序。

值得一提的是，对于前序遍历，大家可能发现取出一个栈顶元素，使其局部前序入栈后，栈顶元素依然是此元素，接着就要出栈输出了，所以使其随局部入栈是没有必要的，其代码就可以简化为下面的形式。


void preorderTraversalNew(TreeNode *root, vector<int> &path)
{
    stack<TreeNode *> s;
    s.push(root);
    while(!s.empty())
    {
        root = s.top();
        s.pop();
        if(root == NULL)
        {
            continue;
        }
        else
        {
            path.push_back(root->val);
            s.push(root->right);
            s.push(root->left);
        }
    }
}


这就是我要介绍的一种更简单的非递归遍历二叉树的方法。

 

二分查找（非递归实现和递归实现）

public class BinarySearch {

    //非递归实现
    public static int binarySearch(int array[], int low, int high, int key) {
        while (low <= high) {
            int middle = (low + high) / 2;
            if (array[middle] == key) {
                return array[middle];
            } else if (array[middle] > key) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }

    //递归实现
    public static int binarySearch2(int[] array, int low, int high, int key) {
        if (low > high) {
            return -1;
        } else {
            int middle = (low + high) / 2;
            if (array[middle] == key) {
                return array[middle];
            } else if (array[middle] > key) {
                return binarySearch2(array, low, middle - 1, key);
            } else {
                return binarySearch2(array, middle + 1, high, key);
            }
        }
    }

    public static void main(String[] args) {
        int a[] = { 2, 4, 6, 5, 8, 9 };
        int reslut = binarySearch2(a, 0, a.length - 1, 1);
        System.out.println("result : " + reslut);
    }

}