【简单算法】快速排序-Java版


快排的思想是:要求时间最快时。

    选择第一个数为p,小于p的数放在左边,大于p的数放在右边。

    递归的将p左边和右边的数都按照第一步进行,直到不能递归。

public static 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);//对右边的子数组进行快速排序
}

代码有很多种,但是就单是这样看代码,是很不容易看懂的,网上有很多这类说法,大的放右边,小的放左边,实际上,很多人的基准值都是第一个,这样读起来,就很不好理解代码逻辑了,所以我来复现下实际执行步骤

有一组数:

7,0,8,3,2,3,5,2,9 a,最大的while循环第一遍 第一个为基准值为7, i=2,j=7 内部交换
7,0,2,3,2,3,5,8,9 b,最大的while循环第二遍 右往左找到比基准值小的 即 j=6时,这时候从左往右找最后一个比基准值大的 因为没有所有i=6时停止,
                        如果有,重复上一步,直到i>=j停止。此时将基准值与最后比基准值小的数交换;
5,0,2,3,2,3,7,8,9 c,接下来递归左边此时递归的参数为 0 ,6-1,所以只处理  5,0,2,3,2,3 这部分
5,0,2,3,2,3,7,8,9 d,因为先从右到左遍历,j找到的小值为最后一个j=5,即a[j]=3,i无法找到大的所以在i=5时停止 无法交换,跳出大循环交换
3,0,2,3,2,5,7,8,9 第三次左边递归 3,0,2,3,2,重复c,d,因为从左到右可以找到一个不比基准值小的数,所以得
3,0,2,2,3,5,7,8,9 第四次左边递归 3,0,2,2 此时无内部替换 
2,0,2,3,3,5,7,8,9 第五次左边递归 2,0,2,此时无内部替换
0,2,2,3,3,5,7,8,9 此时i=1 ,右边递归,但是事实上以及排序完成,所以右边递归大多数是自己和自己交换,可以忽略,递归完就完成了排序

因为文字不定可以看清晰,所以网上找了一个符合我的这份代码的图,有些人的图,真不知道他在做什么,

28.jpg

放上图片地址:http://blog.csdn.net/vast_sea/article/details/8113422

说不定,看他的比我这份要清晰。

 

上面我也是一路debug下来得到的,至于右边递归部分,就像是一种保证一样,避免出错。数据小,所以右边没递归就排完了

另外快排的时间复杂度 平均为:,最坏为:

你也可以看维基百科了解相关资料:快速排序

 

 

声明:TIL|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA[ZH]协议进行授权

转载:转载请注明原文链接 - 【简单算法】快速排序-Java版


Life is very interesting. In the end, some of your greatest pains become your greatest strengths.