能否为我提供一个使用Java编写的快速排序算法示例?同时,请详细解释其实现逻辑。此外,假设我们有一个包含15个按升序排列的整数数组,当用户输入一个数时,如何利用二分查找法确定这个数在数组中的索引位置,如果没有找到则输出'无此数'。
时间: 2024-11-03 08:23:21 浏览: 23
当然可以,这里是一个简单的Java实现的快速排序算法:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找到分割点
int pivotIndex = partition(arr, low, high);
// 对分割点两侧的子数组递归地进行快速排序
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 最后一个元素作为基准
int i = low - 1; // 小于基准的元素指针
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) { // 当前元素小于或等于基准
i++; // 移动i
swap(arr, i, j); // 交换元素
}
}
swap(arr, i + 1, high); // 将基准放回原位
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
快速排序的主要逻辑是选择一个基准值,通过一趟排序将待排记录分隔成独立的两部分,其中一部分的所有记录的关键字均比另一部分的关键字小,然后分别对这两部分继续进行排序,以达到整个序列有序。
对于二分查找在给定数组中寻找特定数字的索引位置,你可以这样做:
```java
public class BinarySearch {
public static int binarySearch(int[] sortedArray, int target) {
int left = 0;
int right = sortedArray.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (sortedArray[mid] == target)
return mid; // 找到了目标数,返回索引
else if (sortedArray[mid] < target)
left = mid + 1; // 目标在右侧,缩小左侧区间
else
right = mid - 1; // 目标在左侧,缩小右侧区间
}
return -1; // 没有找到目标数,返回-1表示"无此数"
}
}
```
用户输入一个数后,调用 `binarySearch(sortedArray, userInput)` 方法即可得到结果。如果返回值为正数,那就是索引;否则,输出 '无此数'。
阅读全文