1、转换字符串的类
1 /**
2 * 排序后组成字符串
3 */
4 public class ArrayToString {
5 public static String arrayToString(int[] arr) {
6 StringBuilder sb = new StringBuilder();
7 sb.append("[");
8 for (int i = 0; i < arr.length; i++) {
9 if (i == arr.length - 1) {
10 sb.append(arr[i]);
11 } else {
12 sb.append(arr[i]).append(",");
13 }
14 }
15 sb.append("]");
16 String s = sb.toString();
17 return s;
18 }
19 }
2、冒泡排序
1 /**
2 * 冒泡排序
3 * 原理：
4 * 1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
5 * 2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这之后，最后的元素应该会是最大的数。
6 * 3、针对所有的元素重复以上的步骤，除了最后一个。
7 * 4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
8 */
9 public class MaoPao {
10 public static void main(String[] args) {
11
12 int[] arr = {27, 12, 34, 22, 11};
13 System.out.println("冒泡排序前：" + arrayToString(arr));
14
15 for (int i = 0; i < arr.length; i++) {
16 for (int j = 0; j < arr.length - 1 - i; j++) {//第一次比较4次，第二次比较3次，以此类推，共需要比较arr.length - 1次
17 if (arr[j] > arr[j + 1]) {
18 int temp = arr[j];
19 arr[j] = arr[j + 1];
20 arr[j + 1] = temp;
21 }
22 }
23 }
24 System.out.println("冒泡排序后：" + arrayToString(arr));
25 }
26 }
3、插入排序
1 /**
2 * 插入排序
3 * 原理：
4 * 1.从第一个元素开始，该元素可以认为已经被排序；
5 * 2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
6 * 3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
7 * 4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
8 * 5.将新元素插入到该位置后；
9 * 6.重复步骤2-5。
10 */
11 public class ChaRu {
12 public static void main(String[] args) {
13 int[] arr = {27, 12, 34, 22, 11};
14 System.out.println("排序前：" + arrayToString(arr));
15
16 for (int i = 0; i < arr.length; i++) {
17 for (int j = i; j > 0; j--) {
18 if (arr[j] < arr[j - 1]) {
19 int temp = arr[j - 1];
20 arr[j - 1] = arr[j];
21 arr[j] = temp;
22 }
23 }
24 }
25 System.out.println("排序后：" + arrayToString(arr));
26 }
27 }
4、选择排序
1 /**
2 * 选择排序
3 * 原理：
4 * 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
5 * 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
6 * 3.重复第二步，直到所有元素均排序完毕。
7 */
8 public class XuanZe {
9 public static void main(String[] args) {
10 int[] arr = new int[]{1, 6, 8, 9, 2, 3, 5, 4, 7};
11 System.out.println("排序前：" + arrayToString(arr));
12
13 for (int i = 0; i < arr.length - 1; i++) {//每次循环都会找出最小的数
14 int minIndex = i;//记录最小数的下标
15 int minNum = arr[i];//记录最小数
16 for (int j = i + 1; j < arr.length; j++) {//每次循环都会找出最小的数
17 if (arr[j] < minNum) {//如果当前数比最小数小，则更新最小数
18 minNum = arr[j];//更新最小数
19 minIndex = j;//更新最小数的下标
20 }
21 }
22 arr[minIndex] = arr[i];//将最小数放到最前面
23 arr[i] = minNum;//将标志位放到最小数原来所在的位置
24 }
25 System.out.println("排序后：" + arrayToString(arr));
26 }
27 }
5、希尔排序
1 /**
2 * 希尔排序
3 * 原理：
4 * 1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
5 * 2.按增量序列个数 k，对序列进行 k 趟排序；
6 * 3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
7 */
8 public class XiEr {
9 public static void main(String[] args) {
10 int[] arr = new int[]{8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
11 System.out.println("希尔排序前：" + arrayToString(arr));
12
13 ShellSort_swap(arr);
14 // ShellSort_move(arr);
15 System.out.println("希尔排序后：" + arrayToString(arr));
16
17 }
18
19
20 //交换式希尔排序
21 public static void ShellSort_swap(int[] arr) {
22 int temp = 0;
23 for (int gap = arr.length / 2; gap > 0; gap /= 2) {
24 for (int i = gap; i < arr.length; i++) {
25 //步长为5（每组有两个元素）
26 for (int j = i - gap; j >= 0; j -= gap) {
27 //如果当前元素大于加上步长后的那个元素，则交换
28 if (arr[j] > arr[j + gap]) {
29 temp = arr[j];
30 arr[j] = arr[j + gap];
31 arr[j + gap] = temp;
32 }
33 }
34 }
35 }
36 }
6、归并排序
1 /**
2 * 归并排序
3 * 原理：
4 * 1、将一个数组拆分为两个，从中间点拆开，通过递归操作来实现一层一层拆分。
5 * 2、从左右数组中选择小的元素放入到临时空间，并移动下标到下一位置。
6 * 3、重复步骤2直到某一下标达到尾部。
7 * 4、将另一序列剩下的所有元素依次放入临时空间。
8 * 5、将临时空间的数据依次放入原数据数组。
9 */
10 public class GuiBing {
11 public static void main(String[] args) {
12 // int[] arr = {1};
13 int[] arr = {1, 4, 7, 8, 3};
14 // int[] arr = {3, 0, 6, 4, 1, 3, 7, 8, 5, 9};
15 System.out.println("归并排序前：" + arrayToString(arr));
16 sort(arr, 0, arr.length - 1);
17 System.out.println("归并排序后：" + arrayToString(arr));
18 }
19
20 public static void sort(int[] arr, int left, int right) {
21 if (left == right) {
22 // System.out.println(right);
23 return;
24 }
25 //分成两半
26 int mid = left + (right - left) / 2;
27 //左边排序
28 sort(arr, left, mid);
29 //右边排序
30 // System.out.println(right);
31 sort(arr, mid + 1, right);
32
33 merge(arr, left, mid + 1, right);
34 }
35
36 /**
37 * @param arr
38 * @param leftPtr 数组最左边
39 * @param rightBound 数组中间
40 * @param rightPtr 数组最右边
41 */
42 static void merge(int[] arr, int leftPtr, int rightBound, int rightPtr) {
43 int mid = rightBound - 1;
44 int[] temp = new int[rightPtr - leftPtr + 1];
45
46 int i = leftPtr;
47 int j = rightBound;
48 int k = 0;
49
50 while (i <= mid && j <= rightPtr) {
51 if (arr[i] <= arr[j]) {
52 temp[k] = arr[i];
53 i++;
54 k++;
55 } else {
56 temp[k] = arr[j];
57 j++;
58 k++;
59 }
60 }
61
62 // 将右边剩余的归并
63 while (i <= mid) {
64 temp[k++] = arr[i++];
65 }
66 //将左边剩余的归并
67 while (j <= rightPtr) {
68 temp[k++] = arr[j++];
69
70 }
71
72 for (int m = 0; m < temp.length; m++) {
73 arr[leftPtr + m] = temp[m];
74 }
75 }
76 }
7、快速排序
1 /**
2 * 快速排序
3 * 原理：
4 * 1．先从数列中取出一个数作为基准数。
5 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
6 * 3．再对左右区间重复第二步，直到各区间只有一个数。
7 * 虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。
8 * 因此我的对快速排序作了进一步的说明：挖坑填数+分治法
9 */
10 public class KuaiSu {
11 public static void main(String[] args) {
12 int[] arr = {56, 12, 45, 34, 67, 1, 78, 90, 68, 14};
13 System.out.println("快速排序前：" + arrayToString(arr));
14
15 quickSort(arr,0,arr.length - 1);
16 System.out.println("快速排序后："+arrayToString(arr));
17 }
18
19 /**
20 * 分区过程
21 * a[] 待分区数组
22 * left 待分区数组最小下标
23 * right 待分区数组最大下标
24 */
25 public static void quickSort(int[] a,int left,int right) {
26 if(left<right) {
27 int temp = qSort(a, left, right);
28 quickSort(a,left,temp-1);
29 quickSort(a,temp+1,right);
30 }
31 }
32 /**
33 * 排序过程
34 * a 待排序数组
35 * left 待排序数组最小下标
36 * right 待排序数组最大下标
37 * @return 排好序之后基准数的位置下标，方便下次的分区
38 */
39 public static int qSort(int[] a,int left,int right) {
40 int temp=a[left];//定义基准数，默认为数组的第一个元素
41 while(left<right) {//循环执行的条件
42 //因为默认的基准数是在最左边，所以首先从右边开始比较进入while循环的判断条件
43 //如果当前arr[right]比基准数大，则直接将右指针左移一位，当然还要保证left<right
44 while(left<right && a[right]>temp) {
45 right--;
46 }
47 //跳出循环说明当前的arr[right]比基准数要小，那么直接将当前数移动到基准数所在的位置，并且左指针向右移一位（left++）
48 //这时当前数（arr[right]）所在的位置空出，需要从左边找一个比基准数大的数来填充。
49 if(left<right) {
50 a[left++]=a[right];
51 }
52 //下面的步骤是为了在左边找到比基准数大的数填充到right的位置。
53 //因为现在需要填充的位置在右边，所以左边的指针移动，如果arr[left]小于或者等于基准数，则直接将左指针右移一位
54 while(left<right && a[left]<=temp) {
55 left++;
56 }
57 //跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
58 if(left<right) {
59 a[right--]=a[left];
60 }
61 }
62 //当循环结束说明左指针和右指针已经相遇。并且相遇的位置是一个空出的位置，
63 //这时候将基准数填入该位置，并返回该位置的下标，为分区做准备。
64 a[left]=temp;
65 return left;
66 }
67 }
8、桶排序
1 /**
2 * 桶排序
3 * 原理：
4 * 1、遍历原始数组，找到数组中的最大值
5 * 2、创建一个下标为原始数组中最大值的桶数组,该桶数组的下标代表元素，该数组下标所对应的值代表这个值出现的次数
6 * 3、再次遍历原始数组，得到原数组中存在的各个元素，以及出现的次数
7 * 4、遍历桶数组,外层循环从桶的第一位开始（即下表为零）；内层循环遍历桶数组中下标为i的值出现的次数
8 */
9 public class Tong {
10 public static void main(String[] args) {
11 int[] arr = {3, 4, 1, 3, 2, 5, 4, 2, 7, 0};
12 System.out.println("桶排序前：" + arrayToString(arr));
13 bucketSort(arr);
14 System.out.println("桶排序后：" + arrayToString(arr));
15 }
16
17 public static void bucketSort(int[] num) {
18
19 // 遍历原始数组，找到数组中的最大值
20 int max = num[0];
21 for (int i = 0; i < num.length; i++) {
22 if (num[i] > max) {
23 max = num[i];
24 }
25 }
26
27 // 创建一个下标为原始数组中最大值的桶数组,该桶数组的下标代表元素，该数组下标所对应的值代表这个值出现的次数
28 int[] bucketArray = new int[max + 1];
29
30 // 再次遍历原始数组，得到原数组中存在的各个元素，以及出现的次数
31 for (int i = 0; i < num.length; i++) {
32 bucketArray[num[i]]++;
33 }
34
35 // 遍历桶数组,外层循环从桶的第一位开始（即下表为零）；内层循环遍历桶数组中下标为i的值出现的次数
36 int index = 0;
37 for (int i = 0; i < bucketArray.length; i++) {
38 for (int j = 0; j < bucketArray[i]; j++) {
39 num[index++] = i;
40 }
41 }
42 }
43 }
9、基数排序
1 /**
2 * 基数排序（利用基本原理进行排序）
3 * 原理：
4 * 1.取得数组中的最大数，并取得位数；
5 * 2.arr为原始数组，从最低位开始取每个位组成radix数组；
6 * 3.对radix进行计数排序（利用计数排序适用于小范围数的特点）。
7 */
8 public class Base {
9 public static void main(String[] args) {
10 int[] arr = {134, 256, 12, 54, 756};
11 System.out.println("基数排序前：" + arrayToString(arr));
12 radixSort(arr);
13 System.out.println("基数排序后：" + arrayToString(arr));
14 }
15
16 public static void radixSort(int[] arr) {
17
18 int max = arr[0];//假设第一个数就是最大数
19 for (int i = 1; i < arr.length; i++) {
20 if (arr[i] > max) {
21 max = arr[i];
22 }
23 }
24 int maxLength = (max + " ").length();
25 //第一轮（针对每个元素的个位进行排序处理）
26
27 //定义一个二维数组，表示10个桶，每个桶就是一维数组
28 //说明：
29 //1.二维数组包含10个一维数组
30 //2.为了防止在放入数的时候，数据溢出，则每个一个数组（桶），大小定为arr.length
31 //3明显，基数排序是使用空间换时间
32 int[][] bucket = new int[10][arr.length];
33
34 //为了记录每个桶中，实际存放了多少个数据，我们定义了一个一维数组来记录各个桶中的个数
35 int[] bucketElementCounts = new int[10];
36
37 for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
38 for (int j = 0; j < arr.length; j++) {
39 //取出每个元素的对应位的值进行排序处理，第一次是个位，第二次是十位。。。
40 int digitOfElement = arr[j] / n % 10;
41 //放入到对应的桶中
42 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
43 bucketElementCounts[digitOfElement]++;
44 }
45
46 //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数组）
47 int index = 0;
48 //遍历每一桶，并将桶中的数据，放入到原数组
49 for (int k = 0; k < bucketElementCounts.length; k++) {
50 //如果桶中，有数据，我们才能放入到原数组
51 if (bucketElementCounts[k] != 0) {
52 //循环该桶即第k个桶，（即第k个一维数组），放入
53 for (int l = 0; l < bucketElementCounts[k]; l++) {
54 //取出元素放入arr
55 arr[index] = bucket[k][l];
56 index++;
57 }
58 }
59 //第i+1轮处理后，需要将每个bucketElementCounts[k]=0!!!
60 bucketElementCounts[k] = 0;
61 }
62 }
63 }
64 }
10、计数排序
1 /**
2 * 计数排序
3 * 原理：
4 * https://blog.csdn.net/allway2/article/details/114003894
5 */
6 import static com.itheima08.paixu.ArrayToString.arrayToString;
7
8 public class JiShu {
9 public static void main(String[] args) {
10 int[] array = {0, 2, 2, 1, 4, 4, 5, 1, 7};
11 System.out.println("计数排序前：" + arrayToString(array));
12 int max = findMaxElement(array);//找数组中最大数
13 System.out.println("数组中最大数是：" + max);
14 int[] after = countingSort(array, max + 1);
15 System.out.println("计数排序后：" + arrayToString(after));
16 }
17
18 private static int findMaxElement(int[] array) {
19 int max = array[0];
20 for (int val : array) {
21 if (val > max) max = val;
22 }
23 return max;
24 }
25
26 private static int[] countingSort(int[] array, int range) {
27 int[] output = new int[array.length];
28 int[] count = new int[range];
29 // Calculate frequency of each element, put it in count array
30 for (int i = 0; i < array.length; i++) {
31 count[array[i]]++;
32 }
33 System.out.println("计数数组是：" + arrayToString(count));
34
35 // Modify count array to get the final position of elements
36 for (int i = 1; i < range; i++) {
37 count[i] = count[i] + count[i - 1];
38 }
39 System.out.println("统计总数数组是：" + arrayToString(count));
40
41 // Add elements to output sorted array
42 for (int i = 0; i < array.length; i++) {
43 output[count[array[i]] - 1] = array[i];
44 count[array[i]]--;
45 }
46 return output;
47 }
48 }
11、堆排序（大顶堆和小顶堆）
1）大顶堆
1 /**
2 * 堆排序（升序：大顶堆）
3 * 原理：
4 * 1、根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
5 * 2、每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
6 */
7 public class BigDui {
8 public static void main(String[] args) {
9 int[] arr = {6, 2, 7, 4, 1, 9, 3};
10 System.out.println("大顶堆排序前：" + arrayToString(arr));
11
12 sort(arr);
13 System.out.println("大顶堆排序后：" + arrayToString(arr));
14 }
15
16 public static void sort(int[] arr) {
17 //1.构建大顶堆
18 for (int i = arr.length / 2 - 1; i >= 0; i--) {
19 //从第一个非叶子结点从下至上，从右至左调整结构
20 adjustHeap(arr, i, arr.length);
21 }
22 //2.调整堆结构+交换堆顶元素与末尾元素
23 for (int j = arr.length - 1; j > 0; j--) {
24 swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
25 adjustHeap(arr, 0, j);//重新对堆进行调整
26 }
27
28 }
29
30 /**
31 * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
32 *
33 * @param arr
34 * @param i
35 * @param length
36 */
37 public static void adjustHeap(int[] arr, int i, int length) {
38 int temp = arr[i];//先取出当前元素i
39 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
40 if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
41 k++;
42 }
43 if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
44 arr[i] = arr[k];
45 i = k;
46 } else {
47 break;
48 }
49 }
50 arr[i] = temp;//将temp值放到最终的位置
51 }
52
53 /**
54 * 交换元素
55 *
56 * @param arr
57 * @param a
58 * @param b
59 */
60 public static void swap(int[] arr, int a, int b) {
61 int temp = arr[a];
62 arr[a] = arr[b];
63 arr[b] = temp;
64 }
65 }
2）小顶堆
1 /**
2 * 堆排序：（降序：小顶堆）
3 * 原理：
4 * 1、根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
5 * 2、每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
6 */
7 public class SmallDui {
8 public static void main(String[] args) {
9 int[] arr = {-5, 6, 2, 7, 4, 1, 9, 3, -1};
10 System.out.println("小顶堆排序前：" + arrayToString(arr));
11
12 sort(arr);
13 System.out.println("小顶堆排序后：" + arrayToString(arr));
14 }
15
16 public static void sort(int[] arr) {
17 //1.构建小顶堆
18 for (int i = arr.length / 2 - 1; i >= 0; i--) {
19 //从第一个非叶子结点从下至上，从右至左调整结构
20 adjustHeap(arr, i, arr.length);
21 }
22 //2.调整堆结构+交换堆顶元素与末尾元素
23 for (int j = arr.length - 1; j > 0; j--) {
24 swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
25 adjustHeap(arr, 0, j);//重新对堆进行调整
26 }
27 }
28
29 /**
30 * 调整小顶堆（仅是调整过程，建立在小顶堆已构建的基础上）
31 *
32 * @param arr
33 * @param i
34 * @param length
35 */
36 public static void adjustHeap(int[] arr, int i, int length) {
37 int temp = arr[i];//先取出当前元素i
38 for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
39 if (k + 1 < length && arr[k] > arr[k + 1]) {//如果左子结点大于右子结点，k指向右子结点
40 k++;
41 }
42 if (arr[k] < temp) {//如果子节点小于父节点，将子节点值赋给父节点（不用进行交换）
43 arr[i] = arr[k];
44 i = k;
45 } else {
46 break;
47 }
48 }
49 arr[i] = temp;//将temp值放到最终的位置
50 }
51
52 /**
53 * 交换元素
54 *
55 * @param arr
56 * @param a
57 * @param b
58 */
59 public static void swap(int[] arr, int a, int b) {
60 int temp = arr[a];
61 arr[a] = arr[b];
62 arr[b] = temp;
63 }
64 }
注：仅用于学习
标签：arr,十大,int,算法,length,数组,排序,public From： https://www.cnblogs.com/it-java-ls/p/17029203.html