QuickSort and QuickSelect

作者 Lucyyang 日期 2020-03-31
QuickSort and QuickSelect

稍微吐个槽,写这个文章的起因是的这样的:我一直以为我是会quicksort的,然后面字节跳动的时候,我也明白面试题目做法要用quicksort。在写partition的时候,面试官打断了我:哎,你这个写法不太对啊?我当时也有点懵,和他解释了我这种做法先把pivot移到最右方便处理,然后不断把比pivot小的数移到左边,最后再把pivot移到相应位置,但面试官好像一直没反应过来。然后他让我重新写个交换smaller和larger的做法,结果我一时慌张,重新开了个中间数组存储,之后就理所应当被diss了下QAQ。最后时间也就这样没了,回来哭诉了一番觉得自己挂了,不过后面接到HR电话感觉好像还好?今天重新想了下这个问题,感觉自己现场的写法好像没错啊(不知道细节是否有问题),但是还是自己不够熟悉吧,因此把quicksort和quickselect总结在此。

QuickSort

先总结下快排的逻辑框架:从无序数组中随机选中一个数作为pivot,将比pivot小的数放在pivot左边,比pivot大的数放在pivot的右边,这样我们完成了一次分割。接着分别对pivot左边的数做同样的处理,右边的数也做同样的处理...,如此循环下去,直至整个数组都有序。逻辑框架如下:

void quickSort(vector<int> array, int low, int high)
{
if (low < high) //注意进行判断
{
/* pi为返回的pivot的位置 */
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
// 完成选中pivot,并将数组按照pivot的大小进行左右分割,返回pivot的位置
int partition(vector<int> array, int low, int high){}

那么我和面试官的写法不同之处在于Partition中如何处理数组array了。我的想法是,将随机选中的pivot先放在array末尾方便处理,用于标示置换位置的pos从low出发,i从low开始遍历,当发现array[i] > array[pivot]时,我们swap(array[i], array[pos]),这样就将小的数放在了左边。之后pos++,i继续前进进行遍历。最后我们的pos停在的位置和pivot进行一次交换,这样pivot恰好把数组分成了左边小,右边大的形式。

//实参传递进行交换
void swap(int* a, int* b) {
int tmp = b;
b = a;
a = tmp;
}
int partition(vector<int>& array, int left, int right){
int pivot = right;
int pos = left;
for(int i = left; i < right; i++){
if(array[i] < array[pivot]){
swap(&array[pos], &array[i]);
pos++;
}
}
swap(&array[pos], &array[pivot]);
return pos;
}

那么面试官的想法则是,partition中用两个指针分别从左右两端出发,当左指针发现比pivot大的数,右指针发现比pivot小的数时进行一次交换。

//这里的swap采用cpp内置函数
int partition(vector<int>& array, int left, int right){
int l = left;
int r = right - 1;
int pivot = right;
while(l < r){
while(l<r && l<right && array[l] < array[pivot])
l++;
while(l<r && r>=left && array[r] > array[pivot])
r--;
swap(array[l], array[r]);
}
//最后l=r停在了最后交换完的后一个值上,直接与pivot进行交换即可
swap(array[l], array[pivot]);
return l;
}

此外注意下,cpp中swap函数已经内置好了,无需重新再写。

QuickSelect

QuickSelect是用于找出无序数组中任意第k小的元素,整体逻辑和quicksort类似,唯一不同的是,当我们进行分割后只需处理target所在的区间即可。

int partition(int arr[], int l, int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++) {
if (arr[j] <= x) {
swap(arr[i], arr[j]);
i++;
}
}
swap(arr[i], arr[r]);
return i;
}
int kthSmallest(int arr[], int l, int r, int k)
{
// If k is smaller than number of
// elements in array
if (k > 0 && k <= r - l + 1) {
int index = partition(arr, l, r);
// If position is same as k
if (index - l == k - 1)
return arr[index];
else if (index - l > k - 1)
return kthSmallest(arr, l, index - 1, k);
else
return kthSmallest(arr, index + 1, r, k - index + l - 1);
}
return INT_MAX;
}