package com.itwang.sort_search;/** * @ProjectName: JavaPractice * @Package: com.itwang.sort_search * @ClassName: BinarySearch * @Author: JikeWang * @Description: 二分查找 * @Date: 2018-08-28 21:21 * @Version: 1.0 */public class Search {    /**     * @Method find     * @Author JikeWang     * @Version  1.0     * @Description 顺序查找     * @param array 要查找的元素数组     * @param key 要查找的元素     * @Return int 返回查找结果 -1：表示没有查找到  0~array.length-1: 表示查找到     * @Exception     * @Date 2018-08-30 18:42     */    public int find(int[] array, int key){        int i;        for (i = 0 ;i < array.length; i++){            if (array[i] == key){                break;            }        }        if (i == array.length){            return -1;//如果没有查找到        }else{            return i;//如果查找到        }    }    /**     * @Method binarySearch     * @Author JikeWang     * @Version  1.0     * @Description 二分查找（折半查找）前提元素必须是有序的     * @param array 要查找的数组     * @param key 要查找的关键元素     * @Return int 返回的查找结果,如果找到则返回元素的位置，如果没有找到则返回元素应该插入的位置     * @Exception     * @Date 2018-08-28 21:28     */    public int binarySearch(int[] array, int key){        int low = 0, high = array.length - 1;        while (low <= high){            int mid = (high + low) >> 1;            if (array[mid] < key){                low = mid + 1;            }else if (array[mid] > key){                high = mid - 1;            }else {                return mid;            }        }        return low;    }    /********************************插入排序********************************/    /**     * @Method insertSort     * @Author JikeWang     * @Version  1.0     * @Description 直接插入排序     * @param array 要排序的数组集合     * @Return void     * @Exception     * @Date 2018-08-30 18:44     */    void insertSort(int[] array){        //直接插入排序，假定前面是有序的，从1后面位置开始插入排序        System.out.println("---------直接插入排序---------");        for (int i = 1; i < array.length; i++){            int tmp = array[i];            int j = i - 1;            //遍历找到插入的位置            while ((j >= 0) && (tmp < array[j])){                array[j + 1] = array[j];//如果插入的元素小于当前元素，元素后移                j--;            }            //将要插入的元素插入到找到的位置（j+1)是由于上面循环结束后减了一次1            array[j + 1] = tmp;        }    }    /**     * @Method binaryInsertSort     * @Author JikeWang     * @Version  1.0     * @Description 折半插入排序（跟直接插入排序一样，只是在查找元素插入位置的时候利用了折半查找     * @param array 要排序的数组集合     * @Return void     * @Exception     * @Date 2018-08-30 18:45     */    void binaryInsertSort(int[] array){        System.out.println("---------折半插入排序---------");        for (int i = 1; i < array.length; i++){            int tmp = array[i];            int low = binarySearch(array,tmp);            //元素后移            for (int j = i - 1; j >= low; j --){                array[j+1] = array[j];            }            array[low] = tmp;        }    }    /**     * @Method shellSort     * @Author JikeWang     * @Version  1.0     * @Description 希尔排序（先将整个待排序记录序列分割成若干子序列，分别进行直接插入排序，     *              待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序）     *              分割序列可以根据某一增量进行分割     * @param array     * @Return void     * @Exception     * @Date 2018-08-30 18:49     */    public void shellSort(int[] array){        //增量每次都是/2        for (int step = array.length / 2; step > 0; step /= 2){            //从增量那组开始进行插入排序，直至完毕            for (int i = step; i < array.length; i++){                int j = i;                int tmp = array[j];                //j-step就是代表与它同组隔壁的元素                while (j - step >= 0 && tmp < array[j - step]){                    array[j] = array[j - step];                    j = j - step;                }                array[j] = tmp;            }        }    }    /********************************交换排序********************************/    /**     * @Method bubbleSort     * @Author JikeWang     * @Version  1.0     * @Description 冒泡排序，每次循环通过比较相邻的元素大小进行交换，最终会是最后一个元素时最大的。     *              第一轮，需要循环n-1次，最后一个元素最大，     *              第二轮，需要循环n-2次，最后一个元素最大，     *              以此类推，需要进行n轮，每轮循环n-i次     * @param array     * @Return void     * @Exception     * @Date 2018-08-30 18:57     */    public void bubbleSort(int[] array){        System.out.println("---------冒泡排序---------");        //进行array.length次循环,每轮进行array.length - i次循环        for (int i = 1; i <= array.length; i++){            boolean flag = true;            //设定一个标记，若为true，则表示此次循环            //没有进行交换，否则有交换            for (int j = 0; j < array.length - i; j++){                if (array[j] > array[j + 1]){                    swap(array, j, j+1);                    flag = false;                }            }        }    }    /**     * @Method quickSort     * @Author JikeWang     * @Version  1.0     * @Description 快速排序（快速排序是对冒泡排序的一种改进，通过一趟排序将待排序列分割成独立的两部分，     *              其中一部分记录的关键字均比另一部分记录关键字小，然后分别对这两部分记录进行排序）     * @param array     * @param low     * @param high     * @Return void     * @Exception     * @Date 2018-08-30 19:01     */    public void quickSort(int[] array, int low, int high){        if (low >= high){            return;        }        int index = partition(array, low, high);        quickSort(array, low, index - 1);        quickSort(array, index + 1, high);    }    public int partition(int[] array, int low, int high) {        //以第一个元素作为枢轴值        int key = array[low];        while (low < high){            //从后半部分向前扫描            while (array[high] >= key && low < high) high--;            //将后半部分小于枢轴值的元素放到前半部分            array[low] = array[high];            //从前半部分向后扫描            while (array[low] <= key && low < high) low++;            //将前半部分大于枢轴值的元素放到后半部分            array[high] = array[low];        }        array[low] = key;        return low;    }    /********************************选择排序********************************/    /**     * @Method selectSort     * @Author JikeWang     * @Version  1.0     * @Description 简单选择排序（每一次首先选择当前索引位置的元素是最小值，通过跟后面元素的比较，确定最小元素位置，     *              如果最小位置发生变化，则将最小位置的元素赋值到当前选择的位置）     * @param array     * @Return void     * @Exception     * @Date 2018-08-30 19:01     */    public void selectSort(int[] array){        System.out.println("---------简单选择排序---------");        for (int i = 0; i < array.length - 1; i++){            int min = i;            //每一趟循环比较，找到最小的元素的下标并赋值给min            for (int j = i + 1;j < array.length; j++){                if (array[j] < array[min])                    min = j;            }            //如果min发生变化，进行交换            if (min != i){                swap(array, min, i);            }        }    }    //构建大顶堆    public int[] buildMaxHeap(int[] array){        for (int i = array.length / 2 - 1;i >= 0;i--){            //从第一个非叶子节点从下至上，从右至左调整结构            adjustDownHeap(array, i, array.length);        }        return array;    }    //向下调整堆    private void adjustDownHeap(int[] array, int k, int length) {        //取出当前元素        int tmp = array[k];        //i为初始化为节点k的左孩子，沿节点较大的子节点向下调整        for (int i = 2*k + 1; i < length - 1; i = 2*i + 1 ){            if (i < length && array[i] < array[i+1])//取节点较大的子节点的下标                i++;//如果节点的右孩子>左孩子，则取右孩子节点的下标            if (array[i] <= tmp) break;//根节点 >=左右子女中关键字较大者，调整结束            else{ //根节点 
     <左右子女中关键字较大者 array[k]="tmp;//被调整的结点的值放人最终位置" k="i;" 【关键】修改k值，以便继续向下调整 } ** * @method heapsort @author jikewang @version 1.0 @description 堆排序（堆排序首先需要构建堆，这里是构建大顶堆，构建完毕后需要将元素从小到大整理出来， 因为堆顶元素时最大值，通过从后向前操作，每次将堆顶元素赋值到当前位置，但每次赋值后， 堆的结构就发生了变化，需要重新调整） @param array="buildMaxHeap(array);" @return void @exception @date 2018-08-30 19:01 public heapsort(int[] array){ n-1趟的交换和建堆过程 for (int i - 1;>
       1;i--){            swap(array, 0, i);//将堆顶元素和堆低元素交换            adjustDownHeap(array, 0, i);//整理、将剩余的元素整理成堆        }    }    /**     * @Method deleteMax     * @Author JikeWang     * @Version  1.0     * @Description 删除堆顶元素操作     * @param array     * @Return int[]     * @Exception     * @Date 2018-08-30 19:02     */    public int[] deleteMax(int[] array){        //将堆的最后一个元素与堆顶元素交换，堆底元素值设为-999996        array[0] = array[array.length-1];        array[array.length-1] = -99999;        //对此时的根节点进行向下调整        adjustDownHeap(array, 0, array.length);        return array;    }    /**     * @Method insertData     * @Author JikeWang     * @Version  1.0     * @Description 插入操作:向大根堆array中插入数据data     * @param array     * @param data     * @Return int[]     * @Exception     * @Date 2018-08-30 19:02     */    public int[] insertData(int[] array, int data){        array[array.length-1] = data; //将新节点放在堆的末端        int k = array.length-1;  //需要调整的节点        int parent = (k-1)/2;    //双亲节点        while(parent >=0 && data>array[parent]){            array[k] = array[parent];  //双亲节点下调            k = parent;            if(parent != 0){                parent = (parent-1)/2;  //继续向上比较            }else{  //根节点已调整完毕，跳出循环                break;            }        }        array[k] = data;  //将插入的结点放到正确的位置        return array;    }    //两个位置的元素交换值    private void swap(int[] array, int j, int i) {        int tmp = array[j];        array[j] = array[i];        array[i] = tmp;    }    //打印元素    void print(int[] array){        for (int a : array) {            System.out.print(a + "\t");        }        System.out.println();    }    public static void main(String[] args) {        int[] array = {2,5,7,9,24};        int[] sort_array = {2,5,3,1};        Search search = new Search();        //二分查找（折半查找）        int result = search.binarySearch(array, 10);        System.out.println(result);        //直接插入排序        //search.insertSort(sort_array);        //折半插入排序        //search.binaryInsertSort(sort_array);        //冒泡排序        //search.binaryInsertSort(sort_array);        //简单选择排序        //search.selectSort(sort_array);        //希尔排序        //search.shellSort(sort_array);        //快速排序        //search.quickSort(sort_array, 0, sort_array.length - 1);        search.heapSort(sort_array);        search.print(sort_array);    }}