qsort11

原创
2017/09/21 14:46
阅读数 9

前言

相信很多搞计算机的朋友都听说过一句话:

程序=数据结构+算法

自己的一些体会是,其实出来工作之后,很少会用到太复杂的算法,基本上都是业务逻辑的编写为主。 退一万步来讲,即使有用到,也有相应的工具库帮你实现好,非常方便^_^。 所以,算法这些东西,通常是学了又忘,忘了又学。

算法虽然不会用到,或者说,不用自己实现。但是了解其原理,还是对我们解决问题有帮助,也是编程能力的一种素养吧。

快速排序思路

开篇,先来一发狠的,说说快速排序。 这个是各种排序算法当中,比较常用的吧。看名字就知道它很牛?快速排序,意思就是它的速度非常快,时间复杂度是O(nlogn)。

下面我们一起看看它的算法过程:

0.有一个乱序数组arr 1.选择arr第一个元素arr[0],作为基准元素x,并在数组的头尾设置两个指针i, j 2.首先看j, j不断往前移动(j--), 直到找到第一个比x小的元素,交换i和j的位置,i向后移动(i++) 3.然后,再看i,i不断往后移动(i++), 直到找到第一个比x大的元素,交换i和j的位置,j向前移动(j--) 4.重复2和3,直到i和j重合(i == j) 5.此时,i的位置就是基准元素x的位置了 6.然后,再将i的前后两部分,再执行一次1,2,3,4,5的流程。直到不能再执行

例子

下面我们用一个例子,来看看一趟快排的执行过程

我们假设,有数组 a = [27, 31, 15, 28, 43, 15, 04]

Alt text

然后,只要把i前面,和j后面的两组元素,分别再执行快速排序流程,直到不能再执行(i > j),此时数组a就是一个有序数组了。

从上面的过程,我们可以发现,快速排序,使用了分治法的思想,分而治之。把一个数组分成两部分,再分别进行排序。

实现

有同学要喷了?你bibi了这么多?代码写了多少? Ok. Talk is cheap, Show me the Code.

附上java版代码实现

    public static void qsort(int[] a, int l, int r){         if(l >= r){             return;         }                  int x = a[l];         int i = l;         int j = r;                  while(i < j){             while(i < j && a[j] >= x){                 j--;             }             if(i < j){                 a[i++] = a[j];             }                          while(i < j && a[i] <= x){                 i++;             }             if(i < j){                 a[j--] = a[i];             }         }                  a[i] = x;                  if(l < i - 1){             qsort(a, l, i - 1);         }         if(j + 1 < r){             qsort(a, j + 1, r);         }     }

由睿江云运维人员提供,想了解更多,请登陆www.eflycloud.com

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部