桶排序占用空间太大?快速排序太慢?有没有更好的排序算法呢?答案肯定是有的。
它就是快速排序。
快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。
快速排序典型的用到了分治算法,至于分治算法是什么以后再为大家来介绍。
学懂快速排序只需要三步:
先从数列中取出一个数作为基准数;
分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边;
再对左右区间重复第二步,直到各区间只有一个数;
我们来规定一下基准数,在这里我们把待排序数列的第一个数字当做基准数。
我们可以写一个双指针扫描。左指针找大于基准数的数字,右指针找小于基准数的数字,如果右指针指向元素的下标大于左指针指向元素的小标,那么就交换元素。再把基准数交换到分界处,然后把这段数分成两段,一段是[头,基准数],另一段是[基准数+1,尾]。
可以上代码了
联系客服