无分区函数的java快速排序，以及最坏和最佳情况下的复杂性

Question

这是我在没有分区函数的情况下快速排序的代码，我试图找出最坏和最好情况的复杂性。你们谁能帮我解释一下它是如何一个循环一个循环或者一步一步地工作的

public static void quickSort(int a[], int first, int last)
{
    int start=first,end=last;
    int mid= (first+last)/2;
    int temp;
    while(start<=end)
    {
        while(a[start]<a[mid])
        {
            start=start+1;
        }
        while(a[end]>a[mid])
        {
            end=end-1;
        }
        if(start<=end)
        {
            temp=a[start];
            a[start]=a[end];
            a[end]=temp;
            start++;
            end--;
        }
    }
    if(first<end)
    {
        quickSort(a,first,end);
    }
    if(start<last)
    {
        quickSort(a,start,last);
    }
}

Answer 1

您的实现是正确的。外部while循环对整个数组迭代一次，因此它具有线性时间复杂度。对于外部while循环的整个迭代，这两个内部循环恰好一次遍历数组的每个元素，因此外部while循环的总体时间复杂度为O（n）

对快速排序函数的调用与标准函数中的调用相同，只是将它们与分区放在同一个函数中

所以，代码的总体时间复杂度和标准快速排序算法相同。（O（nlogn）表示平均情况，O（n2）表示最坏情况）

对样本阵列进行试运行

考虑数组1,7、8、9、6、4、5、2、3、10 现在first=start=0，last=end=9，mid=4

迭代1： 自启动以来<=结束，我们先进入内部，然后循环 现在我们从开始递增，直到它小于中间元素。 因为a[mid]=6，所以我们可以从1开始递增，因为下一个元素是7，它大于6，并且退出第一个内部循环。 现在我们对第二个内循环重复相同的过程 我们将end减少1，因为3小于6并退出第二个内环。 现在我们交换7和3，增加开始和减少结束

新阵列：1,3,8,9,6,4,5,2,7,10

迭代2： 开始指向8，结束指向2 因为start大于middle元素，end小于middle元素，所以我们不进入内部循环并交换start和end。 增加开始和减少结束

新阵列：1,3,2,9,6,4,5,8,7,10

迭代3： 开始指向9，结束指向5 因为start大于middle元素，end小于middle元素，所以我们不进入内部循环并交换start和end。 增加开始和减少结束

新阵列：1,3,2,5,6,4,9,8,7,10

迭代4： 开始指向6，结束指向4 因为start大于middle元素，end小于middle元素，所以我们不进入内部循环并交换start和end。 增加开始和减少结束

新阵列：1,3,2,5,4,6,9,8,7,10

迭代5： 开始指向6，结束指向4 因为开始大于结束，所以我们在这里退出

现在您可以看到，我们迭代了外部循环5次，但是对于内部循环，我们只迭代了总共1次，每次都小于n（=10）

现在您可以自己试运行此阵列，以便更好地理解它。 1,2,3,4,6,5,7,8,9,10.