本专栏目录

蓝桥杯算法竞赛大纲
数论相关（Java）
枚举相关（Java）
对象排序（Java）
字符串相关（Java）
排序相关算法（Java）
记忆化搜索（Java）
树论相关（Java）
图论相关（Java）
堆（Java）
贪心（Java）

冒泡排序

package 排序;public class _冒泡排序 {public static void main(String[] args) {int[] arr = {-1, 123, 32, 12, 58, 9, 90};bubbleSort(arr);}// 冒泡排序public static void bubbleSort(int[] arr){int temp = 0;for (int i = 0; i < arr.length - 1; i++) {// 判断这一趟是否排序好boolean end = true;for (int j = 0; j < arr.length - 1 - i; j++) {if(arr[j] > arr[j+1]){end = false;temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}if(end){break;}}}
}

选择排序

package 排序;import java.util.Arrays;public class _选择排序 {public static void main(String[] args) {int[] arr = {-1, 123, 32, 12, 58, 9, 90};selectSort(arr);System.out.println();System.out.println(Arrays.toString(arr));}public static void selectSort(int[] arr) {int temp = 0;  // 用于交换for (int i = 0; i < arr.length - 1; i++) {int idx = i;for (int j = i; j < arr.length; j++) {if (arr[idx] > arr[j]) {idx = j;}}temp = arr[idx];arr[idx] = arr[i];arr[i] = temp;}}
}

快速排序

package 排序;import java.util.Arrays;public class _快速排序 {public static void main(String[] args) {int[]arr = {123,4,34,1,321,312,3,43,4,3};quick_sort(arr, 0, arr.length-1);System.out.println(Arrays.toString(arr));}public static void quick_sort(int[] arr, int left, int right){if(left < right){int l = left;int r = right;int val = arr[r]; // arr[right]即arr[r]就是第一个坑while (l<r){while (l<r && arr[l]<=val){  // 从左向右找大于val的数来填arr[r]l++;}if(l<r){arr[r--] = arr[l];  // 将arr[l]填到arr[r]中，s[l]就形成了一个新的坑}while (l<r&&arr[r]>val){  // 从右向左找小于或等于val的数来填arr[l]r--;}if(l<r){arr[l++] = arr[r];}}arr[r] = val; // 退出时,l等于r将val填到这个坑中。quick_sort(arr,left,l-1); // 递归调用quick_sort(arr,r+1,right);}}
}

插入排序

package 排序;import java.util.Arrays;public class _插入排序 {public static void main(String[] args) {int[] arr = {-1, 123, 32, 12, 58, 9, 90};insertSort(arr);System.out.println(Arrays.toString(arr));}public static void insertSort(int[] arr){// 默认前i个数都是排好序的, 只需要将第i+1个数插入到合适位置即可int insertVal = 0;for (int i = 1; i < arr.length; i++) {insertVal = arr[i];  // 将这个要插入的数(索引为i对应的val)拿出来// 用这个数跟前面的数比,如果要插入的数大于前面的某个数,则插到这个数后面// 如过比他小,则将这个数往后面的位置挪一下// 注意j>=0int j = i-1;for ( ;j >= 0; j--) {if(insertVal > arr[j]){break;}arr[j+1] = arr[j];}arr[j+1] = insertVal;}}
}

希尔排序

package 排序;import java.util.Arrays;public class _希尔排序 {public static void main(String[] args) {int[] arr = {-1, 123, 32, 12, 58, 9, 90};shellSort(arr);System.out.println(Arrays.toString(arr));}public static void shellSort(int[] arr){/*** 希尔排序是插入排序的优化* 希尔排序相对于插入排序相邻比较,采用了分组等间隔数之间进行比较排序* 间隔的取法: loop: gap /= 2; gap > 0* 希尔排序可以使较小的数尽量的靠前*/int temp = 0;for (int gap=arr.length/2; gap > 0; gap /= 2){for (int i = gap; i < arr.length; i++) {temp = arr[i];int j = i-gap;for (; j >= 0; j-=gap) {if(temp>arr[j]){break;}arr[j+gap] = arr[j];}arr[j+gap] = temp;}
//            System.out.printf("gap为%d的结果为:%s\n",gap,Arrays.toString(arr));}}
}

堆排序

将二叉树调整为大顶堆index指向当前需要调整(子树)的根结点
对所有非叶子节点从下向上, 从左向右进行调整
上浮: k初始指向index对应节点的左子节点
令k指向最大的子节点
当子节点的值大于父节点时, 让子节点上浮
子节点与父节点的值进行交换, 并让index指向子节点,继续下次循环
当父节点值大于子节点值或者此时index指向叶子节点时,调整完毕堆排利用了大顶堆和完全二叉树的特点length = arr.length
二叉树 => 大顶堆
将大顶堆的根节点与有效长度内的最后一个节点交换
length -= 1
对此时的根节点进行调整 => 大顶堆
循环上述过程, 直到length == 1

package 排序;import java.util.Arrays;public class _希尔排序 {public static void main(String[] args) {int[] arr = {-1, 123, 32, 12, 58, 9, 90};shellSort(arr);System.out.println(Arrays.toString(arr));}public static void shellSort(int[] arr){/*** 希尔排序是插入排序的优化* 希尔排序相对于插入排序相邻比较,采用了分组等间隔数之间进行比较排序* 间隔的取法: loop: gap /= 2; gap > 0* 希尔排序可以使较小的数尽量的靠前*/int temp = 0;for (int gap=arr.length/2; gap > 0; gap /= 2){for (int i = gap; i < arr.length; i++) {temp = arr[i];int j = i-gap;for (; j >= 0; j-=gap) {if(temp>arr[j]){break;}arr[j+gap] = arr[j];}arr[j+gap] = temp;}
//            System.out.printf("gap为%d的结果为:%s\n",gap,Arrays.toString(arr));}}
}

归并排序

package 排序;import java.util.Arrays;public class _归并排序 {public static void main(String[] args) {int[] arr = {-1, 123, 32, 12, 58, 9, 90};int[] temp = new int[arr.length];mergeSort(arr, 0, arr.length-1, temp);System.out.println(Arrays.toString(arr));}public static void mergeSort(int[] arr,int left, int right, int[] temp){if(left < right){int mid = (left + right) / 2;  // 中间索引// 向左递归mergeSort(arr, left, mid, temp);// 向右递归mergeSort(arr, mid + 1, right, temp);// 合并merge(arr, left, mid, right, temp);}}/**** @param arr  排序的原始数组* @param left  左边有序序列的初始索引* @param mid  中间索引* @param right  右边索引* @param temp  做中转的数组*/public static void merge(int[] arr, int left, int mid, int right, int[] temp){int i = left;  // 初始化i, 左边有序序列的初始索引int j = mid + 1;   // 初始化j, 右边有序序列的初始索引int t = 0;   // 指向temp数组的当前索引// (一)// 先把左右两边(有序)的数据按照规则填充到temp数组// 直到左右两边的有序序列,有一边处理完毕为止while (i <= mid && j <= right){// 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素// 即将左边的当前元素，填充到 temp数组// 然后 t++, i++if(arr[i] < arr[j]){temp[t] = arr[i];i++;t++;}else{   // 反之,将右边有序序列的当前元素，填充到temp数组temp[t] = arr[j];j++;t++;}}// (二)// 把有剩余数据的一边的数据依次全部填充到tempwhile (i <= mid){   // 左边的有序序列还有剩余的元素，就全部填充到temptemp[t] = arr[i];i++;t++;}while (j <= right){  // 右边的有序序列还有剩余的元素，就全部填充到temptemp[t] = arr[j];j++;t++;}// (三)// 将temp数组的元素拷贝到arr// 注意，并不是每次都拷贝所有t = 0;int tempLeft = left;// 第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3// 最后一次 tempLeft = 0  right = 7while (tempLeft <= right){arr[tempLeft] = temp[t];tempLeft++;t++;}}
}

基数排序

package 排序;import java.util.Arrays;/*
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。
然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。*/
public class _基数排序 {public static void main(String[] args) {int[] arr = {1, 123, 32, 12, 58, 9, 90};radixSort(arr);System.out.println(Arrays.toString(arr));}public static void radixSort(int[] arr){// 得到数组中最大的数的位数int max = arr[0];for (int i=1; i < arr.length;i++){if(arr[i]>max){max = arr[i];}}// 得到最大数是几位数int maxLength = (max + "").length();// 定义一个二维数组,表示10个桶, 每个桶就是一个一维数组int[][] bucket = new int[10][arr.length];  // 空间换时间// 记录每个桶中实际存放了多少个数据int[] bucketElementCounts = new int[10];for (int i = 0; i < maxLength; i++) {for (int j = 0; j < arr.length; j++){// 取出每个元素的对应位的值int digitOfElement = arr[j] / (int)Math.pow(10, i) % 10;// 放入到对应的桶中int count = bucketElementCounts[digitOfElement];bucket[digitOfElement][count] = arr[j];bucketElementCounts[digitOfElement]++;}// 按照这个桶的顺序(一维数组的下标依次取出数据,放入原来数组)int index = 0;for (int k = 0; k < bucketElementCounts.length; k++){// 如果桶中有数据才放入到原数组if(bucketElementCounts[k] > 0){// 循环该桶即第k个桶(即第k个一维数组), 放入for(int l=0; l < bucketElementCounts[k]; l++){arr[index++] = bucket[k][l];}// 第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k] = 0;}}}}
}

插入与归并排序判断

package 排序;import java.util.Arrays;
import java.util.Scanner;public class _InsertorMerge {static int[] arr;static int[] brr;static int[] cmp;static int n;public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt();arr = new int[n];brr = new int[n];cmp = new int[n];for (int i = 0; i < n; i++) {arr[i] = scan.nextInt();brr[i] = arr[i];}for (int i = 0; i < n; i++) {cmp[i] = scan.nextInt();}if (isInsert()) return;int k = 1;boolean flag = false;while (true){k *= 2;for (int i = 0; i < n; i+=k) {if (i+k>n){Arrays.sort(brr, i, n);break;}else {Arrays.sort(brr, i, i+k);}}if (flag){System.out.println("Merge Sort");System.out.print(brr[0]);for (int j = 1; j < n; j++) {System.out.print(" " + brr[j]);}break;}if (isSame(brr, cmp)){flag = true;}}}public static boolean isInsert(){boolean flag = false;for (int i = 1; i < n; i++) {int t = arr[i];int j = i - 1;for (;j >= 0; j--) {if (t > arr[j]){break;}arr[j+1] = arr[j];}arr[j+1] = t;if (flag){System.out.println("Insertion Sort");System.out.print(arr[0]);for (j = 1; j < n; j++) {System.out.print(" " + arr[j]);}return true;}if (isSame(arr, cmp)){flag = true;}}return false;}public static boolean isSame(int[] a, int[] b){for (int i = 0; i < n; i++) {if (a[i]!=b[i]){return false;}}return true;}
}