在计算机科学中,快速选择(Quickselect)是一种从无序列表找到第 k 小元素的选择算法。它从原理上来说与快速排序有关。与快速排序一样都由托尼·霍尔提出的,因而也被称为霍尔选择算法。同样地,它在实际应用是一种高效的算法,具有很好的平均时间复杂度,然而最坏时间复杂度则不理想。快速选择及其变种是实际应用中最常使用的高效选择算法。
voidswap(int *arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
/** * 对给定的数组区间进行划分 * @param arr 数组 * @param left 区间下限,包含arr[left] * @param right 区间上限,包含arr[right] * @return 返回划分后,划分基准的索引 */ intpartition(int *arr, int left, int right){ int j = left - 1; for (int i = left; i < right; i++) { //以arr[right]作为划分基准 if (arr[i] <= arr[right]) swap(arr, i, ++j); } swap(arr, ++j, right); return j; }
/** * 查找第k小元素 * @param arr 无序数组 * @param n 数组长度 * @param k 目标第k小 * @return 成功:返回第k小元素的索引 * 失败:返回-1 */ intquickSelect(int *arr, int n, int k){ int left = 0, right = n - 1; while (left <= right) { int idx = partition(arr, left, right); if ((k - 1) == idx) return idx; if ((k - 1) > idx) left = idx + 1; else right = idx - 1; } return-1; }
intpartition(int *arr, int left, int right){ int base = arr[left]; //以arr[left]作为划分基准 while (left < right) { while (left < right && arr[right] >= base) right--; arr[left] = arr[right]; while (left < right && arr[left] <= base) left++; arr[right] = arr[left]; } arr[left] = base; return left; }
intquickSelect(int *arr, int n, int k){ int left = 0, right = n - 1; while (left <= right) { int idx = partition(arr, left, right); if ((k - 1) == idx) return idx; if ((k - 1) > idx) left = idx + 1; else right = idx - 1; } return-1; }
voidswap(int *arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
intpartition(int *arr, int left, int right){ int j = left - 1; for (int i = left; i < right; i++) { if (arr[i] <= arr[right]) swap(arr, i, ++j); } swap(arr, ++j, right); return j; }
intquickSelect(int *arr, int left, int right, int k){ if (left <= right) { int idx = partition(arr, left, right); if ((k - 1) == idx) return idx; if ((k - 1) > idx) return quickSelect(arr, idx + 1, right, k); elsereturn quickSelect(arr, left, idx - 1, k); } return-1; }
/** * 查找第k小元素 * @param arr 无序数组 * @param k 目标第k小 * @return 成功:返回第k小元素的索引 * 失败:返回-1 */ publicstaticintquickSelect(int[] arr, int k){ int left = 0, right = arr.length - 1, idx; while (left <= right) { idx = partition(arr, left, right); if ((k - 1) == idx) return idx; elseif ((k - 1) > idx) left = idx + 1; else right = idx - 1; } return -1; }
/** * 对给定的数组区间进行划分 * @param arr 数组 * @param left 区间下限,包含arr[left] * @param right 区间上限,包含arr[right] * @return 返回划分后,划分基准的索引 */ privatestaticintpartition(int[] arr, int left, int right){ int j = left - 1; for (int i = left; i < right; i++) { if (arr[i] <= arr[right]) swap(arr, i, ++j); } swap(arr, ++j, right); return j; }
privatestaticvoidswap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }