《iOS面试题整理》- 快速排序

思路

快排利用的是分治的思想, 排序数组中下标 p 到 r 之间的一组数据, 选择 p 到 r 之间的任意一个数据作为 pivot(分区点), 遍历 p 到 r 之间的数据, 将小于 pivot 的放到左边, 大于 pivot 的放到右边, 将 pivot 放到中间。
经过上述操作后, p 到 r 之间的数据被分成了三个部分, p 到 q - 1 之间都是小于 pivot , 中间是 pivot , 后面 q + 1 到 r 之间是大于 pivot的

时间复杂度

快速排序是原地、不稳定的排序算法, O(nlogn)

如果数组中的数据原来已经是有序的了, 例如从小到大排列, 并且选择最后一个元素为分区点, 这样每次分区之后得到的两个区间都是不均等的, 需要进行大量的 n 次分区操作, 这种情况时间复杂度退化为 O(n^2)

实现

 - (void)quickSort:(int *)a start:(int)start size:(int)size {
    [self quickSort:a start:start end:size - 1];
}

- (void)quickSort:(int *)a start:(int)start end:(int)end {
    if (start >= end) return;
    int index = [self partition:a start:start end:end];
    [self quickSort:a start:start end:index -1];
    [self quickSort:a start:index + 1 end:end];
}
- (int)partition:(int *)a start:(int)start end:(int)end {
    if (start >= end) return start;
    int i = start;
    int j = end;
    int pivot = a[start];
    while (i < j) {
        while (i < j && a[j] >= pivot) {
            j--;
        }
        a[i] = a[j];
        
        while (i < j && a[i] <= pivot) {
            i++;
        }
        
        a[j] = a[i];
    }
    
    a[i] = pivot;
    return i;
}

- (void)dump:(int *)a size:(int)size {
    int idx;
    
    for (idx = 0; idx < size; idx++)
        printf("d\n", a[idx]);
}

  // 测试
    int a[6] = {2,5,1,5,4,9};
    QuickSort *sort = [[QuickSort alloc] init];
    [sort quickSort:a start:0 size:6];
    [sort dump:a size:6];

另一种分区方法, 每次都从未处理区间中取一个元素, 如果小于pivot , 则插入已处理区间

  - (int)partition:(int *)a start:(int)start end:(int)end {
    int pivot = a[end];
    int i = start;
    int j = i;
    for (; j <end; j ++) {
        if(a[j] < pivot ) {
            if (i != j) {
                [self swap:a + i b:a +j];
            }
            i++;
        }
    }
    [self swap:a+i b:a+end];
    return i;
}

- (void)swap:(int *)a b:(int *)b{
    int temp = *a;
    *a = *b;
    *b = temp;
}

练习

1. 无序数组中的第 K 大元素, O(n) 时间复杂度

思路: 最后一个数作为 pivot, 进行分区 , a[0.. p -1], a[p], a[p+1.. n], 如果 p + 1 = K， 则 a[p] 就是目标元素, 如果p + 1 < K, 说明目标元素在 a[p + 1.. n] 中, 如果 p + 1 > k, 说明目标元素在a[0.. p-1]中

- (void)lagerstK {
    int a[] = {6,5,7,8,1,2};
    
    int result = [self findLargest:a left:0 right:5 k:2];
    NSLog(@"%d",result);
}

- (int)findLargest:(int *)a left:(int)left right:(int)right k:(int)k {
    QuickSort *sort = [[QuickSort alloc] init];
    int index = [sort partition:a start:left end:right];  // 分区
    if (index > k - 1) {
        return [self findLargest:a left:left right:index - 1 k:k];
    } else if (index < k - 1) {
        return [self findLargest:a left:index + 1 right:right k:k];
    }
    return a[index];
}