标题1.冒泡排序
import java.util.Arrays;
public class Main {
static int temp;
public static void main(String[] args) {
int[] nums = {12,15,13,46,87,164,454,22,45,65};
Bubbing(nums);//调用BBubbing方法
}
public static void Bubbing(int[] nums){
//排序前的数组
System.out.println("排序前数组序列：");
System.out.println(Arrays.toString(nums));//[12, 15, 13, 46, 87, 164, 454, 22, 45, 65]
//冒泡排序
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length-i-1; j++) {
if(nums[j]>nums[j+1]){
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
//遍历输出排序后的数组
System.out.println("排序后数组序列：");
System.out.println(Arrays.toString(nums));//[12, 13, 15, 22, 45, 46, 65, 87, 164, 454]
}
}
2.选择排序
import java.util.Arrays;
public class Main {
static int temp;
public static void main(String[] args) {
int[] nums = {12,15,13,46,87,164,454,22,45,65};
Select(nums, nums.length);
}
public static void Select(int [] nums,int len){
for (int i = 0; i < len-1; i++) {
int index =i;
int j;
for (j = i+1; j < len; j++) {
if(nums[j] < nums[index]){
index = j;
}
}
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
System.out.println(Arrays.toString(nums));
//[12, 15, 13, 46, 87, 164, 454, 22, 45, 65]
//[12, 13, 15, 46, 87, 164, 454, 22, 45, 65]
//[12, 13, 15, 46, 87, 164, 454, 22, 45, 65]
//[12, 13, 15, 22, 87, 164, 454, 46, 45, 65]
//[12, 13, 15, 22, 45, 164, 454, 46, 87, 65]
//[12, 13, 15, 22, 45, 46, 454, 164, 87, 65]
//[12, 13, 15, 22, 45, 46, 65, 164, 87, 454]
//[12, 13, 15, 22, 45, 46, 65, 87, 164, 454]
//[12, 13, 15, 22, 45, 46, 65, 87, 164, 454]
}
}
}
3.插入排序
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] num = {45,12,3,56,78,13,456,123,2};
insertionSort(num);
System.out.println(Arrays.toString(num));
}
public static int[] insertionSort(int []arr) {
int len = arr.length;
int preIndex, current;
for (int i = 1; i < len; i++) {
//获取下标前一个值
preIndex = i - 1;
//获取当前下标的值
current = arr[i];
//判断，下标大于零，按升序排序
while (preIndex >= 0 && arr[preIndex] > current) {
//因为已经取出当前下标的值，这里只需就前面的值往后移动
arr[preIndex + 1] = arr[preIndex];
//每次赋值完成，下标进行--；进行下一次的判断，赋值
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
}
[12, 45, 3, 56, 78, 13, 456, 123, 2]
[3, 12, 45, 56, 78, 13, 456, 123, 2]
[3, 12, 45, 56, 78, 13, 456, 123, 2]
[3, 12, 45, 56, 78, 13, 456, 123, 2]
[3, 12, 13, 45, 56, 78, 456, 123, 2]
[3, 12, 13, 45, 56, 78, 456, 123, 2]
[3, 12, 13, 45, 56, 78, 123, 456, 2]
[2, 3, 12, 13, 45, 56, 78, 123, 456]
4.快速排序
public static void main(String[] args) {
int[] arr = new int[]{45,12,3,56,78,13,456,123,2};
//快速排序，传入数组，最开始的位置
quickSort(arr,0,arr.length-1);
//打印输出
printArr(arr);
}
public static void quickSort(int[] arr,int left,int right){
//判断左边的下标是否和右边的相等，等于的时候就结束程序
if (left < right){
//将数组分为两个部分，arr[left..pivot]和arr[pivot...right]，pivot为基准数
//接收基准数所在的下标
int mid = get_mid(arr, left, right);
//递归的对左边序列进行排序，使有序
quickSort(arr,left,mid-1);
//递归的对右边序列进行排序，使有序
quickSort(arr,mid+1,right);
}
}
public static int get_mid(int[] arr,int left,int right){
//以left下标的值为基准数，此时left的位置相当于是空的，可以往里面赋值
int pivot = arr[left];
//当left与right相遇的时候，循环结束
while (left < right){
//遍历右边的数
//如果右边的数大于基准数，说明符合，将下标right--
while (arr[right] >= pivot && left < right)right--;
//当右边的数没有大于基准数时，将aa[right]的值赋给上面的挖空的位置
arr[left] = arr[right];
//遍历左边的数
//如果左边的数小于基准数，说明符合，将left++
while (arr[left] <= pivot && left < right)left++;
//如果左边的数大于基准数，说明这个应该出现在基准数的右边，将arr[left]的值赋给arr[right]的位置
arr[right] = arr[left];
}
//循环结束后，中间的一个位置的值是空的，这时候就需要将基准数的值赋到这个位置，可以满足左边的数都比基准数小
arr[left] = pivot;
//返回left小标，作为下一次循环的基准数的下标
return left;
}
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
5.希尔排序
public class Test3 {
public static void main(String[] args) {
int[] arr = new int[]{11,2,54,55,122,1,4,54,5,12};
shellSort(arr);
}
private static void shellSort(int[] arr){
for (int gap = arr.length/2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[i];
if (arr[j] < arr[j-gap]) {
while (j-gap >= 0 && temp < arr[j-gap]) {
arr[j] = arr[j-gap];
j -= gap;
}
arr[j] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
}
}
6.归并排序
public class Test3 {
public static void main(String[] args) {
//需要进行排序的数组
int[] array=new int[]{8,3,2,1,7,4,6,5};
//输出原数组的内容
printResult(array);
//归并排序操作
sort(array,0,array.length-1);
//输出排序后的相关结果
printResult(array);
}
private static void sort(int[] array,int i,int j) {
if(i
7.堆排序
public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
heapSort(array);
System.out.println(Arrays.toString(array));
}
public static void heapSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
//1.构建大顶堆
for (int i = length / 2 - 1; i >= 0; i--) {
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(array, i, length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (int j = length - 1; j > 0; j--) {
//将堆顶元素与末尾元素进行交换
swap(array, 0, j);
//重新对堆进行调整
adjustHeap(array, 0, j);
}
}
private static void adjustHeap(int[] array, int i, int length) {
//先取出当前元素i
int temp = array[i];
//从i结点的左子结点开始，也就是2i+1处开始
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
//如果左子结点小于右子结点，k指向右子结点
if (k + 1 < length && array[k] < array[k + 1]) {
k++;
}
//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
if (array[k] > temp) {
array[i] = array[k];
i = k;
} else {
break;
}
}
//将temp值放到最终的位置
array[i] = temp;
}
private static void swap(int[] array, int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
8.计数排序
public static void countingSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
int max = array[0];
int min = array[0];
for (int i = 0; i < length; i++) {
if (max < array[i]) {
max = array[i];
}
if (min > array[i]) {
min = array[i];
}
}
// 最大最小元素之间范围[min, max]的长度
int offset = max - min + 1;
// 1. 计算频率，在需要的数组长度上额外加1
int[] count = new int[offset + 1];
for (int i = 0; i < length; i++) {
// 使用加1后的索引，有重复的该位置就自增
count[array[i] - min + 1]++;
}
// 2. 频率 -> 元素的开始索引
for (int i = 0; i < offset; i++) {
count[i + 1] += count[i];
}
// 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
int[] aux = new int[length];
for (int i = 0; i < length; i++) {
// 填充一个数据后，自增，以便相同的数据可以填到下一个空位
aux[count[array[i] - min]++] = array[i];
}
// 4. 数据回写
for (int i = 0; i < length; i++) {
array[i] = aux[i];
}
}
public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
countingSort(array);
System.out.println(Arrays.toString(array));
}
9.桶排序
public static void bucketSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
// 建立桶，个数和待排序数组长度一样
int length = array.length;
linkedList[] bucket = (linkedList[]) new linkedList[length];
// 待排序数组中的最大值
int maxValue = Arrays.stream(array).max().getAsInt();
// 根据每个元素的值，分配到对应范围的桶中
for (int i = 0; i < array.length; i++) {
int index = toBucketIndex(array[i], maxValue, length);
// 没有桶才建立桶(延时)
if (bucket[index] == null) {
bucket[index] = new linkedList<>();
}
// 有桶直接使用
bucket[index].add(array[i]);
}
// 对每个非空的桶排序，排序后顺便存入临时的List，则list中已经有序）
List temp = new ArrayList<>();
for (int i = 0; i < length; i++) {
if (bucket[i] != null) {
Collections.sort(bucket[i]);
temp.addAll(bucket[i]);
}
}
// 将temp中的数据写入原数组
for (int i = 0; i < length; i++) {
array[i] = temp.get(i);
}
}
private static int toBucketIndex(int value, int maxValue, int length) {
return (value * length) / (maxValue + 1);
}
public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
bucketSort(array);
System.out.println(Arrays.toString(array));
}
10.基数排序
public static void radixSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
// 每位数字范围0~9，基为10
int radix = 10;
int[] aux = new int[length];
int[] count = new int[radix + 1];
// 以关键字来排序的轮数，由位数最多的数字决定，其余位数少的数字在比较高位时，自动用0进行比较
// 将数字转换成字符串，字符串的长度就是数字的位数，字符串最长的那个数字也拥有最多的位数
int x = Arrays.stream(array).map(s -> String.valueOf(s).length()).max().getAsInt();
// 共需要d轮计数排序, 从d = 0开始，说明是从个位开始比较，符合从右到左的顺序
for (int d = 0; d < x; d++) {
// 1. 计算频率，在需要的数组长度上额外加1
for (int i = 0; i < length; i++) {
// 使用加1后的索引，有重复的该位置就自增
count[digitAt(array[i], d) + 1]++;
}
// 2. 频率 -> 元素的开始索引
for (int i = 0; i < radix; i++) {
count[i + 1] += count[i];
}
// 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
for (int i = 0; i < length; i++) {
// 填充一个数据后，自增，以便相同的数据可以填到下一个空位
aux[count[digitAt(array[i], d)]++] = array[i];
}
// 4. 数据回写
for (int i = 0; i < length; i++) {
array[i] = aux[i];
}
// 重置count[]，以便下一轮统计使用
for (int i = 0; i < count.length; i++) {
count[i] = 0;
}
}
}
private static int digitAt(int value, int d) {
return (value / (int) Math.pow(10, d)) % 10;
}
public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
radixSort(array);
System.out.println(Arrays.toString(array));
}
