Java常用算法分类介绍与示例

柔光的暖阳◎ 2024-03-22 15:02 10阅读 0赞

### 一、排序算法 ###

排序算法用于将一组元素按照特定顺序进行排列。

#### 1. 冒泡排序（Bubble Sort） ####

冒泡排序是一种简单的排序算法，它依次比较相邻的元素，并交换它们的位置，使得最大（或最小）的元素逐渐“冒泡”到数组的末尾。

示例代码：

public class BubbleSort {
        
        public static void bubbleSort(int[] arr) {
        
            int n = arr.length;
            for (int i = 0; i < n - 1; i++) {
        
                for (int j = 0; j < n - i - 1; j++) {
        
                    if (arr[j] > arr[j + 1]) {
        
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
    }

#### 2. 插入排序（Insertion Sort） ####

插入排序是一种简单直观的排序算法，它将数组分为已排序和未排序两部分，每次从未排序部分取一个元素插入到已排序部分的正确位置。

示例代码：

public class InsertionSort {
        
        public static void insertionSort(int[] arr) {
        
            int n = arr.length;
            for (int i = 1; i < n; i++) {
        
                int key = arr[i];
                int j = i - 1;
                while (j >= 0 && arr[j] > key) {
        
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = key;
            }
        }
    }

#### 3. 选择排序（Selection Sort） ####

选择排序是一种简单直观的排序算法，它通过在每次遍历中选择最小（或最大）的元素，并将其放在已排序部分的末尾。

示例代码：

public class SelectionSort {
        
        public static void selectionSort(int[] arr) {
        
            int n = arr.length;
            for (int i = 0; i < n - 1; i++) {
        
                int minIndex = i;
                for (int j = i + 1; j < n; j++) {
        
                    if (arr[j] < arr[minIndex]) {
        
                        minIndex = j;
                    }
                }
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

#### 4. 快速排序（Quick Sort） ####

快速排序是一种高效的排序算法，它使用分治法策略，将数组分为小于基准值和大于基准值的两部分，然后递归地对两部分进行排序。

示例代码：

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++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            int temp = arr[i + 1];
            arr[i + 1] = arr[high];
            arr[high] = temp;
            return i + 1;
        }
    }

#### 5. 归并排序（Merge Sort） ####

归并排序是一种稳定的排序算法，它使用分治法策略，将数组分为两部分，递归地对两部分进行排序，然后将两部分合并成一个有序数组。

示例代码：

public class MergeSort {
        
        public static void mergeSort(int[] arr, int low, int high) {
        
            if (low < high) {
        
                int mid = (low + high) / 2;
                mergeSort(arr, low, mid);
                mergeSort(arr, mid + 1, high);
                merge(arr, low, mid, high);
            }
        }
        
        private static void merge(int[] arr, int low, int mid, int high) {
        
            int[] temp = new int[high - low + 1];
            int i = low, j = mid + 1, k = 0;
            while (i <= mid && j <= high) {
        
                if (arr[i] <= arr[j]) {
        
                    temp[k++] = arr[i++];
                } else {
        
                    temp[k++] = arr[j++];
                }
            }
            while (i <= mid) {
        
                temp[k++] = arr[i++];
            }
            while (j <= high) {
        
                temp[k++] = arr[j++];
            }
            for (int m = 0; m < temp.length; m++) {
        
                arr[low + m] = temp[m];
            }
        }
    }

#### 6. 堆排序（Heap Sort） ####

堆排序是一种高效的排序算法，它使用堆数据结构维护元素的大小关系，将未排序部分中最大（或最小）的元素放到已排序部分的末尾。

示例代码：

public class HeapSort {
        
        public static void heapSort(int[] arr) {
        
            int n = arr.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
        
                heapify(arr, n, i);
            }
            for (int i = n - 1; i >= 0; i--) {
        
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                heapify(arr, i, 0);
            }
        }
        
        private static void heapify(int[] arr, int n, int i) {
        
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if (left < n && arr[left] > arr[largest]) {
        
                largest = left;
            }
            if (right < n && arr[right] > arr[largest]) {
        
                largest = right;
            }
            if (largest != i) {
        
                int temp = arr[i];
                arr[i] =            arr[largest];
                arr[largest] = temp;
                heapify(arr, n, largest);
            }
        }
    }

### 二、查找算法 ###

查找算法用于在给定的数据集合中查找特定元素的位置或判断是否存在。

#### 1. 顺序查找（Linear Search） ####

顺序查找是一种简单直观的查找算法，它逐个遍历数据集合中的元素，直到找到目标元素或遍历完所有元素。

示例代码：

public class LinearSearch {
        
        public static int linearSearch(int[] arr, int target) {
        
            int n = arr.length;
            for (int i = 0; i < n; i++) {
        
                if (arr[i] == target) {
        
                    return i;
                }
            }
            return -1;
        }
    }

### 如何使用算法示例 ###

使用这些算法示例的步骤如下：

1.  创建一个Java类文件，例如"SortingExample.java"。
2.  在类中引入相应的排序或查找算法类，例如"import com.example.Sorting.\*;"。
3.  在主方法中创建一个测试数组或数据集合，并调用相应的算法方法进行排序或查找。
4.  运行Java程序，查看算法的执行结果。

例如，使用冒泡排序算法对一个整数数组进行排序的示例：

import com.example.Sorting.BubbleSort;
    
    public class SortingExample {
        
        public static void main(String[] args) {
        
            int[] arr = {
        5, 3, 8, 2, 1, 4};
            BubbleSort.bubbleSort(arr);
            System.out.println("排序结果：");
            for (int num : arr) {
        
                System.out.print(num + " ");
            }
        }
    }

希望以上示例能帮助你了解和使用Java中的常用算法。