快速排序

时间复杂度分析

最好的情况

注意：划分的时候我们忽略了-1操作，本来应该划分为n/2,n/2-1，我们简化成n/2,n/2,并且我们假定n/2都是整数
令数组A[n],最好的情况是，每一轮都可以做到等分数组,左边A[n/2]，右边A[n/2],以此类推......

令层数为k，有1*2^k-1 = n,则k = ，每层的和都是n，所以遍历的总次数为n

平均情况

快速排序的平均请接近于最好情况，而不是最坏情况
例如，加入划分算法总是按照9：1的情况划分，此时，我们得到的快速排序的时间复杂度的递归公式为
T(n) = T(9n/10)+T(n/10)+cn
图示如下

从图示我们看到时间复杂度应该为cn*
对对数进行换底，底数变为2，并且省去常数项变为n
令c1，c2为常数，由换底公式可以推导出,属于同一时间复杂度，所以只要划分是按照常数比例的，那么快排的时间复杂度都为n

最坏的情况

快速排序退化成冒泡排序，时间复杂度为

code

void quickSort(int a[],int left,int right) {
    if (left >= right) {
        return;
    }
    int k = a[left];
    int i = left;
    int j = right;
    
    while (i < j) {
        //从右向左
        while (i < j) {
            if (k > a[j]) {
                int tmp = a[j];
                a[j] = a[I];
                a[i] = tmp;
                break;
            } else {
                j--;
            }
        }
        
        //从左向右
        while (i < j) {
            if (a[i] <= k) {
                i++;
            } else {
                int tmp = a[j];
                a[j] = a[I];
                a[i] = tmp;
                break;
            }
        }
        
    }
    quickSort(a,left,i -1);
    quickSort(a,i+1,right);
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
        int len = (int) sizeof(arr) / sizeof(*arr);
        quickSort(arr,0,len-1);
        for (int i = 0; i< len; i++) {
            printf("%d,",arr[i]);
        }
    }
    return 0;
}

console

0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,Program ended with exit code: 0