快速排序的java实现

简介

快速排序,看这名字就知道这是一种很快的排序方法,实际上也是如此。快速排序属于分治法的一种,就是说通过把数据分成几部分来同时处理的一种算法。这种算法很重要,所以研发岗的面试经常考。

快速排序的步骤

我们以数组int[]a={7,5,3,2,9,10,8,4,6,1};这个数组为例来说明一下快速排序到底是怎么进行的。

第1步:找基准值

所谓的基准值,顾名思义就是以它为基准进行比大小。通常来说,我们选取数组的第一个数为基准值。在数组a里基准值就是7.

第2步:比大小

先从数组的最右边开始往左边找比基准值小的第一个数,然后从数组的最左边开始往右找比基准值大的第一个数。那么为什么要这么找呢?因为现在我们要把数组从小到大排序,所以要找出比基准值小的数放到基准值的左边,找出比基准值的数放在基准值的右边。
那么在数组a里,从左往右找,第一个比7大的数就是9,我们把它的坐标记为i;从右往左找,第一个比7小的数就是1,我们把它的坐标记为j。

第3步:交换

找到之后,如果这个时候i<j,那么就交换这两个数,因为i=4,j=9,符合条件,将9和1进行交换。现在数组变成了int[]a={7,5,3,2,1,10,8,4,6,9};
如果j>=i,那么不做处理
为什么还要判断i和j的大小呢?就像第二步说的,我们要找出比基准值小的数放到基准值的左边,找出比基准值的数放在基准值的右边。所以如果i<j的话,交换就达到目的了,如果i>=j,比基准值小的数就在基准值的左边,比基准值大的数已经在基准值的右边了,这时候就没必要交换了。

第4步:继续查找

在i<j的前提下,继续向右查找比基准值大的数,往左找比基准值小的数,然后交换。
在我们的例子中,10和6、8和4都符合交换的条件,所以数组就变成了
int[]a={7,5,3,2,1,6,4,8,10,9};这时候i=6,j=7

第5步:交换基准值到合适的位置

当查找继续进行,这时候i=j=6,已经不满足继续查找和交换的条件了,那么我们应该怎么办呢?答案就是把a[6]和基准值交换,因为i=j的时候说明已经到了一个分界线的位置,分界线左边的数比基准值小,分界线右边的数比基准值大,而这个分界线就是我们的基准值,所以把它和a[i]交换,这时候数组就变成:
int[]a={4,5,3,2,1,6,7,8,10,9};

第6步:重复

对基准值左右两边的两个子数组重复前面五个步骤直至排序完成。

复杂度

时间复杂度

从上面的步骤可以看出来快速排序的快慢取决于区域划分的次数,理想情况下是每次都等分,所以划分次数为logn(即log2n),时间复杂度为
T[n] = 2T[n/2] + O(n)其中O(n)为PARTITION()的时间复杂度,对比主定理,

T[n]= aT[n/b]+f (n)

我们的快速排序中:a = 2, b = 2, f(n) = O(n)

最坏的情况就是每次划分之后,一边只有一个元素,另一边有n-1个元素,这样就得划n-1次,这时候时间复杂度为O(n2)

所以平均的时间复杂度为O(nlogn)

空间复杂度

不需要额外的空间,空间复杂度为O(1)

稳定性

快速排序算法的稳定性取决于和基准值交换的那个数的大小,如果它们相等的话,那么稳定性就被破坏了,所以快速排序是一种不稳定的排序方法。

java实现

  public void quickSort(int[]a,int left,int right)
{
    if(left>right)
        return;
    int pivot=a[left];//定义基准值为数组第一个数
    int i=left;
    int j=right;
    
    while(i<j)
  {
     while(pivot<=a[j]&&i<j)//从右往左找比基准值小的数
           j--;
     while(pivot>=a[i]&&i<j)//从左往右找比基准值大的数
           i++;
       if(i<j)                     //如果i<j,交换它们
    {
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
  }
   a[left]=a[i];
   a[i]=pivot;//把基准值放到合适的位置
   quickSort(a,left,i-1);//对左边的子数组进行快速排序
   quickSort(a,i+1,right);//对右边的子数组进行快速排序
}

参考

快速排序
That's all.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,214评论 0 52
  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,742评论 0 15
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,270评论 0 2
  • 我喜欢理性的聪明人 可是面对爱的人 我想感性一次 不想讲那么多的道理。 平安喜乐,勿忘心安
    饼干超人阅读 238评论 0 1
  • 上帝说地球太冰冷所以他创造女人然而并没有什么卵用 有个女生朋友转发了一条微博帖子给我。 讲的是一个渣男如何骗爱骗炮...
    在下张十五阅读 2,338评论 4 5