创建一个14个长的数组,插入13个随机数,要求查找固定数值的位置。方法要求java生成随机数组,然后用快速排序再用折半查找法
时间: 2024-03-26 10:39:58 浏览: 90
好的,我可以帮你解决这个问题。首先,我会介绍一下快速排序和折半查找法的原理和实现,然后给出Java代码。
快速排序是一种基于比较的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后再分别对这两部分记录继续进行排序,以达到整个序列有序的目的。快速排序的时间复杂度为O(nlogn)。
折半查找法是一种在有序数组中查找指定元素的算法。它的基本思想是将数组分成两部分,如果要查找的元素比中间元素小,则在左半部分继续查找;如果要查找的元素比中间元素大,则在右半部分继续查找;如果要查找的元素等于中间元素,则返回中间元素的位置。折半查找法的时间复杂度为O(logn)。
下面是Java代码实现:
```java
import java.util.Arrays;
import java.util.Random;
public class QuickSortAndBinarySearch {
public static void main(String[] args) {
int[] arr = generateRandomArray(14);
System.out.println("Original array: " + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: " + Arrays.toString(arr));
int target = 5; // 要查找的数值
int index = binarySearch(arr, target);
if (index == -1) {
System.out.println("The target value does not exist in the array.");
} else {
System.out.println("The target value is at index " + index + " in the array.");
}
}
// 生成指定长度的随机数组
public static int[] generateRandomArray(int length) {
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length - 1; i++) {
arr[i] = random.nextInt(100);
}
return arr;
}
// 快速排序
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
// 快速排序的划分函数
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}
// 折半查找法
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
```
这段代码会生成一个长度为14的随机数组,然后使用快速排序将其排序,最后使用折半查找法查找指定数值的位置。你可以根据需要修改代码中的目标数值和数组长度。
阅读全文