几种常用的Java 算法

package jsh.mg.msg.service.msg.test;

import java.util.Arrays;

import static java.util.Arrays.binarySearch;


/**
 *
 * 几种常用的Java 算法
 */
public class TestClass {


    /**
     *
     * 二分查找算法
     */


    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;
    }

//    public static void main(String[] args) {
//        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//        int target = 5;
//        int index = binarySearch(arr, target);
//        if (index == -1) {
//            System.out.println("没有找到目标值");
//        } else {
//            System.out.println("目标值在数组中的位置是：" + (index+1));
//        }
//    }


    /**
     * 冒泡排序算法
     *
     * @param args
     */


    public static void sortMethod(int arr[]) {

        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

//    public static void main(String[] args) {
//
//        int arr[] = {50, 30, 10, 20, 40, 70, 60};
//
//        sortMethod(arr);
//        System.out.println("排序后的数组为：");
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(arr[i] + "");
//        }
//    }


    /**
     * 插入排序算法
     *
     * @param arr
     */
    public static void sort(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;
        }
    }

//    public static void main(String[] args) {
//        int[] arr = {4, 2, 9, 3, 5};
//        sort(arr);
//        for (int i : arr) {
//            System.out.print(i + " ");
//        }
//    }

    /**
     * 快速排序算法
     */
    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivotIndex = partition(arr, start, end); // 获取分区点
            quickSort(arr, start, pivotIndex - 1); // 对左半部分进行快速排序
            quickSort(arr, pivotIndex + 1, end); // 对右半部分进行快速排序
        }
    }

    // 分区函数
    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[start]; // 选取第一个元素作为分区点
        int left = start + 1;
        int right = end;
        while (left <= right) {
            // 搜索大于等于 pivot 的元素位置
            while (left <= right && arr[left] < pivot) {
                left++;
            }
            // 搜索小于等于 pivot 的元素位置
            while (left <= right && arr[right] > pivot) {
                right--;
            }
            if (left <= right) {
                // 交换元素位置
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
        }
        // 将分区点放入正确的位置上
        int temp = arr[start];
        arr[start] = arr[right];
        arr[right] = temp;
        return right;
    }

//    public static void main(String[] args) {
//        int[] arr = {5, 3, 8, 6, 4};
//        quickSort(arr, 0, arr.length - 1);
//        for (int i : arr) {
//            System.out.print(i + " ");
//        }
//    }


    /**
     *
     * 希尔排序算法
     * @param args
     */

    public static void shellSort(int[] arr) {
        int len = arr.length;
        int h = 1;
        while (h < len / 3) {
            h = 3 * h + 1;  // Knuth序列
        }
        while (h >= 1) {
            for (int i = h; i < len; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    swap(arr, j, j - h);
                }
            }
            h /= 3;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

//    public static void main(String[] args) {
//        int arr[] = {2,4,1,6,3,8};
//
//        shellSort(arr);
//
//        for (int i : arr) {
//            System.out.println(i + "");
//        }
//    }


    /**
     * 归并排序算法
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int[] temp = new int[arr.length];// 申请一个与原数组相同大小的临时数组
        mergeSort(arr, 0, arr.length - 1, temp);// 调用递归函数排序
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);// 左子序列归并排序
            mergeSort(arr, mid + 1, right, temp);// 右子序列归并排序
            merge(arr, left, mid, right, temp);// 合并两个有序子序列
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;// 左序列指针
        int j = mid + 1;// 右序列指针
        int t = 0;// 临时数组指针
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {// 如果左序列当前元素不大于右序列当前元素
                temp[t++] = arr[i++];// 将左序列当前元素拷贝到临时数组中
            } else {// 如果左序列当前元素大于右序列当前元素
                temp[t++] = arr[j++];// 将右序列当前元素拷贝到临时数组中
            }
        }
        while (i <= mid) {// 如果右序列已经全部拷贝到临时数组中，而左序列还有剩余
            temp[t++] = arr[i++];// 继续将左序列剩余元素拷贝到临时数组中
        }
        while (j <= right) {// 如果左序列已经全部拷贝到临时数组中，而右序列还有剩余
            temp[t++] = arr[j++];// 继续将右序列剩余元素拷贝到临时数组中
        }
        t = 0;// 将归并后的临时数组拷贝回原数组
        while (left <= right) {
            arr[left++] = temp[t++];
        }
    }

//    public static void main(String[] args) {
//        int[] arr = {3, 5, 2, 6, 1, 4};
//        mergeSort(arr);
//        for (int i : arr) {
//            System.out.print(i + " ");
//        }
//    }

}