快速排序算法(思路分析) [数据结构][Java]

快速排序算法(思路分析)

快速排序(QuickSort)是对冒泡排序的一种改进,基本思想是: 通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以使用递归的方式进行,已达到整个数组变成一个有序序列

快速排序和冒泡排序都属于交换排序

快速排序算法示意图:

快速排序的思路分析:

我们定义一个临时变量用来保存待排序部分最左边的位置的下标,再用一个临时变量保存待排序部分最右边的下标,最开始的时候我们的待排序部分就是一整个数组,我们会通过一轮快速排序将其分为两个待排序部分: 我们称之为: 左待排序部分和右待排序部分,对于左待排序部分我们要采取左递归的方式来进行排序,对右待排序部分我们要采取右递归的方式来排序,我们在第一轮排序的时候, 我们用一个l (left首字母)来记录最左边的下标,用一个r来记录最右边的下标, 最左边和最右边的下标还有每次待排序数据都是通过参数传递过来的 ( 但是我们其实只用传递一次,剩下的就交给递归调用即可 )

• 注意: 我们这里讲的快排算法中还要引用一个临时变量pivot ( prvot表示中轴的意思 ) 来记录中间位置的值,我们每次依据中间位置的值进行分割

  • 当引入pivot变量之后会让我们对快速排序可以掌握的更加透彻

  • 我们在开始第一轮选择排序的时候在外层while循环之中我们写一个内层while循环,循环用来实现如果满足 arr[l] < pivot的时候我们让l++ , 因为这个时候其实就是我们的左边的值要比我们的中轴值小, 这个时候l 就要右移,直到找到一个比中间值大的值或者找到中间值为止,然后就停下,对于右边也是一样的, 如果满足 arr[r] > pivot的时候我们就让r–

    • 这个时候注意: 我们判断的是arr[l] < pivot的时候l++,而不是arr[l] <= pivot的时候l++,这个时候是因为什么?

      • 如果我们的arr[l] <=的时候 l++,这个时候如果我们的中轴值之前的所有值都比中轴值小,这个时候我们的l不会停留到中轴位置,而是会一直到右边, 而这个时候如果右边正好有 小于中轴值的元素,这个时候我们的这个小于中轴值的元素按理就要和我们的中轴值左边的元素或者最极限的情况就是和我们的中轴值进行交换,但是这个时候我们的l一直到了中轴值的右边,这个时候交换之后还是错误的,我们的中轴的右边会有比中轴值小的元素 , 按理来说我们的中轴值左边的值都要比中轴值小,而我们的中轴值右边的值都要比我们中轴值大

    • 然后我们l和r移动之后找到了满足交换条件的l之后,这个时候我们又要判断: 判断我们是不是 l >= r了,如果大于或者等于l了,这个时候直接退出, 这个时候由于我们判断条件有l = r的情况,所以: 我们如果退出这个外层for循环之后可能l = r ,这个时候如果l = r 的时候我们接下来如果l = r的情况下进入 左递归和右递归中会无限的递归,这个时候由于无限的调用自己这个方法,就会报一个栈溢出异常

      • 我们在判断了 l发现 l小于 r之后就要进行元素的交换,而交换了元素之后我们也要进行一个判断,我们要判断如果 arr[l] == pivot,那么就让r–, 如果arr[r] == pivot,那么就让l ++

        • 这个时候是为什么?

          • 我们这里首先要知道 arr[l] == arr[r] == pivot的情况分为两种:

            1. arr [l] == arr[r] == pivot 且 l != r
            2. arr [l] == arr[r] == pivot 且 l == r

            • 而对于如果我们是遇到了上面的第1种情况,这个时候就是表示l != r的时候,那么l != r,那么就是陷入了一个死循环,每次都进入不了内层while循环之中,并且l != r, 也就不能通过判断条件退出循环

              • 所以我们就要判断如果 arr[l] == pivot,那么就让r–, 如果arr[r] == pivot,那么就让l ++ , 这个时候为什么 arr[l] == pivot那么就让 r–,而不是让l++?

                • 这个时候其实就是如果是小于pivot的值,或者是大于pivot的值,这个时候我们可以直接交换完元素之后就可以后移,但是我们没有,就是因为如果出现 等于(=) pivot的值,这个时候如果是r 或者 l 其中之一为pivot,那么这个时候一定要注意: 我们等于pivot的l或者r一定不能移动 —> 这个原因我们前面已经说过了(和内层while循环的 arr[l] < pivot的原因是一样的), 但是如果我们遇到了r = l = pivot的时候一定要让r – 并且要让 r++,因为这个时候就是要让我们的r 指向我们的pivot的前一个元素, 让l – ,让我们的l指向我们的pivot的后一个元素