数组里最小的k个元素&&快排
这个题目之前在看数据结构和算法分析的时候见过，其实解法也挺多的。
-
排序后找出前k个元素
快排O(NlogN)，然后O（K)，总的复杂度为O(NlogN) -
创建一个长度为k的容器，然后不断地维护更新，这样的话，每次都要：
1，将当前的k个元素中的最大者与当前遍历的元素比较
2，若当前的元素更小，则需要替换这个值
3，若有上一步的话，将新的数组排序
据说用二叉树的话复杂度为O(logK)。。
然后遍历n-k的元素
总的复杂度为O(Nlog(k)）
- 和快速排序一样，我们改造一下得到快速选择
quickSelect
首先大家如果不太熟悉快排，可以去看一下。
这里我们要打印的元素只是前k个，因此我们把快排的算法改进一下
快排：
void quick_sort(int* a, int left, int right)
{
int i, j;
int pivot;
if (left + 3<= right)
{
//pivot = Median3(a, left, right);
pivot = get_pivot(a, left, right);//error1
i = left;
j = right - 1;
for (;;)
{
while (a[++i] < pivot){}
while (a[--j] > pivot){}
if (i < j)
swap(&a[i], &a[j]);
else
break;
}
swap(&a[i], &a[right - 1]);
quick_sort(a, left, i - 1);
quick_sort(a, i + 1, right);
}
else
InsertionSort(a + left, right - left + 1);
}
特别要提到的是
if (left + 3<= right)这里加上了一个cutoff量
我试了一下，如果这个值是0，1，2的话，会出错
大家可以宏定义一个cutoff，然后自己设置值，这一点呢，我猜是为了防止越界的时候出现问题，交给插入排序来做
其中pivot的程序：
//不仅是找到中位数，而且为了方便要把pivot移动到最右边（hide），这样就不用去处理这个元素了
//技巧：找中位数不要局限在比较大小，这样很麻烦的，可以通过swap快速达到效果
int get_pivot(int*arr, int beg, int end)
{
int middle = (beg + end) / 2; //change2
if (arr[middle] < arr[beg])
swap(&arr[middle], &arr[beg]);
if (arr[end] < arr[beg])
swap(&arr[beg], &arr[end]);
if (arr[middle]>arr[end])
swap(&arr[middle], &arr[end]);
//hide pivot
swap(&arr[middle], &arr[end - 1]);//we don't need to deal with arr[end],but it's ok if you do
return arr[end - 1];
}
swap：
void swap(int* a, int *b) { int tmp = *a; *a = *b; *b = tmp; }
快排里面，
quick_select(arr,beg,i-1); quick_select(arr,i+1,end);
这一句可以改进而使quickselect更快速，快排的复杂度为O(N*logN),而下面的算法则可以达到O(N)!
.
因为我们只需要保证前k个元素是最小的；而我们每次调用，都保证了pivot前面的元素不大于pivot && pivot后面的元素不小于pivot
我们有一个下标 i 来记录pivot的位置，所以我们可以判断k与i的关系来决定对那一部分继续进行递归：
1，如果k小于i，那么只需要对前面的i个进行递归调用
2，如果k等于i+1，说明刚好有k个元素，直接打印
3，如果k大于i，那么前i个元素就不需要管理，处理后面的一部分
如下：
//quickSelect:
//attention that Kth value in array is arr[k-1]
if (k < i)
quick_select(arr, beg, i - 1, k);
else
if (k>i + 1)
quick_select(arr, i + 1, end, k);
//如果k比中间要长，那么 i 之前的都不需要管了，只需要看后面的部分
//所以我们看见，quickSelect只需要对一边进行递归，所以，复杂度会低于quicksort
以上是quickSort，接下来是select：
函数的本身并没有什么变化，只是改动了上面提到的两句递归部分：
/*if (k - 1 == i) //it seems that it dosen't matter
return;
else*/
if (k < i)
quick_select(arr, beg, i - 1, k);
else
if (k>i + 1)
quick_select(arr, i + 1, end, k);
*不过我试了一下，第一种情况k - 1 == i可以注释掉。。
void quick_select(int* arr, int beg, int end, int k)
{
int pivot;
int i, j;
if (beg +2 <= end)//<= matters
{
pivot = get_pivot(arr, beg, end);
i = beg;
j = end - 1;//it is okay to be j=end
while (1)
{
while (arr[++i] < pivot);//it doesn't matter wether it is "++i" or "i++"
while (arr[--j] > pivot);
if (i < j)
swap(&arr[i], &arr[j]);
else break;
}
swap(&arr[i], &arr[end - 1]);//since you hide, restore here
//follow the quickSort :
//quick_select(arr, beg, i - 1, k);
//quick_select(arr, i + 1, end, k);
//quickSelect:
//attention that Kth value in array is arr[k-1]
if (k - 1 == i)
return;
else if (k < i)
quick_select(arr, beg, i - 1, k);
else
if (k>i + 1)
quick_select(arr, i + 1, end, k);
//如果k比中间要长，那么 i 之前的都不需要管了，只需要看后面的部分
//所以我们看见，quickSelect只需要对一边进行递归，所以，复杂度会低于quicksort
}
else
InsertionSort(arr + beg, end - beg + 1);
}
我用例子试了一下是没有问题的：
int a[] = { 5, 3, 8, 99, 10, 2, 4, 7, 1, 22 };
quick_select(a, 0, 9, 6);
//Qsort(a, 0, 9);
//quick_sort(a, 0, 9);
for (int i = 0; i < 10; i++)
std::cout << a[i] << " ";
补充
我在做这道题的时候在网上搜索过，还有一种题目是让你输出第k个元素。。在以上程序中稍稍改进，加入返回的值然后输出
像这样就可以了：
if (k - 1 == i)
return arr[i];
else if (k < i)
return quick_select_k(arr, beg, i - 1, k);
else
if (k>i + 1)
return quick_select_k(arr, i + 1, end, k);
- 记录一下我遇到的坑：
在写get_pivot()的时候，我最开始是这样写的：
//int middle = arr[(beg + end) / 2]; //change2
//if (middle < arr[beg])
// swap(&middle, &arr[beg]);
//if (arr[end] < arr[beg])
// swap(&arr[beg], &arr[end]);
//if (middle>arr[end])
// swap(&middle, &arr[end]);
//swap(&middle, &arr[end - 1]);
//beg<middle<end
第一行就出错了啊！
int middle = arr[(beg + end) / 2];
我tm调试了一两个小时才找到这个问题啊！一直以为我算法错了啊！
这里在数组里面用除法，似乎是有问题的！
update:
上stackoverflow问了一下发现果然很sb啊！
我那种错误的写法根本没有达到交换的效果，只是把middle这个值赋给了数组里面的一个元素！
学习了！
