intellij
链接：https://pan.baidu.com/s/1ZcPuFQC2YirPt-QtKcEDmg?pwd=2314
提取码：2314
一、基数排序
适用于范围较小的整数数组，先统计每个元素出现的次数，然后根据统计结果依次输出原数组的每个元素。非比较排序。
package db; import java.util.Arrays; public class jspx { public static void main(String[] args) { int[] arr = {10, 2, 4, 9, 11, 15, 45, 87, 56, 23, 96, 100, 120, 17, 156}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int[] arr) { // 找最大值 int max = arr[0]; for (int j = 0; j < arr.length; j++) { if (arr[j] > max) { max = arr[j]; } } // 找最大值的位数 int maxLen = (max + "").length(); // 定义0-9十个桶 int[][] bucket = new int[10][arr.length]; // 定义桶记录工具 int[] elementCount = new int[10]; // 每个桶中有效元素的计数 int n = 1; // 每一轮所处理的位数（1, 10, 100,...） // 不断执行数据放入和数据取出 for (int m = 0; m < maxLen; m++) { // 数据放入 for (int i = 0; i < arr.length; i++) { // 将数据放入哪个桶 int element = (arr[i] / n) % 10; // 将数据放入桶中，并更新元素计数 bucket[element][elementCount[element]] = arr[i]; elementCount[element]++; } // 数据取出 int index = 0; for (int k = 0; k < 10; k++) { for (int l = 0; l < elementCount[k]; l++) { arr[index++] = bucket[k][l]; // 只增加 index } // 清除桶记录中的数据 elementCount[k] = 0; // 计数清零 } n = n * 10; // 处理下一个位数 } } }
二、冒泡排序
通过重复遍历待排序的数组，比较相邻的元素并交换它们的位置，如果顺序错误。每次遍历找到最大的元素放到最后，逐步将未排序的部分缩小，直到数组有序。
package db; public class Bubble { public static void main(String[] args) { int[] arr = new int[] {1, 2, 5, 6, 8, 9, 7}; sort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void sort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length-1-i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } }
三、希尔排序
基于插入排序，通过将数组按一定增量分组，先对小组内元素进行插入排序，再逐步缩小增量，最终进行一轮插入排序，使得整个数组有序。
package db; public class xepx { public static void main(String[] args) { int [] arr=new int [] {1,2,3,6,5,4,8,9,7 }; sort(arr); for(int i=0;i<arr.length;i++) { System.out.print(arr[i]); } } public static void sort(int[] arr) { for(int h=arr.length/2;h>0;h/=2) { for(int i=h;i<arr.length;i++) { for(int j=i-h;j>0;j--) { if(arr[j]>arr[j+h]) { int temp=arr[j]; arr[j]=arr[j+h]; arr[j+h]=temp; } } } } } }
四、插入排序
将未排序的元素插入到已排序的部分中，逐步扩展已排序部分。开始时，将第一个元素视为已排序。对每个元素，从后向前遍历，找到合适的位置插入。
package db; public class insert { public static void main(String[] args) { int[] arr=new int[] {1,2,3,4,5,8,4,2}; sort(arr); for(int i=0;i<arr.length;i++) { System.out.print(arr[i]); } } public static void sort(int[] arr) { for(int i=1;i<arr.length;i++) { for(int j=i-1;j>=0;j--) { if(arr[j]>arr[j+1]) { int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } } }
五、堆排序
利用堆数据结构，把数组构造成一个最大堆或最小堆，然后依次将最大值或最小值取出放到已排序部分。该过程包括构建堆和调整堆。
package db; public class HeapSort { public static void main(String[] args) { int[] arr = new int[] {1, 2, 3, 4, 5, 8, 4, 2}; sort(arr); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void sort(int[] arr) { int n = arr.length; for (int i = n-1; i >= 0; i--) { heapify(arr, n, i); } for (int i = n - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } public static void heapify(int[] arr, int n, int rootIndex) { int largest = rootIndex; int leftChild = 2 * rootIndex + 1; int rightChild = 2 * rootIndex + 2; if (leftChild < n && arr[leftChild] > arr[largest]) { largest = leftChild; } if (rightChild < n && arr[rightChild] > arr[largest]) { largest = rightChild; } if (largest != rootIndex) { int swap = arr[rootIndex]; arr[rootIndex] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } }
六、快速排序
选择一个“基准”元素，将数组分为左右两个部分，左侧为小于基准的元素，右侧为大于基准的元素。递归地对这两个部分进行排序。
package db; public class quiksort { public static void main(String[] args) { int[] arr = new int[] {1, 2, 3, 4, 5, 8, 4, 2}; sort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void sort(int [] arr,int left,int right) { if (left>=right) { return ; } int i=left; int j=right; int base=arr[left]; while(i!=j) { while(base<=arr[j]&&j>i) { j--; } while(base>=arr[i]&&i<j) { i++; } int t=arr[j]; arr[j]=arr[i]; arr[i]=t; } arr[left]=arr[j]; arr[j]=base; sort(arr,left,i-1); sort(arr,i+1,right); } }
七、选择排序
选择排序是一种简单的排序算法，其基本思路是通过多次遍历，将每次遍历中找到的最小（或最大）元素放到已排序序列的末尾（或开头）。
package db; public class SeachSort { public static void main(String[] args) { int [] arr=new int[] {1,2,5,6,8,9,7}; sort(arr); for(int i=0;i<arr.length;i++) { System.out.print(arr[i]); } } public static void sort(int[] arr) { for(int j=0;j<arr.length;j++) { int minIndex=j; int min=arr[j]; for(int i=j+1;i<arr.length;i++) { if(min>arr[i] ){ min=arr[i]; minIndex=i; } } arr[minIndex]=arr[j]; arr[j]=min; } } }
八、归并排序
采用分治法将数组分成两半，分别排序并合并。这是一个递归算法，先递归到最小的子数组（1个元素），再合并成有序数组。
package db; public class MergeSort { public static void main(String[] args) { int[] arr = new int[] {1, 2, 3, 4, 5, 8, 4, 2}; sort(arr, 0, arr.length - 1); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void sort(int[] arr, int left, int right) { if (left >= right) { return; } int mid = (left + right) / 2; sort(arr, left, mid); sort(arr, mid + 1, right); merge(arr, left, mid, right); } public static void merge(int[] arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int[] L = new int[n1]; int[] R = new int[n2]; for (int i = 0; i < n1; i++) { L[i] = arr[left + i]; } for (int j = 0; j < n2; j++) { R[j] = arr[mid + 1 + j]; } int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k++] = L[i++]; } else { arr[k++] = R[j++]; } } while (i < n1) { arr[k++] = L[i++]; } while (j < n2) { arr[k++] = R[j++]; } } }
