一直以来，对排序都不太感冒，能立马写出来的排序恐怕就只有冒泡排序了，但是我又深知排序算法还是挺重要的

然后，就不得不研究一下，那首先拿快速排序来开刀吧

我们先不管排序的复杂度什么的，直入主题

题目：对数列 4 6 9 3 2 8 5 1 用快速排序

首先抽出一个数字（可以是这个数列中的任何一个）

抽取第一个吧 x=4

然后对数列进行标记

A1 = 4, A2=6 …… A8=1

首先从后往前找（肯定是找比x小的了，大的就放在后面吧，反正我们是从小到大，从左往右排的），一下子就找到了 A8就比X小

然后怎么办呢？

把A8的数字挖出来，放在x原来在的位置，那就是第一个喽

1 6 9 3 2 8 5 _  

后面找过了，开始找前面（前面要找比x大的），找到了A2

然后把它挖出来，放哪里呢？当然是当到坑里了，坑在哪？刚刚最后一个位置不是刚刚挖出一个数字嘛，于是那个位置就变成坑了（是不是挺合理的？嘿嘿）

1 _ 9 3 2 8 5 6

继续继续 

又该从后面找了，要从A8 开始，找啊找 找到了 A5 

于是数列变成了

1 2 9 3 _ 8 5 6

又要从前面找了，其实我觉得挺公平的，前后一替一次，防止吵架，这次是A3

1 2 _ 3 9 8 5 6

后面 A4 

1 2 3 _ 9 8 5 6

这个时候好像坑前面的都比x小，后面的都比x大，可是我们能看见，计算机不知道啊，怎么办呢？

那就再找一次，该前面了，上次找到了A3，继续找，A3后面就是A4，可是A4刚刚都被找过了，再来一次明显不合理嘛，一个人被抢一次就行了，再抢一次那就太对不起观众了，所以到此为止，不找了，那总得有个理由吧，什么理由呢？ 就说 A3++ = A4（位置，不是数字哦）或在 A4-- =A3

这找了一遍，好像还不是从小到大的排序啊，再来

这次咱们分开，坑前面的一伙，坑后面的一伙，中间的坑要填上 （用x填）

坑前的 1 2 3

{

这好像是排好序的了，可是计算机依然不知道啊（有的时候，计算就爱认死理，非要证据，那好，咱们给他证据）

继续挖坑算法（快速排序哪里去了？）

x=1

_ 2 3

从后面开始找，我去啊，都比X大，怎么办，淡然是结束挖坑啊

再然后呢？分坑，坑前（坑前没有，那就算了），坑后的是 2 3 （记得x填坑）

继续

x =2

后面就一个3,没有比x小的，结束挖坑

坑前没有，坑后就一个3，一个数字还比较个毛啊，结束结束，回家吃饭

于是坑前的就变成了 1 2 3 （毛啊，这不是没变嘛，这不一样，这个是计算机认证过的，能和没验的一样？没验的属于没贴牌的东西，错了售后肯定不管的）

}

坑前的没了，还有坑后的呢

{

9 8 5 6

继续挖坑算法

x= 9

_ 8 5 6

6 8 5 _

从前面找没找到，结束挖坑。分坑，填坑！

坑前 6 8 5 坑后 没有

继续挖坑算法

x=6

_ 8 5 

5 8 _

5 _ 8 

这个时候从前面找的和从后面找的碰头了，结束挖坑，分坑，填坑！

前坑和后坑都是一个数字，不用再挖坑了，就这样，后坑也弄完了

}

把前坑和后坑结合起来，于是

1 2 3 4 5 6 8 9

快速排序完成

总结一下

4 6 9 3 2 8 5 1

4  /  _ 6 9 3 2 8 5 1

4  /  1 6 9 3 2 8 5 _

4  /  1 _ 9 3 2 8 5 6

4  /  1 2 9 3 _ 8 5 6

4  /  1 2 _ 3 9 8 5 6

4  /  1 2 3 _ 9 8 5 6

4  /  ( 1 / _ 2 3 ) _ ( 9 / _ 8 5 6 )

4  /  ( 1 / _ ( 2 / _ 3 ) ) _ ( 9 / 6 8 5 _ )

4  /  ( 1 / _ ( 2 / _ ( 3 ) ) _ ( 9 / ( 6 / _ 8 5 ) _ )

4  /  ( 1 / _ ( 2 / _ ( 3 ) ) _ ( 9 / ( 6 /  5 8 _ ) _ )

4  /  ( 1 / _ ( 2 / _ ( 3 ) ) _ ( 9 / ( 6 /  5 _ 8 ) _ )

4  /  ( 1 / _ ( 2 / _ ( 3 ) ) _ ( 9 / ( 6 /  ( 5 ) _ ( 8 ) ) _ )

填坑 1 2 3 4 5 6 8 9