目录

一、前言

二、例子

三、快速排序算法图片讲解

四、快速排序算法代码

五、纯净代码

---

一、前言

用比较好懂的方式讲一下快速排序算法。

二、例子

如果我有一堆钱，想数清楚，最快的方案是什么？

 答：先分类，一百的一堆，十块的一堆.....，如果还是多，那再把100的分成两三堆，再每堆每堆数。

 快速排序就是这样，先分类再排序，再分类，再排序。

三、快速排序算法图片讲解

 但是怎么分呢？按照第一个数字分。我们先随便拿一组数字，第一个数是5。（如图2所示）

我们接下来就按照快速排序算法，用这个数字过一遍。

第一步：把第一个数拿出来        5拿出来（如图3所示）

然后我们就发现，第一位空了出来，接下来，我们做一个分类，把比5小的都往前拿，比5大的都往后拿 。

第二步：因为第一位是空的，所以我们就从后往前找一个比5小的数，填到第一位去。

过程：我们发现，从后往前数，2是第一个比5小的，就把2放到前面去。（如图4所示）

这里我们记一下，2原来的位置是正数第7位。也就是说，7位往后都比5大，不用再关心了。

再然后，我们发现，后面空了一位出来， 我们再从前往后数，把比5大的挪到后面去。

第三步：因为后面是空的，所以我们就从前往后找一个比5大的数，填过去。

过程：我们发现，从前往后数，第二位，数字7，是比5大的，我们把数字7挪到后面去。（如图5所示）

 现在空出来的是前面的格子，并且，7往后的数字都是比较过的，都比5大，所以我们从7往前数，继续找比5小的。

第四步：因为前面是空的，所以我们就从第七位往前找一个比5小的数，填过去。

过程：我们发现，继续往前数，1是比5小的，把1放到前面去。（如图6所示） 

第五步：因为后面是空的，所以我们从第二位往后找一个比5大的数，填过去。

过程：继续往后数，6是比5大的，把6放到前面去。（如图6所示）

第六步：因为前面是空的，所以我们就从第六位往前找一个比5小的数，填过去。

过程：继续往前数，3是比5小的，把3放到前面去。（如图7所示）

 第七步：所有的交换都完成了，现在左边都是比5小的，右边都是比5大的。最后把5填回去。（如图7所示）

 第8步：把5前面的数和5后面的数分开成两堆，再做同样的事情。

四、快速排序算法代码

 我们先把刚才图片示例的部分用代码写出来。

//先看这部分            //一个数组   //这一堆第几是开始
public int Partition(List<int> li, int left, int right)//这一堆第几个是结束
{//把第一位先拿出来，就是那个5int tmp = li[left];//因为我也从左边数，也从右边数，他们还没数到一起的时候while (left<right){//空位在左边，所以从右边数 //到左边前        //如果比5大while (left < right&&li[right]>=tmp)      {//继续往前找right--;}//找到了比5小的，就把它放到左边空的位置li[left] = li[right];//现在空位就去右边了，再从左边开始找比5大的//到最右边前      //如果比5小while (left < right && li[left] <= tmp){//继续往后找left++;}//找到了比5大的，填到后面去li[right] = li[left];//如果没有找完，就继续找，如果找完了，就走下面的代码}//都找完了，把5填回去li[left] = tmp;//最后把元素填回去//把5的位置返回去，因为后面要从5的位置分成左一半，右一半return left;}

我们使用上面的代码，进行完整的排序。

public void QuickSort(List<int> li,int left,int right)
{//中间位初始化int mid = 0;if (left<right){//这个就是上面的代码，返回了刚才5的位置，mid = Partition(li,  left, right);//我们把数组劈成了两半//5左边的，重新去执行一遍排序QuickSort(li,left,mid-1);//5右边的，重新去执行一遍排序 QuickSort(li, mid+1, right);}
}

 然后他们就和套娃一样，不停的一分为二，不停的排序，直到全部排序完成。

五、纯净代码

    public void QuickSort(List<MScrollSlot> li, int left, int right){int mid = 0;if (left < right){mid = Partition(li, left, right);QuickSort(li, left, mid - 1);QuickSort(li, mid + 1, right);}}public int Partition(List<MScrollSlot> li, int left, int right){MScrollSlot tmp = li[left];while (left < right){while (left < right && li[right].GetScale() >= tmp.GetScale()){right--;}li[left] = li[right]; while (left < right && li[left].GetScale() <= tmp.GetScale()){left++;}li[right] = li[left];}li[left] = tmp;return left;}