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