1.冒泡排序
package com.leay; public class BubbleSort { public static int[] sort(int[] arr) { for (int i = arr.length - 1; i > 0; i--) { for (int j = 0; j <= i - 1; j++) { if (arr[j] > arr[i]) { swap(arr, i, j); } } } return arr; } public static void swap(int[] arr, int i, int j) { int swap = arr[i]; arr[i] = arr[j]; arr[j] = swap; } public static void print(int[] arr) { String printStr = ""; for (int i : arr) { printStr = printStr + i + ","; } System.out.println(printStr); } public static void main(String[] args) { Random random = new Random(0); random.ints(-100, 100); int[] arr = new int[20]; for (int i = 0; i < arr.length; i++) { arr[i] = random.nextInt(100); } print(arr); print(sort(arr)); } }
2.插入排序
package com.leay; import java.util.Objects; public class InsertSort { public static int[] sort(int[] arr) { if (Objects.isNull(arr) || arr.length <= 1) { return arr; } for (int i = 1; i < arr.length; i++) { int j = i - 1; while (j >= 0 && arr[j] > arr[j + 1]) { swap(arr, j, j + 1); j--; } } return arr; } }
3.希尔排序
package com.leay; public class ShellSort { // 相邻间隔有序 public static int[] sort(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { int j = i; while (j - gap >= 0 && arr[j - gap] > arr[j]) { Utils.swap(arr, j - gap, j); j = j - gap; } } } return arr; } }
4.快速排序
package com.leay; public class QuickSort { public static void sort(int[] arr, int left, int right) { if (left > right) { return; } // 去除当前最后一个元素 int temp = arr[right]; int l = left; int r = right - 1; // 当前l比temp大 r比temp小 while (l <= r) { while (l <= r && arr[r] > temp) { r--; } while (l <= r && arr[l] < temp) { l++; } if (l <= r) { swap(arr, l, r); l++; r--; } } swap(arr, l, right); sort(arr, left, l - 1); sort(arr, l + 1, right); } }
5.归并排序
package com.leay; public class MergeSort { public static int[] sort(int[] arr, int low, int high) { if (low >= high) { return arr; } int mid = (high + low) / 2; sort(arr, low, mid); sort(arr, mid + 1, high); int[] temp = new int[high - low + 1]; int left = low; int right = mid + 1; int cur = 0; while (left <= mid && right <= high) { if (arr[left] < arr[right]) { temp[cur++] = arr[left++]; } else if (arr[left] > arr[right]) { temp[cur++] = arr[right++]; } else { temp[cur++] = arr[left++]; temp[cur++] = arr[right++]; } } while (left <= mid) { temp[cur++] = arr[left++]; } while (right <= high) { temp[cur++] = arr[right++]; } for (int i = 0; i < temp.length; i++) { arr[i + low] = temp[i]; } return arr; } }
6.堆排序
package com.leay; public class HeapSort { // 创建一个大根堆 public static int[] heapInsert(int[] arr) { // 比parent节点大的往上走 int parent; for (int i = 0; i < arr.length; i++) { parent = (i - 1) / 2; while (i > 0 && arr[parent] < arr[i]) { swap(arr, parent, i); i = parent; parent = (parent - 1) / 2; } } return arr; } // 当前节点的子节点的最大值是否大于当前父节点如果大于就交换 public static void heapAdjust(int[] arr, int end) { int parent = 0; while (parent < end) { int maxSon = 2 * parent + 1 >= end ? parent : 2 * parent + 2 >= end || arr[2 * parent + 1] > arr[2 * parent + 2] ? 2 * parent + 1 : 2 * parent + 2; int max = arr[maxSon] > arr[parent] ? maxSon : parent; if (max == parent) { break; } swap(arr, parent, max); parent = max; } } public static int[] sort(int[] arr) { if (arr.length <= 1) { return arr; } heapInsert(arr); swap(arr, 0, arr.length - 1); for (int i = arr.length - 1; i > 1; i--) { heapAdjust(arr, i); swap(arr, 0, i - 1); } return arr; } }
7.桶排序
package com.leay; import java.util.ArrayList; import java.util.List; public class BucketSort { public static int[] sort(int[] arr) { int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; // 计算桶的个数 for (int i : arr) { min = Math.min(min, i); max = Math.max(max, i); } int size = max - min + 1; // 初始化桶 ArrayList[] bucketList = new ArrayList[size]; for (int i = 0; i < size; i++) { bucketList[i] = new ArrayList(); } // 元素放到指定的桶中 for (int item : arr) { int index = item-min; bucketList[index].add(item); } int i = 0; for (ArrayList bucket : bucketList) { for (int temp : bucket) { arr[i++] = temp; } } return arr; } }
8.选择排序
package com.leay; public class SelectionSort { public static int[] sort(int[] arr) { for (int i = arr.length - 1; i >= 1; i--) { for (int j = i - 1; j >= 0; j--) { if (arr[j] > arr[i]) { swap(arr, i, j); } } } return arr; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)