图解快排

2019-02-21 本文已影响1人 ea7607fa5153

下面简单演示下如何用快排来实现下面数组从小到大排序

int arr[] = {2 4 1  8 4 0 3 6 2 5 8};

首先什么都别想，跟着我一步一步的实现它

将这些数字放在一个数组里，下标从0开始。分别设置两个变量start，end指向数组的头和尾。以数组的第一个元素为关键字key。如图所示

1

快排的思想是选取一个关键字，所有比这个关键字大的放后面，比它小的放前面

1.先比较end变量所指向的元素，若比key大，向前挪一位，直到满足条件为止。挪一位的前提是当start<end时，所以必须满足下列条件时end才能减一

start<end && arr[end]>=key

下图中end指向的8大于关键字2，向前挪一位，end--

2

2.没有交换，继续向前挪位，直到end指向了0

图有点失误，大家忽略这张图的swap(arr,end,start)就可以啦

3

3.此时不满足start<end && (arr[end]=0)>=(key=2)这个条件，将end指向的0跟start指向的2交换

swap(arr,end,start)

4

4.现在开始比较start指向的元素，若比key小，向后挪一位，直到满足条件为止。挪一位的前提是当start<end时，所以必须得同时满足这个条件start<end && arr[start]<=key时start才能加一

start指向了4

5

5.此时不满足start<end && (arr[start]=4)<=(key=2)这个条件，将start指向的4跟end指向的2交换

swap(arr,end,start)

6

6.好了，开启一轮新的循环，从end开始，当start<end && arr[end]>key不满足时进行交换。也就是end指向 1 时

7

7.继续交换

swap(arr,end,start)

8

8.继续从start这边比较，start指向 1 小于关键字key=2，于是start往前挪一位，start++，此时start==end。外循环退出，返回start所指向的下标。

9

拿到返回来的start，将数组分割成两部分，如图

10

此时再分别对两部分数组进行快排，重复上一步骤，就可以得到排序好的数组啦~~~

下面是晚饭用java实现的快排，存放在github上，有兴趣的你不妨自己写出来，这个代码仅供参考噢
java实现的快排代码，包括时间复杂度分析

欢迎关注，微信公众号，获取最新文章

晚饭带你学Java