冒泡排序
package 排序;
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int j=0;j<arr.length;j++) {
for(int i=0;i<arr.length-1-j;i++) {
if(arr[i]>arr[i+1]) {
//进行交换
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
}
}
}
堆排序
package 排序;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {65,67,46,2,0,34,16,66};
// 1. 构建大顶堆,从最后一个非叶子节点开始构建大顶堆
for (int p = arr.length-1; p >= 0; p--) {
adjust(arr, p, arr.length);
}
// 2. 堆排序
for (int i = arr.length - 1; i > 0; i--) {
// 交换堆顶（当前最大值）和堆的最后一个元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 对剩余的元素重新调整为大顶堆
adjust(arr, 0, i);
}
System.out.println(Arrays.toString(arr));
}
// 堆的维护（调整为大顶堆）
public static void adjust(int[] arr, int parent, int length) {
int child = 2 * parent + 1;
while (child < length) {
int rchild = child + 1;
int largest = child; // 假设左孩子最大
if (rchild < length && arr[rchild] > arr[largest]) {
largest = rchild; // 右孩子更大
}
// 如果父节点小于最大的子节点，则交换
if (arr[parent] < arr[largest]) {
int temp = arr[parent];
arr[parent] = arr[largest];
arr[largest] = temp;
// 继续向下调整
parent = largest;
child = 2 * parent + 1;
} else {
break; // 父节点已经大于或等于最大的子节点，无需继续调整
}
}
}
}
插入排序
package 排序;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int i=1;i<arr.length;i++) {
//用j和j+1进行比较交换
for(int j=i-1;j>=0;j--) {
if(arr[j]>arr[j+1]) {
//进行交换
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}else {
//跳出循环
break;
}
}
}
}
}
归并排序
package 排序;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
Mergesort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
//拆分
public static void Mergesort(int[] arr,int left,int right) {
//递归出口
if(left==right) {
return;
}
int mid = (left + right)/2;
Mergesort(arr,left,mid);
Mergesort(arr,mid+1,right);
//合并
merge(arr,left,right,mid);
}
public static void merge(int[] arr,int left,int right,int mid) {
//定义第一段和第二段的开始
int s1 = left;
int s2 = mid+1;
//定义临时空间
int[] temp = new int[right-left+1];
int index = 0;//定义游标遍历临时空间
while(s1<=mid&&s2<=right) {
if(arr[s1]<arr[s2]) {
temp[index] = arr[s1];
s1++;
index++;
}else {
temp[index] = arr[s2];
s2++;
index++;
}
}
//判断s1中是否有数据，如果有将其放入临时数组
while(s1<=mid) {
temp[index] = arr[s1];
s1++;
index++;
}
//判断s2中是否有数据，如果有将其放入临时数组
while(s2<=right) {
temp[index] = arr[s2];
s2++;
index++;
}
//将临时数组中的数据写回原数组
for(int j=0;j<temp.length;j++) {
arr[left + j] = temp[j];
}
}
}
快速排序
package 排序;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {65, 67, 46, 27, 10, 34, 16, 66};
quicksort(arr, 0, arr.length - 1); // 注意这里修改为 arr.length - 1
System.out.println(Arrays.toString(arr));
}
public static void quicksort(int[] arr, int left, int right) {
if (left >= right) {
return; // 当左索引不小于右索引时，无需排序
}
// 定义基准数
int base = arr[left];
// 定义i, j
int i = left;
int j = right;
while (i != j) {
// j游标从后往前移动，找比基准数小的
while (arr[j] >= base && i < j) {
j--;
}
// i游标从前往后移动，找比基准数大的
while (arr[i] <= base && i < j) {
i++;
}
// i和j交换
if (i < j) { // 确保不交换相同索引的元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// i和j相遇，将基准数放到正确的位置
arr[left] = arr[i];
arr[i] = base;
// 排序左边和右边（不包括已经排序好的基准数位置）
quicksort(arr, left, i - 1); // 注意这里是 i - 1
quicksort(arr, i + 1, right);
}
}
基数排序
package 排序;
import java.util.Arrays;
public class RadixSort {
public static void main(String[] args) {
int[] arr = {9, 7, 45, 2, 10, 3, 17, 66};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int max = arr[0];
for (int j = 0; j < arr.length; j++) {
if (arr[j] > max) {
max = arr[j];
}
}
int maxLen = (max + "").length();
// 定义桶
int[][] bucket = new int[10][arr.length];
// 定义桶记录工具
int[] elementCounts = new int[10];
int n = 1;
for (int m = 0; m < maxLen; m++) {
// 遍历数组，将数组中的数据放入桶中
for (int i = 0; i < arr.length; i++) {
int digit = (arr[i] / n) % 10; // 获取当前位的数字
int count = elementCounts[digit];
bucket[digit][count] = arr[i];
elementCounts[digit]++;
}
// 将桶中的数据取出
int index = 0; // 遍历待排序数组的游标
for (int k = 0; k < elementCounts.length; k++) {
if (elementCounts[k] != 0) {
for (int i = 0; i < elementCounts[k]; i++) {
arr[index] = bucket[k][i];
index++;
}
}
elementCounts[k] = 0; // 重置桶计数
}
n *= 10; // 移动到下一个位数
}
}
}
选择排序
package 排序;
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int j=0;j<arr.length;j++) {
int min = arr[j];//记录最小值
int minIndex = j;//记录最小值下标
//找真正的最小值
for(int i=j;i<arr.length;i++) {
if(arr[i]<min) {
min = arr[i];
minIndex = i;
}
}
//真正的最小值和待排序数组中的第一个进行交换
arr[minIndex] = arr[j];
arr[j] = min;
}
}
}
希尔排序
package 排序;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int grp = arr.length/2;grp>0;grp=grp/2) {
for(int i = grp;i<arr.length;i++) {
//arr[j] arr[j+grp]进行比较
for(int j=i-grp;j>=0;j=j-grp) {
if(arr[j] > arr[j+grp]) {
int temp = arr[j];
arr[j] = arr[j+grp];
arr[j+grp] = temp;
}else {
break;
}
}
}
}
}
}