重温数据结构和算法 Sorts 2019-03-11 bubbleSort & insertionSort & selectionSort & MergeSort & quickSort & CountingSort bubbleSort & insertionSort & selectionSort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192package Sort;/** * @Author: Leooel * @Date: 2019/3/11 9:07 */public class Sorts { // 冒泡排序,a 是数组,n 是数组大小 public static void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前结束循环的标志 boolean flag = false; for (int j = i; j < n - i - 1; ++j) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; flag = true; } } // 没有数据交换,排序已完成,提前停止冒泡 if (flag == false) break; } } // 插入排序,a 是数组,n 是数组大小 public static void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找要插入的位置,并迅速移动 for (; j >= 0; --j) { if (a[j] > value) { a[j + 1] = a[j]; } else { break; } } a[j + 1] = value; } } // 选择排序,a 是数组,n 是数组大小 public static void selectionSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 查找最小值 int minIndex = i; for (int j = i + 1; j < n; ++j) { if (a[j] < a[minIndex]) { minIndex = j; } } // 交换数值 int temp = a[i]; a[i] = a[minIndex]; a[minIndex] = temp; } } public void printAll(int[] a, int n) { for (int i = 0; i < n; ++i) { System.out.print(a[i] + " "); } System.out.println(); } public static void main(String[] args) { Sorts object = new Sorts(); int[] a = new int [4]; a[0] = 1; a[1] = 4; a[2] = 3; a[3] = 2; object.printAll(a, 4); object.bubbleSort(a, 4); // object.selectionSort(a, 4); // object.insertionSort(a, 4); object.printAll(a, 4); }} MergeSort12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788package Sort;/** * @Author: Leooel * @Date: 2019/3/9 10:36 */public class MergeSort { // 归并排序算法, a 是数组,n 表示数组大小 public static void mergeSort(int[] a, int n) { mergeSortInternally(a, 0, n - 1); } // 递归调用函数 private static void mergeSortInternally(int[] a, int p, int r) { // 递归终止条件 if (p >= r) return; // 取 p 到 r 之间的中间位置 q,防止 (p + r) 的和超过 int 类型最大值 int q = p + (r - p) / 2; // 分治递归 mergeSortInternally(a, p, q); mergeSortInternally(a, q + 1, r); // 合并 merge(a, p, q, r); } private static void merge(int[] a, int p, int q, int r) { // 初始 i,j,k int i = p; int j = q + 1; int k = 0; // 申请一个跟原数组 a 一样大的临时数组 tmp int[] tmp = new int[r - p + 1]; while (i <= q && j <= r) { if (a[i] <= a[j]) { tmp[k++] = a[i++]; } else { tmp[k++] = a[j++]; } } // 判断哪个子数组还有剩余数据 int start = i; int end = q; if (j <= r) { start = j; end = r; } // 将剩余数据拷贝到临时数组 tmp while (start <= end) { tmp[k++] = a[start++]; } // 将 tmp 中的数据拷回原数组 a for (i = 0; i <= r - p; ++i) { a[p + i] = tmp[i]; } } public void printAll(int[] a, int n) { for (int i = 0; i < n; ++i) { System.out.print(a[i] + " "); } System.out.println(); } public static void main(String[] args) { MergeSort object = new MergeSort(); int[] a = new int [4]; a[0] = 1; a[1] = 4; a[2] = 3; a[3] = 2; object.printAll(a, 4); object.mergeSort(a, 4); object.printAll(a, 4); }} quickSort1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768package Sort;/** * @Author: Leooel * @Date: 2019/3/9 12:31 */public class QuickSort { // 快速排序,a 是数组,n 表示数组的大小 public static void quickSort(int[] a, int n) { quickSortInternally(a, 0, n - 1); } // 快速排序递归函数,p,r 为下标 private static void quickSortInternally(int[] a, int p, int r) { if (p >= r) return; // 获取分区点 int q = partition(a, p, r); quickSortInternally(a, p, q - 1); quickSortInternally(a, q + 1, r); } private static int partition(int[] a, int p, int r) { int pivot = a[r]; int i = p; for (int j = p; j < r; ++j) { if (a[j] < pivot) { if (i == j) { ++i; } else { int tmp = a[i]; a[i++] = a[j]; a[j] = tmp; } } } int tmp = a[i]; a[i] = a[r]; a[r] = tmp; System.out.println("i = " + i); return i; } public void printAll(int[] a, int n) { for (int i = 0; i < n; ++i) { System.out.print(a[i] + " "); } System.out.println(); } public static void main(String[] args) { QuickSort object = new QuickSort(); int[] a = new int [4]; a[0] = 1; a[1] = 4; a[2] = 3; a[3] = 2; object.printAll(a, 4); object.quickSort(a, 4); object.printAll(a, 4); }} CountingSort123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869package Sort;/** * @Author: Leooel * @Date: 2019/3/11 21:14 */public class CountingSort { // 计数排序,a 是数组, n 是数组大小;假设数组中存储的都是非负整数 public static void countingSort(int[] a, int n) { if (n <= 1) return; // 查找数组中数据的范围 int max = a[0]; for (int i = 1; i < n; ++i) { if (max < a[i]) { max = a[i]; } } // 申请一个计数数组 countArray, 下标大小 [0, max] int[] countArray = new int[max + 1]; for (int i = 0; i < max + 1; ++i) { countArray[i] = 0; } // 计算数组 a 中每个元素的个数,放入 countArray 数组中 for (int i = 0; i < n; ++i) { countArray[a[i]]++; } // 依次累加 for (int i = 1; i < max + 1; ++i) { countArray[i] = countArray[i] + countArray[i - 1]; } // 临时数组 tempArray, 存储排序之后的结果 int[] tempArray = new int[n]; // 计算排序的关键步骤 for (int i = n - 1; i >= 0; --i) { int index = countArray[a[i]] - 1; tempArray[index] = a[i]; countArray[a[i]]--; } // 将结果拷贝到数组 a for (int i = 0; i < n; ++i) { a[i] = tempArray[i]; } } public static void printAll(int[] a, int n) { for (int i = 0; i < n; ++i) { System.out.print(a[i] + " "); } System.out.println(); } public static void main(String[] args) { CountingSort object = new CountingSort(); int[] a = new int[]{5,7,4,1,6}; object.printAll(a, 5); object.countingSort(a, 5); object.printAll(a, 5); }} 赏 谢谢你请Leo吃糖果哦 支付宝 微信 数据结构与算法 扫一扫,分享到微信