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] = array[i];//将左右子结点中较大值array[i]调整到双亲节点上
 k = i; //【关键】修改k值，以便继续向下调整
 }
 }
 array[k] = tmp;//被调整的结点的值放人最终位置
 }
 /**
 * @Method heapSort
 * @Author JikeWang
 * @Version 1.0
 * @Description 堆排序（堆排序首先需要构建堆，这里是构建大顶堆，构建完毕后需要将元素从小到大整理出来，
 * 因为堆顶元素时最大值，通过从后向前操作，每次将堆顶元素赋值到当前位置，但每次赋值后，
 * 堆的结构就发生了变化，需要重新调整）
 * @param array
 * @Return void
 * @Exception
 * @Date 2018-08-30 19:01
 */ public void heapSort(int[] array){
 array = buildMaxHeap(array);
 //n-1趟的交换和建堆过程
 for (int i = array.length - 1; i > 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);
 }
}