冒泡排序，选择排序，快速排序，堆排序与二分查找算法-蒲公英云

冒泡排序，选择排序，快速排序，堆排序与二分查找算法

public class Test {
    public static void main(String[] args) {
        int arr[] = { 5, 2, 3, 1, 4, -4, 6, 2 };
        // arr = sort1(arr);
        // arr = sort2(arr);
        //arr = sort3(arr, 0, arr.length - 1);
        arr = sort4(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        System.out.println("下标是:" + binarySearch(arr, 1));
    }
    // 冒泡排序
    public static int[] sort1(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    // 选择排序
    public static int[] sort2(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            if (i != min) {
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
        return arr;
    }
    // 快速排序
    public static int[] sort3(int arr[], int l, int r) {
        if (l < r) {
            int i = l, j = r, x = arr[l];
            while (i < j) {
                while (i < j && arr[j] >= x) {// 从向左找出第一个小于x的数并交换
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
                while (i < j && arr[i] < x) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = x;
            sort3(arr, l, i - 1);
            sort3(arr, i + 1, r);
        }
        return arr;
    }
    // 堆排序
    //3.交换
    public static void swap(int i, int j, int[] arr) { 
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //2.排序
    public static int[] sort4(int arr[]) {
        for (int i = 0; i < arr.length - 1; i++) {
            buildMaxHeap(arr, arr.length - i - 1);
            swap(0, arr.length - i - 1, arr);
        }
        return arr;
    }
    //1.构建最大堆
    public static void buildMaxHeap(int[] array, int lastIndex) {
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            // 记录当前的节点
            int k = i;
            // 说明有左孩子
            while (2 * k + 1 <= lastIndex) {
                int bigIndex = 2 * k + 1;
                // 说明有右孩子
                if (bigIndex < lastIndex) {
                    if (array[bigIndex] < array[bigIndex + 1]) {
                        bigIndex++;
                    }
                }
                if (array[bigIndex] > array[i]) {
                    swap(k, bigIndex, array);
                    k = bigIndex;
                } else {
                    break;
                }
            }
        }
    }
    // 二分查找
    public static int binarySearch(int arr[], int v) {
        int l = 0;
        int r = arr.length - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (arr[m] == v) {
                return m;
            } else if (arr[m] < v) {
                l = m + 1;
            } else if (arr[m] > v) {
                r = m - 1;
            }
        }
        return -1;
    }
}