首页 > 代码库 > POJ 2388 Who's in the Middle 快排解法
POJ 2388 Who's in the Middle 快排解法
又是一题快速排序的题目,活用快排求某个位置的数。
这次完善一下自己的基础,把快排代码规范化和增加一个random算法,进一步确保不会出现最坏情况。
思路和前一道题差不多,不过是求第k个数了,这里的第k个数是中序数。
花了点时候整理下代码,果然变得十分工整了。
#include <cstdio> #include <stdlib.h> #include <algorithm> #include <time.h> using namespace std; const int SIZE = 10000; int arr[SIZE]; int partition(int *arr, int low, int up) { for (int j = low; j < up; j++) if (arr[j] < arr[up]) swap(arr[low++], arr[j]); swap(arr[low], arr[up]); return low; } int selectK_1(int *arr, int low, int up, int k) { int r = rand() % (up - low + 1) + low; swap(arr[r], arr[up]); int m = partition(arr, low, up); int lowerParts = m - low + 1; if (lowerParts == k) return arr[m]; if (k < lowerParts) return selectK_1(arr, low, m-1, k); return selectK_1(arr, m+1, up, k - lowerParts); } int main() { srand((int)time(NULL)); int N; while (~scanf("%d", &N)) { for (int i = 0; i < N; i++) { scanf("%d", &arr[i]); } printf("%d\n", selectK_1(arr, 0, N-1, (N>>1)+1)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。