java实现快速排序、归并排序、希尔排序、基数排序算法...

素颜马尾好姑娘i 2023-03-14 08:28 18阅读 0赞

## 快速排序算法 ##

import java.util.Arrays;
    
    public class QuickSort { 
    	public static void main(String[] args) { 
    		int[] arr = { 1,1,78,-5,4,3,76,12};
    		
    		System.out.println("排序前:"+Arrays.toString(arr));
    		quickSort(arr,0,arr.length-1);
    		System.out.println("排序后:"+Arrays.toString(arr));
    	}
    	
    	public static void quickSort(int[] arr,int low,int high) { 
    		if(low < high) { 
    			int pivotloc = partition(arr,low,high);
    			quickSort(arr,low,pivotloc-1);
    			quickSort(arr,pivotloc+1,high);
    		}
    	}
    	
    	public static int partition(int[] arr,int low,int high) { 
    		int temp;
    		int pivot = arr[low];
    // System.out.println("pivot=" + pivot);
    		while(low < high) { 
    			while(low < high && arr[high] >= pivot) { 
    				high--;
    			}
    			temp = arr[high];
    			arr[high] = arr[low];
    			arr[low] = temp;
    			
    			while(low < high && arr[low] <= pivot) { 
    				low++;
    			}
    			temp = arr[high];
    			arr[high] = arr[low];
    			arr[low] = temp;
    			
    		}
    		return low;
    	}
    }

## 归并排序算法 ##

import java.util.Arrays;
    
    public class MergeSort { 
    	public static void main(String[] args) { 
    		int[] arr = {  1,124,-99, 1, 78, 4, 9, 1, 23, -5, 12 };
    		int[] temp = new int[arr.length];
    		
    		System.out.println("排序前:" + Arrays.toString(arr));
    		mergeSort(arr,0,arr.length-1,temp);
    		System.out.println("排序后:" + Arrays.toString(arr));
    	}
    	
    	public static void mergeSort(int[] arr, int left,int right,int[] temp) { 
    		if(left < right) { 
    			// 计算中间位置
    			int mid = (left + right)/2;
    			// 向左递归分解
    			mergeSort(arr,left,mid,temp);
    			// 向右递归分解 
    			mergeSort(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++;
    			}		
    		}
    		
    		// 把两边剩余的数据复制到临时数组 中
    		while(i <= mid) { 
    			temp[t] = arr[i];
    			t++;
    			i++;
    		}
    		while(j <= right) { 
    			temp[t] = arr[j];
    			t++;
    			j++;
    		}
    		
    		// 把数据从临时数组中复制到arr中
    		t = 0;
    		int tempLeft = left;
    		while(tempLeft <= right) { 
    			arr[tempLeft] = temp[t];
    			tempLeft++;
    			t++;
    		}
    		
    	}
    }

## 希尔排序算法 ##

import java.util.Arrays;
    import java.util.Random;
    
    public class ShellSort { 
    
    	public static void main(String[] args) { 
    // int[] arr = { 1, 1, 78, 4, 9, 1, 23, -5, 4, 3, 76, 12 };
    		// 随机生成数组
    		int[] arr = new int[8];
    		Random rand = new Random();
    		for(int i = 0; i < arr.length; i++) { 
    			arr[i] = rand.nextInt(1000);
    		}
    
    		System.out.println("排序前:" + Arrays.toString(arr));
    		shellSort(arr);
    		System.out.println("排序后:" + Arrays.toString(arr));
    	}
    
    	public 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];
    				// 找位置
    				while(j-gap >= 0 && temp < arr[j-gap]) { 
    					arr[j] = arr[j-gap];
    					j -= gap;
    				}
    				// 此时的j 就是那个合适的位置了
    				arr[j] = temp;
    			}
    		}
    	}
    }

## 基数排序算法 ##

import java.util.Arrays;
    
    public class RadixSort { 
    	public static void main(String[] args) { 
    		int[] arr = {  -7, -335, 0, -90, 1, 123, 1, 78, 4, 64,2204, 9, 0, 1, 23,12 };
    
    		System.out.println("排序前:" + Arrays.toString(arr));
    		radixSort(arr);
    		System.out.println("排序后:" + Arrays.toString(arr));
    	}
    
    	public static void radixSort(int[] arr) { 
    
    		// 定义20个桶，正负数皆可
    		int[][] bucket = new int[20][arr.length];
    		// 每个桶的指针
    		int[] counts = new int[20];
    
    		// 求数组最大值的位数
    		int max = arr[0];
    		for (int i = 1; i < arr.length; i++) { 
    			if (max < arr[i]) { 
    				max = arr[i];
    			}
    		}
    		int len = (max + "").length();
    
    		for (int i = 0, n = 1; i < len; i++, n *= 10) { 
    			for (int j = 0; j < arr.length; j++) { 
    				
    				int rem = (arr[j] /n) %10;
    				// 负数用前10个桶，正数用后10个桶
    				rem += 10;
    				bucket[rem][counts[rem]++] = arr[j];
    				
    			}
    			
    			int index = 0;
    			// 遍历所有的桶将数据取出，放入数组
    			for(int k = 0; k < counts.length; k++) { 
    				if(counts[k] > 0) { 
    					for(int p = 0; p < counts[k]; p++) { 
    						arr[index++] = bucket[k][p];
    					}
    					counts[k] = 0;
    				}
    			}
    		}
    
    	}
    }