algorithms-蛇形填数

package com.hqq.exercise.sort_search; import org.omg.CORBA.PUBLIC_MEMBER; import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.util.Arrays; /** * Sort 排序算法 * Created by heqianqian on 2017/8/15. */ public class Sort { private static final Logger LOGGER = LoggerFactory.getLogger(Sort.class); //选择排序 /** * 堆排序 */ public static void heapSort(int[] array) { if (array == null || array.length == 0) { return; } initMaxHeap(array); int temp; for (int i = array.length - 1; i >= 0; i--) { //每次交换第一个元素和最后一个元素 再调整成最大堆 temp = array[0]; array[0] = array[i]; array[i] = temp; createMaxHeap(array, i, 0); } } /** * 创建最大堆 */ private static void initMaxHeap(int[] array) { for (int i = (array.length - 1) / 2; i >= 0; i--) {//从第一个非叶子节点开始调整 createMaxHeap(array, array.length, i); } } private static void createMaxHeap(int[] array, int length, int index) { int rootIndex = index;//当前要调整最大堆的根节点 int childIndex = 2 * index + 1;//左孩子节点 int temp = array[rootIndex]; boolean flag = true; while (childIndex < length && flag) { if (childIndex < length - 1 && array[childIndex] < array[childIndex + 1]) { childIndex++;//选择左右子节点中的较大者 } if (temp > array[childIndex]) {//当前已经满足最大堆 flag = false; } else {//子节点上移 array[rootIndex] = array[childIndex]; rootIndex = childIndex; childIndex = 2 * rootIndex + 1;//继续往下遍历 } } array[rootIndex] = temp; } //交换排序 /** * 冒泡排序 * * @param array 待排序数组 */ public static void bubbleSort(int[] array) { boolean flag = false;//用来表示当前次排序有无交换元素 for (int i = 1; i < array.length && !flag; i++) { flag = true; for (int j = 0; j < array.length - i; j++) { if (array[j] > array[j + 1]) { flag = false; switchNumber(array, j, j + 1); } } } } /** * 双指针快排 * [默认以起始节点为基数] */ public static void quickSort(int[] array) { if (array == null || array.length == 0) { return; } partition(array, 0, array.length - 1); } private static void partition(int[] array, int start, int end) { if (start >= end) {//递归出口 左右指针重合 return; } int base = array[start];//默认选择第一个元素为基准元素 int leftIndex = start;//左指针 int rightIndex = end;//右指针 while (leftIndex != rightIndex) { while (leftIndex < rightIndex && array[rightIndex] >= base) {//从右往左寻找比基准元素小的元素 rightIndex--; } while (leftIndex < rightIndex && array[leftIndex] <= base) {//从左往右找比基准元素大的元素 leftIndex++; } if (leftIndex < rightIndex) {//交换两个元素 int temp = array[leftIndex]; array[leftIndex] = array[rightIndex]; array[rightIndex] = temp; } } //当前轮排序结束 将基准元素和指针元素交换 array[start] = array[leftIndex]; array[leftIndex] = base; //递归排序 partition(array, start, leftIndex - 1); partition(array, leftIndex + 1, end); } public static void main(String[] args) { int[] array = new int[]{3, 1, 2, 5}; int[] result = mergeSort(array); System.out.println(Arrays.toString(result)); } /** * 归并排序 */ public static int[] mergeSort(int[] array) { if (array == null || array.length == 0) { throw new IllegalArgumentException("Wrong Array!"); } int[] result = new int[array.length]; mergeSort(array, 0, array.length - 1, result); return result; } /** * 归并排序 */ private static void mergeSort(int[] array, int start, int end, int[] result) { if (start < end) {//拆分数组元素 直到每个数组的大小为1 int mid = (start + end) / 2; mergeSort(array, start, mid, result); mergeSort(array, mid + 1, end, result); //合并两个子数组 mergeArray(array, start, mid, end, result); } } /** * 合并两个子数组 */ private static void mergeArray(int[] array, int start, int mid, int end, int[] result) { int aIndex = start, bIndex = mid + 1, rIndex = 0; while (aIndex <= mid && bIndex <= end) { //只要两个子数组非空 就放入两个数组种较小的那个元素 if (array[aIndex] < array[bIndex]) { result[rIndex++] = array[aIndex++]; } else { result[rIndex++] = array[bIndex++]; } } /*当一个数组为空 将另一个数组的元素全部按照顺序取出*/ while (aIndex <= mid) { result[rIndex++] = array[aIndex++]; } while (bIndex <= end) { result[rIndex++] = array[bIndex++]; } //最后把排好序的元素复制合并到原数组中 System.arraycopy(result, 0, array, start, rIndex); } /** * 合并两个数组 * 前提是两个数组必须是有序的 */ private static int[] mergeArray(int[] a, int[] b) { int[] result = new int[a.length + b.length]; int aIndex = 0, bIndex = 0, rIndex = 0; while (aIndex < a.length && bIndex < b.length) { //两个数组都存在元素的情况下 取较小的那个元素 if (a[aIndex] < b[bIndex]) { result[rIndex++] = a[aIndex++]; } else { result[rIndex++] = a[bIndex++]; } } //当某个数组为空时 直接将另一个元素中剩下的元素按序取出即可 while (aIndex < a.length) { result[rIndex++] = a[aIndex++]; } while (bIndex < b.length) { result[rIndex++] = a[bIndex++]; } return result; } /** * 基数排序 * <p> * 如果需要对0-100内的若干个数据排序 那么初始化101个元素的数组 * 统计数组中每个值为i的元素出现的次数，存入数组的第i项 * 最后对所有的计数累加并打印 * * @param array 待排序数组 */ public static void radixSort(int[] array) { int maxNumber = getMaxNumber(array); int[] bucket = new int[maxNumber + 1]; for (int i = 0; i < array.length; i++) { bucket[array[i]]++; } for (int i = 0; i < bucket.length; i++) { for (int j = 0; j < bucket[i]; j++) { System.out.print(i + " "); } } } /** * 获取数组中的最大值 */ private static int getMaxNumber(int[] array) { int max = array[0]; for (int i = 1; i < array.length; i++) { if (max < array[i]) { max = array[i]; } } return max; } /** * 交换数组中两个元素的值 */ private static void switchNumber(int[] array, int index1, int index2) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } }