排序算法
排序算法
资料
冒泡排序
- 从后往前循环比较相邻两数，小数前大数后，一遍完成最小数即排在最前，最后循环排序
实现
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) return;
int index = arr.length - 1;
for (int i = 0; i < index; i++) {
for (int j = index; j > i; j--) { // 最小在最前
if (arr[j] < arr[j - 1]) { // 小在前大在后
exchange(arr, j, j - 1);
}
}
}
}
private static void exchange(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
简单选择排序
- 从前向后循环排序，查找最小数互换位置
实现
public static void selectSort(int[] arr) {
if (arr == null || arr.length == 0) return;
int minIndex;
int length = arr.length;
for (int i = 0; i < length - 1; i++) {
// 选择最小
minIndex = i;
for (int j = i + 1; j < length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 置最前
if (minIndex != i) {
exchange(arr, i, minIndex);
}
}
}
堆排序
- 使用二叉堆的特性，调整为大顶堆，选择最大值出堆，最后循环调整大顶堆出堆
特性
- 树是一对多的数据结构，从一个根结点开始，生长出它的子结点，而每一个子结点又生长出各自的子结点，成为子树。如果某个结点不再生长出子结点了，它就成为叶子。
- 二叉树每个结点最多只有两棵子树，而且左右子树是有顺序的，不可颠倒。
- 满二叉树的所有分支结点都既有左子树又有右子树，并且所有叶子都在同一层。
- 完全二叉树不一定是满的，但它自上而下，自左而右来看的话，是连续没有缺失的。
- 二叉堆是完全二叉树或者近似完全二叉树，父结点的值总是大于或等于(小于或等于)任何一个子节点的值。
- 存储为一维数组，子i父(i-1)/2，父i子2i+1和2i+2
- 入堆，末尾添加，尾元素比较上浮
- 出堆，首尾互换，首元素比较下沉，尾元素出堆
实现
public static void heapSort(int[] arr) {
if (arr == null || arr.length == 0) return;
int length = arr.length;
for (int i = length / 2 - 1; i >= 0; i--) { // 从最后一个元素的父开始整理，建立大顶堆
adjustMaxHeap(arr, i, length);
}
for (int i = length - 1; i > 0; i--) { // 堆出队列，首尾互换，最大置尾，堆调整
exchange(arr, 0, i);
adjustMaxHeap(arr, 0, i);
}
}
private static void adjustMaxHeap(int[] arr, int start, int end) {
int temp = arr[start];
int child = start * 2 + 1; // 左边子
while (child < end) {
if ((child + 1) < end && arr[child] < arr[child + 1]) { // 两子节点比较选大
child++; // 右边子
}
if (arr[child] <= temp) break; // 已是大顶堆
// 否则父沉子浮
arr[start] = arr[child];
// 再循环调整
start = child;
child = start * 2 + 1;
}
arr[start] = temp;
}
直接插入排序
- 分序列为左有序右无序，从第二个数开始向后循环，与有序序列循环比较大小确定位置插入
特性
- 如果序列基本有序或者长度较小时，使用直接插入排序效率就非常高
实现
public static void insertSort(int[] arr) {
if (arr == null || arr.length == 0) return;
int insertNum;
int length = arr.length;
for (int i = 1; i < length; i++) {
insertNum = arr[i]; // 无序序列第一个数，即需要插入的数
int j = i - 1; // 有序序列最后位置
while (j >= 0 && arr[j] > insertNum) { // 大则后移
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = insertNum;
}
}
二分插入排序
- 分序列为左有序右无序，从第二个数开始向后循环，在有序序列中二分查找确定位置插入
实现
public static void binarySort(int[] arr) {
if (arr == null || arr.length == 0) return;
int insertNum;
int length = arr.length;
for (int i = 1; i < length; i++) {
insertNum = arr[i]; // 无序序列第一个数，即需要插入的数
// 二分查找
int left = 0; // 插入位置
int right = i - 1; // 有序序列最后位置
for (int middle; left <= right; ) {
middle = left + (right - left) / 2;
if (arr[middle] < insertNum) {
left = middle + 1;
} else if (arr[middle] > insertNum) {
right = middle - 1;
} else {
left = middle + 1;
break;
}
}
// 批量后移
for (int j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = insertNum;
}
}
希尔排序
- 增量分组，组内插入排序，然后增量二分缩减再插入排序，最后循环缩减增量至一
特性
- 时间复杂度可以达到O(n^1.3)
实现
public static void shellSort(int[] arr) {
if (arr == null || arr.length == 0) return;
for (int step = arr.length / 2; step >= 1; step /= 2) { // 增量分组
for (int i = 0; i < step; i++) { // 组内插入排序
insertSort(arr, step);
}
}
}
private static void insertSort(int[] arr, int step) {
int insertNum;
int length = arr.length;
for (int i = step; i < length; i += step) {
insertNum = arr[i]; // 无序序列第一个数，即需要插入的数
int j = i - step; // 有序序列最后一个数
while (j >= 0 && arr[j] > insertNum) { // 大则后移
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = insertNum;
}
}
快速排序
- 确定首数为基准数比较大小，从右往左循环小数换位，从左往右循环大数换位，循环至中间相遇位置置为基准数，最后以中间位置分左右两个序列递归
实现
public static void quickSort(int[] arr) {
if (arr == null || arr.length == 0) return;
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int start, int end) {
if (start >= end) return;
int baseNumber = arr[start]; // 基准数
int left = start, right = end;
while (left < right) {
while (left < right && arr[right] >= baseNumber) right--; // 右边寻找小与基准数
if (left < right) arr[left++] = arr[right]; // 小数左移
while (left < right && arr[left] <= baseNumber) left++; // 左边寻找大于基准数
if (left < right) arr[right--] = arr[left]; // 大数右移
}
arr[left] = baseNumber; // 基准赋值
// 分开递归
quickSort(arr, start, left - 1);
quickSort(arr, left + 1, end);
}
归并排序
- 二分序列归并排序，最后比较大小合并
特性
- 使用了递归分治的思想，先递归划分子问题，然后合并结果
实现
public static void mergeSort(int[] arr) {
if (arr == null || arr.length == 0) return;
mergeSort(arr, 0, arr.length - 1);
}
private static void mergeSort(int[] arr, int start, int end) {
if (start >= end) return;
// 二分递归
int middle = (start + end) / 2;
mergeSort(arr, start, middle);
mergeSort(arr, middle + 1, end);
merge(arr, start, middle, end); // 合并
}
private static void merge(int[] arr, int start, int middle, int end) {
int left = start, right = middle + 1;
int length = end - start + 1;
int[] temp = new int[length]; // 临时数组
// 存入临时数组
int index = 0;
while (left <= middle && right <= end) { // 左右两数组比较，小的存入
temp[index++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
}
// 剩下的存入临时数组
while (left <= middle) {
temp[index++] = arr[left++];
}
while (right <= end) {
temp[index++] = arr[right++];
}
// 还原
for (int i = 0; i < length; i++) {
arr[start + i] = temp[i];
}
}
计数排序
- 序列的值作为计数数组的下标，统计每个数字的个数，最后依次输出计数数组的下标
特性
- 待排序的数要满足一定的范围的正整数
- 计数排序需要比较多的辅助空间
- 时间复杂度为O(n)
实现
public static void countSort(int[] arr) {
if (arr == null || arr.length == 0) return;
// 以值为脚标建立计数数组
int max = 0;
for (int item : arr) {
if (item > max) max = item;
}
// 映射分配，排序
int[] count = new int[max + 1];
Arrays.fill(count, 0);
for (int i : arr) {
count[i]++;
}
// 还原
int index = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < count[i]; j++) {
arr[index++] = i;
}
}
}
桶排序
- 序列分别映射至有序的桶，桶内排序，最后依次输出
特性
- 映射函数：关键字
k1 < k2，那么f(k1) <= f(k2)，即桶(i)最大的数小于桶(i+1)中最小的数 - 桶越多，桶内需排序的数则越少，单占用空间越大
实现
public static void bucketSort(int[] arr) {
if (arr == null || arr.length == 0) return;
// 创建桶，使用链表
int bucketNumber = 10;
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketNumber; i++) {
buckets.add(new LinkedList<Integer>());
}
// 映射分配
int index;
for (int item : arr) {
index = item / bucketNumber; // 映射关系
buckets.get(index).add(item);
}
// 排序，还原
index = 0;
for (List<Integer> bucket : buckets) {
if (!bucket.isEmpty()) {
Collections.sort(bucket); // 桶内排序
for (Integer integer : bucket) {
arr[index++] = integer; // 还原
}
}
}
}
基数排序
- 序列按最大位数分趟，按进制分桶，按位的值映射至桶，再依次输出，最后趟循环
特性
- 多关键字分成多趟单关键字，单关键字排序，最后趟循环
实现
public static void radixSort(int[] arr) {
if (arr == null || arr.length == 0) return;
// 确定趟数，趟数为最大位数
int max = 0;
for (int item : arr) {
int length = Integer.toString(item).length();
if (length > max) max = length;
}
// 创建桶，桶数为进制数
int bucketNumber = 10;
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketNumber; i++) {
buckets.add(new LinkedList<Integer>());
}
// 按趟排序
int index;
for (int i = 0; i < max; i++) {
// 映射分配，排序
for (int item : arr) {
// 映射关系，按位获取
String s = Integer.toString(item);
index = 0;
if (s.length() > i) {
index = s.charAt(s.length() - i - 1) - '0';
}
buckets.get(index).add(item);
}
// 还原
index = 0;
for (List<Integer> bucket : buckets) {
if (!bucket.isEmpty()) {
for (Integer integer : bucket) {
arr[index++] = integer;
}
}
bucket.clear();
}
}
}
