使用Java实现算法：快速排序、二分查找等实例展示

原创逃离我推掉我的手 2024-09-20 13:12 20阅读 0赞

以下是使用Java实现的快速排序和二分查找两种常见算法的实例：

1. 快速排序：
```java
public class QuickSort {
    // 定义分区函数，将数组分为两部分
    public int partition(int[] arr, int low, int high) {
        // 选择一个基准元素
        int pivot = arr[high];
        
        // 设定两个指针，一个比基准小，一个比基准大
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
            // 如果当前元素小于或等于基准，则交换它们的位置
            if (arr[j] <= pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        
        // 返回基准元素的索引，这里即为分区后的基准位置
        return i + 1;
    }

// 快速排序的主方法
    public 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);
        }
    }

public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 7};
        int low = 0;
        int high = arr.length - 1;

System.out.println("Original Array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }

QuickSort quickSort = new QuickSort();
        quickSort.quickSort(arr, low, high);
        
        System.out.println("\nSorted Array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
```
2. 二分查找（Binary Search）：
```java
public class BinarySearch {
    // 二分查找函数，参数是已排序的数组和要查找的目标值
    public int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

while (low <= high) {
            int mid = (low + high) / 2;

// 如果找到目标元素，返回其索引
            if (arr[mid] == target) {
                return mid;
            }
            
            // 如果目标元素小于中间元素，则将搜索范围设置为中间元素的左边
            if (target < arr[mid]) {
                high = mid - 1;
            }
            
            // 如果目标元素大于中间元素，则将搜索范围设置为中间元素的右边
            else if (target > arr[mid]) {
                low = mid + 1;
            }
        }

// 如果没有找到目标元素，返回-1
        return -1;
    }

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int target = 4;

int index = binarySearch(arr, target);

if (index != -1) {
            System.out.println("Element " + target + " found at index: " + index);
        } else {
            System.out.println("Element " + target + " not found in the array.");
        }
    }
}
```
这段代码首先定义了二分查找的函数`binarySearch`。然后在`main`方法中创建了一个数组和一个要查找的目标值，最后调用`binarySearch`函数并打印结果。