抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

快速排序-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下来得到的,至于右边递归部分,就像是一种保证一样,避免出错。数据小,所以右边没递归就排完了

另外快排的时间复杂度

平均为:

{\displaystyle O(n\log n)}

最坏为:

O(n^{2})

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


0条评论

发表评论