快速排序,如果想搞清楚快速排序,主要是为了应付简单的习题,比如选择,填空之类的。可以看这个,如果想深入理解,并想掌握代码书写,请移步到:https://www.jianshu.com/p/8f9beb0d28d8
快速排序说白了就是,以一个关键字为基准,比较其他元素与之的大小,然后进行有选择的交换。
废话不多说,上例子。
60 80 55 40 42 85
首先,我们应以60为基准,为什么呢,一般都是把第一个元素当做基准。准备两个指针变量i,j。
i 指向 最左端,j 指向最右端。如下
60 80 55 40 42 85
i j
比较60和85,因为60小于85,且85在60后面,所以不用交换,并且 j 向右移动一位。
60 80 55 40 42 85
i j
继续看60和42,60大于42,且42在60后面,交换位置,并且 i 向后移动一位。结果如下,
42 80 55 40 60 85
i j
继续看80和60,80大于60,且在60前面,交换位置,j向右移动一位。
42 60 55 40 80 85
i j
继续看60和40 , 60大于40,且40 在60 的后面,故交换位置,i 向后移动一位。
42 40 55 60 80 85
i j
看55和60,不用交换,i 向后移一位,此时 i j 重合,第一趟排序结束。
然后进行第二趟排序,以42 为基准,方法如上,直至排成有序数组。