排序算法及比较

冒泡排序

/**
 * 冒泡排序
 * 时间复杂度 是 O(n^2)
 * 空间复杂度 是 O(1)
 *  稳定
 * 
 */
private static void bubbleSort(int[] arr) {
        /*  标识符  flag  true 表示执行过交换操作  否则没有进行交换*/
        boolean flag = false;
        for (int i = 0; i < arr.length-1; i++) {

            /*  每循环一次，都会将最大的数放到最后 */
            for (int j = 0; j < arr.length-1-i; j++){
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            System.out.println("第"+(i+1)+"趟排序后："+ Arrays.toString(arr));
            if (flag==false){
                /* 在一趟排序操作中  没有执行过一次交换操作  则表示数组已经有序*/
                break;
            }else {
                flag = false; /*  重置标识符 进行判断*/
            }

        }
    }

选择排序

/**
 * 
 */
 private static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i+1; j <= arr.length-1 ; j++) {
                /* 找到最小值 索引 */
                if (min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
//            if (minIndex!=i){
            /*   交换 最小的索引*/
//                arr[minIndex] = arr[i];
//                arr[i] = min;
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
//            }
        }
    }

插入排序

/**
 * 插入排序
 * 
 */

 public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {


            int insertVal = arr[i];
            int insertIndex =i-1;

            while( insertIndex>=0 && insertVal <arr[insertIndex]){

                arr[insertIndex +1] =arr[insertIndex];
                insertIndex--;

                System.out.println(Arrays.toString(arr));
            }


            arr[insertIndex+1]=insertVal;
        }
    }

快速排序

/**
 * 快速排序
 */
 public static void  quickSort(int arr[],int left ,int right){

            if(left>=right){
                return;
            }

            int pos = left;
            int posVal = arr[left];
            int i = left;
            int j= right;
            while(i != j){
//			先保证右侧找到一个比pos 小 的
                while(i<j){

                    if(arr[j]<posVal){

                        break;
                    }

                    j--;
                }
//			从  左侧找一个比基准值大的
                while(i<j){

                    if(arr[i]>posVal){

                        break;
                    }

                    i++;
                }


                if(i==j){
                    break;
                }else{
                    /*   交换变量的值  */
                    int temp = arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }


            if (i==j){
//		  相等  则 交换 pos  和  指针的值
                arr[pos]= arr[i];
                arr[i]= posVal;

            }

            /* 像左侧递归*/
            quickSort(arr,left,i-1);
            /*  向右侧递归*/
            quickSort(arr,i+1,right);


        }

堆排序

二分查找

/**
 * 
 *  二分查找  
 */

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) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }


            return  -1;


    }
/**     二分查找基于 递归              */

  /**
     *
     *  二分查找  递归 
     * @param arr  数组本身
     * @param target   查找目标元素   
     * @param left    左指针
     * @param right  右指针
     * @return  返回下标
     */
    public static int binarySearch(int[] arr, int target ,int left ,int right) {

        if (left>right){
            return -1;
        }

        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
            return binarySearch(arr,target,left,right);
        } else {
            left = mid + 1;
            return binarySearch(arr,target,left,right);
        }






    }