public class Main {
public static void main(String[] args) {
int[] array = {3,2,4,1,5};
int[] temp = new int[array.length];
radixSort(array);
System.out.println(Arrays.toString(array));
}
//基数排序
public static void radixSort(int[] array){
//初始化桶
int[][] bucket = new int[10][array.length];
int[] everyBucketEleNum = new int[10];
//得到最大数的位数，这个位数决定总共排几次
int max = 0;
for (int i = 0;i < array.length;i++){
if (array[i] > max){
max = array[i];
}
}
int maxLength = (max + "").length();
int temp = 1;//取位数的值
for (int i = 1;i <= maxLength;i++){
//先放到桶中
for (int j = 0;j < array.length;j++){
//第一轮循环就是得到这个数的个位、下一轮循环就是百位。。。
int digitOfElement = (array[j] / temp) % 10;
//把它加入到桶中
bucket[digitOfElement][everyBucketEleNum[digitOfElement]] = array[j];
everyBucketEleNum[digitOfElement]++;
}
//然后从桶里面取出来
int index = 0;
for (int j = 0;j < 10;j++){
if (everyBucketEleNum[j] > 0){
for (int k = 0;k < everyBucketEleNum[j];k++){
array[index] = bucket[j][k];
index++;
}
everyBucketEleNum[j] = 0;
}
}
//进行下一次的时候 temp要变化
temp *= 10;
}
}
//归并排序
public static void mergeSort(int[] array){
int[] temp = new int[array.length];
mergeSort(array,0,array.length - 1,temp);
}
public static void mergeSort(int[] array,int left,int right,int[] temp){
if (left < right){
int middle = (left + right) / 2;
//先分左边
mergeSort(array,left,middle,temp);
//再分右边
mergeSort(array,middle + 1,right,temp);
//然后进行治
sort(array,left,middle,right,temp);
}
}
public static void sort(int[] array,int left,int middle,int right,int[] temp){
//i是对左边的索引，j是对右边的索引,t是对temp的索引
int i = left;
int j = middle + 1;
int t = 0;
while (i <= middle && j <= right){
if (array[i] < array[j]){
temp[t] = array[i];
i++;
t++;
}else {
temp[t] = array[j];
t++;
j++;
}
}
//如果左边有剩的
while (i <= middle){
temp[t] = array[i];
i++;
t++;
}
//如果右边有剩的
while (j <= right){
temp[t] = array[j];
t++;
j++;
}
//然后把temp赋值到array上面
t = 0;//t是temp的索引
for (int k = left;k <= right;k++){
array[k] = temp[t];
t++;
}
}
//快速排序
public static void quickSort(int[] array,int l,int r){
if (l < r){
int left = l;
int right = r;
int x = array[l];
while (left < right){
//先从右往左
while (left < right && array[right] > x){
right--;
}
if (left < right){
array[left] = array[right];
left++;
}
//再从左往右
while (left < right && array[left] < x){
left++;
}
if (left < right){
array[right] = array[left];
right--;
}
}
array[left] = x;
quickSort(array,l,left - 1);
quickSort(array,left + 1,r);
}
System.out.println(Arrays.toString(array));
}
//希尔排序，交换式
public static void shellSort1(int[] array){
for (int gap = array.length / 2;gap > 0;gap = gap / 2){
for (int i = gap;i < array.length;i++){
for (int j = i - gap;j >= 0;j = j - gap){
if (array[j + gap] < array[j]){
int temp = array[j];
array[j] = array[j + gap];
array[j + gap] = temp;
}
}
}
}
System.out.println(Arrays.toString(array));
}
//希尔排序，移位式
public static void shellSort2(int[] array){
for (int gap = array.length/2;gap > 0;gap = gap/2){
for (int i = gap;i < array.length;i++){
int insertIndex = i - gap;
int insertVal = array[i];
while (insertIndex >= 0 && insertVal < array[insertIndex]){
array[insertIndex + gap] = array[insertIndex];
insertIndex = insertIndex - gap;
}
array[insertIndex + gap] = insertVal;
}
}
System.out.println(Arrays.toString(array));
}
//插入排序
public static void insertSort(int[] array){
int insertVal;//要插入的值
int insertIndex;//要插入的位置的下标
for (int i = 1;i < array.length;i++){//i要从1开始
insertIndex = i - 1;//这里的初始值是i - 1 ，而不是i 一定记住了！
insertVal = array[i];
//找到要插入的位置
while (insertIndex >= 0 && array[insertIndex] > insertVal){
//把每个数据往后挪
array[insertIndex + 1] = array[insertIndex];
insertIndex--;
}
//找到了要插入的位置
array[insertIndex + 1] = insertVal;
}
System.out.println(Arrays.toString(array));
}
//选择排序
public static void selectSort(int[] array){
int min;//记录最小值
int minIndex;//最小值的下标
for (int i = 0;i < array.length - 1;i++){//外层for表示一共需要比较几轮，内层for表示每一轮的索引
//默认第一个是最小值
min = array[i];
minIndex = i;
for (int j = i + 1;j < array.length;j++){
if (array[j] < min){
min = array[j];
minIndex = j;
}
}
//每一轮比较完，就应该在i的位置更新最小值
if (minIndex != i){//最小值不是i指向的位置
array[minIndex] = array[i];
array[i] = min;
}
}
System.out.println(Arrays.toString(array));
}
//冒泡排序（升级版）
public static void bubbleSort(int[] array){
//定义flag，记录有没有发生交换
boolean flag = false;//默认是没有发生交换
for (int i = 0;i < array.length - 1;i++){
for (int j = 0;j < array.length - i - 1;j++){
if (array[j + 1] < array[j]){
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
flag = true;//说明发生了交换
}
}
if (flag){
//发生了交换，则继续
flag = false;
}else {
break;
}
}
System.out.println(Arrays.toString(array));
}
}
