用java实现算法线性时间选择问题,把原来的元素按照五个一组进行排序
时间: 2023-05-28 14:08:11 浏览: 44
算法线性时间选择问题:
算法线性时间选择问题是一个在未排序的n个元素的序列中选出第k小元素的问题。它可以在O(n)的时间复杂度内解决。
代码实现:
public static int linearSelect(int[] arr, int k) {
if (arr.length < k) {
return -1; // 数组元素不足k个,返回-1
}
int left = 0, right = arr.length - 1;
while (left <= right) {
int pivot = partition(arr, left, right);
if (pivot + 1 == k) {
return arr[pivot];
} else if (pivot + 1 < k) {
left = pivot + 1;
} else {
right = pivot - 1;
}
}
return -1; // 没有找到第k小元素,返回-1
}
private static int partition(int[] arr, int left, int right) {
int randomIndex = (int) (Math.random() * (right - left + 1)) + left; // 随机选择一个元素作为枢纽元
int pivot = arr[randomIndex];
swap(arr, randomIndex, right); // 将枢纽元放到数组末尾
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right); // 将枢纽元放到中间
return i + 1; // 返回枢纽元的下标
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
把原来的元素按照五个一组进行排序:
public static void sortFive(int[] arr) {
for (int i = 0; i < arr.length; i += 5) {
insertionSort(arr, i, Math.min(i + 4, arr.length - 1)); // 对每五个元素进行插入排序
}
for (int i = 5; i < arr.length; i++) {
int j = i;
while (j > 0 && arr[j] < arr[j - 5]) { // 对每相邻的五个元素进行归并排序
swap(arr, j, j - 5);
j -= 5;
}
}
}
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int j = i;
while (j > left && arr[j] < arr[j - 1]) { // 对每五个元素进行插入排序
swap(arr, j, j - 1);
j--;
}
}
}
private static void mergeSort(int[] arr, int left, int mid, int right) {
int[] tmp = new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) { // 归并排序
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= right) {
tmp[k++] = arr[j++];
}
for (i = 0; i < tmp.length; i++) { // 将排序后的元素放回原数组
arr[left + i] = tmp[i];
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}