冒泡排序
package com.sort;
//冒泡排序 时间复杂度O(n^2)
public class BubbleSort {
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
int temp=0;
boolean flag=false;//判断是否发生交换
for (int i = 0; i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
// 升序排列
if(arr[j]<arr[j-1]){
flag=true;
temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}
}
if(!flag){
break;
}else{
flag=false;
}
}
for (int i:arr
) {
System.out.println(i);
}
}
}插入排序
package com.sort;
import java.util.Arrays;
//插入排序 时间复杂度O(n^2)
public class InsertSort {
public static void main(String[] args) {
int[] arr={1,44,787,33,74};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
for (int i = 1; i < arr.length; i++) {
for (int j = i; 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 com.sort;
import java.lang.reflect.Array;
import java.util.Arrays;
//选择排序 时间复杂度O(n^2)
public class SelectSort {
public static void main(String[] args) {
int[] arr={12,87,44,78,7,67,34};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
for (int j = 0; j < arr.length-1; j++) {
int indexmin=j;
int min=arr[j];
for (int i = j+1; i < arr.length; i++) {
if(min > arr[i]){
min=arr[i];
indexmin = i;
}
}
if(indexmin != j) {
arr[indexmin] = arr[j];
arr[j] = min;
}
}
}
}希尔排序
package com.sort;
import java.util.Arrays;
//希尔排序 时间复杂度O(n long n)
public class ShellSort {
public static void main(String[] args) {
int[] arr = {2, 5, 8, 1, 4, 9, 7, 3, 0, 6};
// sort(arr);//交换法
sort2(arr);
System.out.println(Arrays.toString(arr));
}
// 交换法 不推荐
public static void sort(int[] arr) {
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
for (int j = i - gap; j >= 0; j -= gap) {
if (arr[j] > arr[j + gap]) {
int temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
// 移位法
public static void sort2(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;
}
}
}
}
}快速排序
package com.sort;
import java.util.Arrays;
//快速排序 时间复杂度O(n long n)
public class QuickSort {
public static void main(String[] args) {
int[] arr = {-1, -10, 6, 3, 0, 4};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int left, int right) {
int l = left;
int r = right;
int p = arr[(left + right) / 2];
int temp = 0;
while (l < r) {
while (arr[l] < p) {
l += 1;
}
while (arr[r] > p) {
r -= 1;
}
if (l >= r) {
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
if (arr[l] == p) {
r -= 1;
}
if (arr[r] == p) {
l += 1;
}
}
if (l == r) {
l += 1;
r -= 1;
}
if (left < r) {
sort(arr, left, r);
}
if (right > l) {
sort(arr, l, right);
}
}
}归并排序
package com.sort;
import java.util.Arrays;
//归并排序 时间复杂度O(n long n)
public class MergetSort {
public static void main(String[] args) {
int[] arr={11,3,16,8,4,5,0,8};
int[] temp=new int[arr.length];
sort(arr,0, arr.length-1,temp );
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int left, int right, int[] temp){
if(left<right){
int mid=(left+right)/2;
sort(arr,left,mid,temp);
sort(arr,mid+1,right,temp);
merge(arr,left,mid,right,temp);
}
}
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
} else {
temp[t] = arr[j];
t++;
j++;
}
}
// 将剩余的传入到temp数组中
while (i <= mid) {
temp[t] = arr[i];
t++;
i++;
}
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
// 数组拷贝
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft]=temp[t];
t++;
tempLeft++;
}
}
}基数排序
package com.sort;
import java.util.Arrays;
//基数排序 O(n*k)
//缺点：数组中不能含有负数，空间换时间，占用内存较大
public class RadixSort {
public static void main(String[] args) {
int[] arr={1,5,7,2,98,3,88,246,1478};
// int[] arr = new int[80000];
// for (int i = 0; i < arr.length; i++) {
// arr[i] = (int) (Math.random() * 8000);
// }
// 测试运行运行时间
// 开始时间
// long startTime = System.currentTimeMillis();
sort(arr);
// long endTime = System.currentTimeMillis();
// System.out.println("程序运行时间：" + (double) (endTime - startTime) / 1000 + "s");
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int max = arr[0];
// 得到数组中的最大值
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 判断数组中最大值的位数
int maxLength = (max + "").length();
// 定义一个二维数组，每一个一维数组就是一个桶
int[][] bucked = new int[10][arr.length];
// 定义一维数组，记录每个桶中存放的数据
int[] backEleCount = new int[10];
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
for (int j = 0; j < arr.length; j++) {
// 取出每个元素个位值
int digitOfEle = arr[j] / n % 10;
// 存放到桶中
bucked[digitOfEle][backEleCount[digitOfEle]] = arr[j];
backEleCount[digitOfEle]++;
}
// 从一维数组中依次取出数据
int index = 0;
for (int j = 0; j < backEleCount.length; j++) {
if (backEleCount[j] != 0) {
// 遍历第j个桶中的元素 放入到数组中
for (int k = 0; k < backEleCount[j]; k++) {
arr[index++] = bucked[j][k];
}
}
backEleCount[j] = 0;
}
}
}
}标签：sort,arr,int,length,++,算法,排序,public From： https://www.cnblogs.com/xming2023/p/17104921.html