Java基础学习笔记：补充内容5 十大排序的图示

一、简单选择排序

public class SelectSort { public static void selectSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { for (int j = i + 1; j < arrayLength; j++) { if (data[i] - data[j] > 0) { int temp = data[i]; data[i] = data[j]; data[j] = temp; } } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } public class SelectSort2 { public static void selectSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { int minIndex = i; for (int j = i + 1; j < arrayLength; j++) { if (data[minIndex] - data[j] > 0) { minIndex = j; } } if(minIndex != i){ int temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); selectSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

二、直接插入排序

public class InsertSort { public static void insertSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 1; i < arrayLength; i++) { int temp = data[i]; if (data[i] - data[i - 1] < 0) { int j = i - 1; for (; j >= 0 && data[j] - temp > 0; j--) { data[j + 1] = data[j]; } data[j + 1] = temp; } System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); insertSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } } /** * 折半插入排序 * */ public class BinaryInsertSort { public static void binaryInsertSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 1; i < arrayLength; i++) { int temp = data[i]; int low = 0; int high = i - 1; while (low <= high) { int mid = (low + high) / 2; if (temp > data[mid]) { low = mid + 1; } else { high = mid - 1; } } for (int j = i; j > low; j--) { data[j] = data[j - 1]; } data[low] = temp; System.out.println(java.util.Arrays.toString(data)); } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); binaryInsertSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

三、堆排序

public class HeapSort { public static void heapSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; // 循环建堆 for (int i = 0; i < arrayLength - 1; i++) { // 建堆 buildMaxdHeap(data, arrayLength - 1 - i); // 交换堆顶和最后一个元素 swap(data, 0, arrayLength - 1 - i); System.out.println(java.util.Arrays.toString(data)); } } // 对data数组从0到lastIndex建大顶堆 private static void buildMaxdHeap(int[] data, int lastIndex) { // 从lastIndex处节点（最后一个节点）的父节点开始 for (int i = (lastIndex - 1) / 2; i >= 0; i--) { // k保存当前正在判断的节点 int k = i; // 如果当前k节点的子节点存在 while (k * 2 + 1 <= lastIndex) { // k节点的左子节点的索引 int biggerIndex = 2 * k + 1; // 如果biggerIndex小于lastIndex，即biggerIndex +1 // 代表k节点的右子节点存在 if (biggerIndex < lastIndex) { // 如果右子节点的值较大 if (data[biggerIndex] - data[biggerIndex + 1] < 0) { // biggerIndex总是记录较大子节点的索引 biggerIndex++; } } // 如果k节点的值小于其较大子节点的值 if (data[k] - data[biggerIndex] < 0) { // 交换它们 swap(data, k, biggerIndex); // 将biggerIndex赋给k，开始while循环的下一次循环 // 重新保证k节点的值大于其左、右节点的值 k = biggerIndex; } else { break; } } } } // 交换data数组中i、j两个索引处的元素 private static void swap(int[] data, int i, int j) { int temp = data[i]; data[i] = data[j]; data[j] = temp; } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); heapSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

四、归并排序

public class MergeSort { public static void mergeSort(int[] data) { // 归并排序 sort(data, 0, data.length - 1); } // 将索引从left到right范围的数组元素进行归并排序 private static void sort(int[] data, int left, int right) { if(left < right){ //找出中间索引 int center = (left + right)/2; sort(data,left,center); sort(data,center+1,right); //合并 merge(data,left,center,right); } } // 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序 private static void merge(int[] data, int left, int center, int right) { int[] tempArr = new int[data.length]; int mid = center + 1; int third = left; int temp = left; while (left <= center && mid <= right) { if (data[left] - data[mid] <= 0) { tempArr[third++] = data[left++]; } else { tempArr[third++] = data[mid++]; } } while (mid <= right) { tempArr[third++] = data[mid++]; } while (left <= center) { tempArr[third++] = data[left++]; } while (temp <= right) { data[temp] = tempArr[temp++]; } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); mergeSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

五、基数排序

public class MultiKeyRadixSort { public static void radixSort(int[] data, int radix, int d) { System.out.println("开始排序："); int arrayLength = data.length; int[] temp = new int[arrayLength]; int[] buckets = new int[radix]; for (int i = 0, rate = 1; i < d; i++) { // 重置count数组，开始统计第二个关键字 Arrays.fill(buckets, 0); // 当data数组的元素复制到temp数组中进行缓存 System.arraycopy(data, 0, temp, 0, arrayLength); for (int j = 0; j < arrayLength; j++) { int subKey = (temp[j] / rate) % radix; buckets[subKey]++; } for (int j = 1; j < radix; j++) { buckets[j] = buckets[j] + buckets[j - 1]; } for (int m = arrayLength - 1; m >= 0; m--) { int subKey = (temp[m] / rate) % radix; data[--buckets[subKey]] = temp[m]; } System.out.println("对" + rate + "位上子关键字排序：" + java.util.Arrays.toString(data)); rate *= radix; } } public static void main(String[] args) { int[] data = { 1100, 192, 221, 12, 13 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); radixSort(data, 10, 4); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

六、计数排序

七、快速排序

/** * 快速排序 * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小， * 则分别对这两部分继续进行排序，直到整个序列有序。 */ public class QuickSort { private static void swap(int[] data, int i, int j) { int temp = data[i]; data[i] = data[j]; data[j] = temp; } private static void subSort(int[] data, int start, int end) { if (start < end) { int base = data[start]; int low = start; int high = end + 1; while (true) { while (low < end && data[++low] - base <= 0) ; while (high > start && data[--high] - base >= 0) ; if (low < high) { swap(data, low, high); } else { break; } } swap(data, start, high); subSort(data, start, high - 1);//递归调用 subSort(data, high + 1, end); } } public static void quickSort(int[] data){ subSort(data,0,data.length-1); } public static void main(String[] args) { int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); quickSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

八、冒泡排序

/** * 冒泡排序 * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 * 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 * 针对所有的元素重复以上的步骤，除了最后一个。 * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较 * */ public class BubbleSort { public static void bubbleSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { for (int j = 0; j < arrayLength - 1 - i; j++) { if (data[j] > data[j + 1]) { int temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; } } System.out.println(java.util.Arrays.toString(data)); } } //优化1 public static void bubbleSort1(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; for (int i = 0; i < arrayLength - 1; i++) { boolean flag = false; for (int j = 0; j < arrayLength - 1 - i; j++) { if (data[j] > data[j + 1]) { int temp = data[j + 1]; data[j + 1] = data[j]; data[j] = temp; flag = true; } } System.out.println(java.util.Arrays.toString(data)); if (!flag) break; } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); bubbleSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

九、桶排序

/** * 桶式排序 * */ public class BucketSort { public static void bucketSort(int[] data, int min, int max) { System.out.println("开始排序"); int arrayLength = data.length; int[] temp = new int[arrayLength]; int[] buckets = new int[max - min]; for (int i = 0; i < arrayLength; i++) { buckets[data[i] - min]++; } System.out.println(Arrays.toString(buckets)); for (int i = 1; i < max - min; i++) { buckets[i] = buckets[i] + buckets[i - 1]; } System.out.println(Arrays.toString(buckets)); System.arraycopy(data, 0, temp, 0, arrayLength); for (int k = arrayLength - 1; k >= 0; k--) { data[--buckets[temp[k] - min]] = temp[k]; } } public static void main(String[] args) { int[] data = { 9, 5, -1, 8, 5, 7, 3, -3, 1, 3 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); bucketSort(data, -3, 10); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }

十、希尔排序

/** * Shell排序 */ public class ShellSort { public static void ShellSort(int[] data) { System.out.println("开始排序"); int arrayLength = data.length; int h = 1; while (h <= arrayLength / 3) { h = h * 3 + 1; } while (h > 0) { System.out.println("===h的值：" + h + "==="); for (int i = h; i < arrayLength; i++) { int temp = data[i]; if (data[i] - data[i - h] < 0) { int j = i - h; for (; j >= 0 && data[j] - temp > 0; j -= h) { data[j + h] = data[j]; } data[j + h] = temp; } System.out.println(java.util.Arrays.toString(data)); } h = (h - 1) / 3; } } public static void main(String[] args) { int[] data = { 9, -16, 21, 23, -30, -49, 21, 30, 30 }; System.out.println("排序之前：\n" + java.util.Arrays.toString(data)); ShellSort(data); System.out.println("排序之后：\n" + java.util.Arrays.toString(data)); } }