冒泡排序
外层循环次数为集合元素数 - 1 (两两比较)
内层循环每次 -1 (每次循环确定最末尾数)
1 | public static void bubbleSort(int[] arr) { |
选择排序
默认首位数为最小,遍历后续元素,确定最小索引,交换数据
1 | public static void selectSort(int[] arr) { |
插入排序
默认从二号元素开始,左侧元素为有序列
遍历时若较左侧小的数,进行移动(类冒泡),否则直接进入下次外循环 (较左侧最近数大,则较有序列所有数大)
1 | public static void insertionSort(int[] a) { |
希尔排序
一种改进的插入排序
最外层循环为步长
1 | public static void shellSort(int[] arr) { |
快速排序
首先确定一个基数,将大于/小于他的数置于其两侧,再对左右两侧集合进行递归
1 | public static void quickSort(int[] arr, int start, int end) { |
归并排序
先进行递归,将列表进行拆分,首先从最小的切分集合进行排序,之后进行合并排序,最终合并排序为一个有序表
1 | public static void mergeSort(int[] arr, int start, int end) { |
堆排序
构建堆 (此处是升序排序,所以选择大顶堆)
- 从第一个非叶子结点从下至上,从右至左调整,将大数置于根节点 (根节点 > 子节点)
- 调整堆结构,持续交换堆顶元素与末尾元素,从尾部向头部逐渐递归出一个有序表
1 | class HeapSort { |
基数排序
此处是最低位优先 (Least Significant Digit first,LSD) 法,从个位开始,对数组进行排序
将对应位元素出现的次数存储在 buckets 中
buckets[i] += buckets[i - 1] 将 bucket 的值变为对应最后一个元素的索引 (此时buckets 为一个有序索引桶),每确定一个索引的元素将对应 bucket 的值 -1,将 bucket 存储的索引移动到对应的下一个索引
(实际上是索引 + 1,因为默认没有元素的 bucket 的值为 0,之后从 bucket 中取得索引需要 -1)
1 | public static void radixSort(int[] arr) { |