快速排序

一、什么是快速排序

     快速排序同冒泡排序一样,是一种 交换排序,通过元素之间的比较和交换达到排序目的。不同的是,冒泡排序每一轮只把一个元素(该轮最大/最小)冒泡到最右端;而快速排序每一轮则是选一个 基准元素( pivot),并让其它 比基准元素小的数通过交换放在基准元素 左端,而 比基准元素大的数则放在基准元素的 右端,从而把待排序的数列拆分成两部分,这就是 分治法的典型应用。然后不断重复这个过程( 递归),待排序的序列就变成了有序序列。

二、基准元素的选择

    通过上述对快速排序思想的了解,可以发现:基准元素的选择很重要。一般情况下,基准元素 最简单的就是 选择序列的第一个元素,但是如果待排序的序列是一个 逆序序列,期望排序成一个顺序序列,每一轮排序选择第一个元素作为基准元素,会出现什么情况呢?如下图:

**从上图中可以看出:**在这种情况下, 每一轮排序只会确定基准元素的位置(第一个元素/最后一个元素),而没有把序列分成较为均匀的两部分,在这种情况下,快速排序需要进行N轮,发挥不了分治法的优势,排序的 时间复杂度将会是O(n²)。

要解决上述问题,基准元素的选取我们可以不选取第一个元素,而是采用 随机选取基准元素。但是,即便是这样做,也有很小的几率选到数列的最大/最小元素作为基准元素,同样会影响分治的效果,所以快 速排序平均时间复杂度是nlog(n),最坏时间复杂度是O(n²)。

三、快速排序的两种实现方法

     看到这里,我们讨论了基准元素的选择,但是没有讨论快速排序具体的分治算法。现在已有的针对 快速排序的分治算法,比较典型的有两种,一种是 挖坑法,另一种是 指针交换法。下面我们来一一学习这两种算法。

3.1 挖坑法

     什么是挖坑法呢?顾名思义,每一次我们先挖好一个“坑”,然后寻找符合条件的元素填入坑中,填坑的元素的位置又变成新的坑,重复这个过程( 挖坑—填坑—挖坑),直到寻找元素的 左右指针相交,相交的位置填入基准元素的值,一轮排序结束。用文字说明有些地方说的不够详细,而且有些抽象,下面用图来描述这个过程:

给定原始数列如下,要求从小到大排序:

首先,选择基准元素(这里选第一个元素),记住 基准元素的位置index, 值pivot,这个位置就是“坑”的位置,然后设置两个指针 left和right,分别指向序列的左右两端的端点:

接下来,移动right指针( 坑在最左边,则先移动right指针)。如果找到的元素 比privot大,则 right指针继续向左移动。直到找到 小于等于pivot的元素, right指针就停止移动,并 把right指针所指的元素填入“坑”中, left指针向右移一位。并且, 坑的指针指向right指针所指元素(挖一个新的“坑”)。

在这里,1<4,1填入坑,index指向right所指元素,同时left指针向右移一位:

此时,left左边绿色的区域代表着小于或等于基准元素的区域。

接下来, 切换到left指针进行比较。如果left指针所指的元素 小于等于pivot,那么 left指针继续右移,直到找到一个 比prvot大的元素, left指针停止移动,并 把这个元素填入坑中,同时 right指针左移一位, index指向left指针。

在这里,7>4,所以把7填入坑(index的位置),这时候元素7本来的位置成为了新的坑(index指向left),同时,right向左移动一位:

此时,right右边橙色的区域代表着大于基准元素的区域。

下面按照上述的思路继续排序:

 

8>4,元素位置不变,right左移:

 

2<4,用2来填坑,left右移,切换到left:

 

6>4,用6来填坑,right左移,切换到right:

 

3<4,用3来填坑,left右移,切换到left:

5>4,用5来填坑,right右移。这时候left和right重合在了同一位置:

这时候,把之前的pivot元素,也就是4放到index的位置。此时数列左边的元素都小于或等于4,数列右边的元素都大于4,这一轮交换终告结束。

一轮排序结束,重复上述过程,完成排序。

3.1.1 挖坑法代码

1 /** 2 * 3 * @param arr 待排序的序列 4 * @param left 左指针的位置 5 * @param right 右指针的位置 6 */ 7 public static void qucik_sort(int[] arr,int left,int right) { 8 //递归出口 9 if(left >= right) return; 10 11 //得到基准元素的位置 12 int pivot_index = partition_digHole(arr,left,right); 13 14 //对基准元素的左侧待排序序列进行排序 15 qucik_sort(arr,left,pivot_index - 1); 16 17 //对基准元素的右侧待排序序列进行排序 18 qucik_sort(arr,pivot_index + 1,right); 19 } 20 21 /** 22 * @param arr 待排序的序列 23 * @param left 左指针的位置 24 * @param right 右指针的位置 25 * @return 一轮交换之后基准元素所在位置 26 */ 27 public static int partition_digHole(int[] arr,int left,int right) { 28 int pivot = arr[left]; 29 int index = left; 30 while(right > left) { 31 32 //右指针左移,直到找到小于或等于基准元素的元素 33 while(right > left) { 34 if(arr[right] <= pivot) { 35 arr[index] = arr[right];//把找到的元素填坑 36 index = right;//坑指针指向右指针所指位置 37 left++;//左指针向右移动一位 38 break; 39 } 40 right--;//右指针左移 41 } 42 43 //左指针右移,直到找到大于基准元素的元素 44 while(right > left) { 45 if(arr[left] > pivot) { 46 arr[index] = arr[left];//把找到的元素填坑 47 index = left;//坑指针指向左指针所指位置 48 right--;//右指针向左移动一位 49 break; 50 } 51 left++; 52 } 53 } 54 55 //左右指针重合,跳出循环,重合的位置即为基础元素的位置。本轮排序结束 56 arr[index] = pivot; 57 return index; 58 } 59

3.2 指针交换法

     指针交换法,相对于挖坑法来说,更容易理解,并且元素交换的次数更少:第一次循环,从right指针开始,如果 right指针所指向的元素大于pivot,那么 right指针左移,直到 right指针指向的元素小于或等于pivot, right指针停止移动;切换到left指针,如果 left指针指向的元素小于或等于pivot, left指针左移,直到 left指针指向的元素大于pivot, left指针停止移动。然后把 left和right指针指向的元素互换,并进入第二次循环, 循环往复,直到 left指针和right指针重合,再把 重合的位置的元素与第一个元素互换(因为这里 选取的基准元素是序列的第一个元素,所以与第一个元素互换),本轮排序结束

给定原始数列如下,要求从小到大排序:

 

选定第一个元素为基准元素,取出基准元素的值保存在Pivot中,并且设置两个指针left和right,指向数列的最左和最右两个元素:

在当前数列中,1<4,所以right指针直接停止移动,换到left指针,进行下一步行动:

由于left指针一开始指向的是基准元素,判断肯定相等,所以left右移一位。由于7 > 4,left指针在元素7的位置停下。这时候,我们让left和right指向的元素进行交换:

接下来,我们进入第二次循环,重新切换到right向左移动。right先移动到8,8>4,继续左移。由于2<4,停止在2的位置:

切换到left,6>4,停止在6的位置:

元素6和2交换:

进入第三次循环,right移动到元素3停止,left移动到元素5停止:

元素5和3交换:

进入第四次循环,right移动到元素3停止,这时候请注意,left和right指针已经重合在了一起:

当left和right指针重合之时,我们让Pivot元素和left与right重合点的元素进行交换。此时数列左边的元素都小于或等于4,数列右边的元素都大于4,这一轮交换结束:

一轮排序之后,重复上述过程,完成排序。

3.2.1 指针交换法代码

1 /** 2 * 3 * @param arr 待排序的序列 4 * @param left 左指针的位置 5 * @param right 右指针的位置 6 */ 7 public static void qucik_sort(int[] arr,int left,int right) { 8 //递归出口 9 if(left >= right) return; 10 11 //得到基准元素的位置 12 int pivot_index = partition_needleExc(arr,left,right); 13 14 //对基准元素的左侧待排序序列进行排序 15 qucik_sort(arr,left,pivot_index - 1); 16 17 //对基准元素的右侧待排序序列进行排序 18 qucik_sort(arr,pivot_index + 1,right); 19 } 20 21 22 /** 23 * 24 * @param arr 待排序的序列 25 * @param left 左指针的位置 26 * @param right 右指针的位置 27 * @return 一轮排序之后基准元素所在位置 28 */ 29 public static int partition_needleExc(int[] arr,int left,int right) { 30 //基准元素所在位置 31 int index = left; 32 33 //基准元素的值 34 int pivot = arr[left]; 35 36 //当左、右指针相交则一轮排序结束 37 while(right > left) { 38 39 //右指针左移,直到找到小于或等于pivot的元素,右指针停止移动 40 while(right > left && arr[right] > pivot) { 41 right--; 42 } 43 44 //左指针右移,直到找到大于pivot的元素,左指针停止移动 45 while(right > left && arr[left] <= pivot) { 46 left++; 47 } 48 49 //若左右指针还未相交,则交换此时左右指针所指元素 50 if(right > left) { 51 int temp = arr[left]; 52 arr[left] = arr[right]; 53 arr[right] = temp; 54 } 55 } 56 57 //左右指针相交,本轮排序结束,左右指针重合的位置即为基准元素所在的位置 58 int temp = arr[left]; 59 arr[left] = arr[index]; 60 arr[index] = temp; 61 62 return left; 63 } 64

四、注意点

** 1、为什么挖坑法是从右指针开始移动?**

答:因为本文实现的挖坑法, 基准元素选取的是左指针指向的元素,即最开始挖的坑是左指针指向的元素,所以需要从右指针开始寻找元素填入第一个坑中。

2、为什么指针交换法也是从右指针开始移动?

答:也是因为 选取的基准元素是左指针指向的元素(即第一个元素),指针交换法最后会把左右指针重合位置的元素和基准元素作交换,如果从左指针开始移动,那么会出现左右指针重合时所指向的元素比基准元素大的情况,与基准元素作交换以后,基准元素左边会出现比它大的元素,这显然是不可以的,所以我们要从右指针开始移动,避免出现上述情况。

五、快速排序的时间复杂度和稳定性分析

通过上面对面快速排序的分析,以及对快速排序进行代码实现,可以看出:

快速排序 最好情况下,时间复杂度为: O(nlogn);

快速排序 最坏情况下,时间复杂度为: O(n²);

快速排序的 平均时间复杂度为: O(nlogn);

快速排序的 稳定性: 不稳定;

下一篇:归并排序

代码交流 2021