十大经典排序算法-纯代码-java版

public class BubbleSort{

	public static void bubbleSort(int[] arr) {
	
		if (arr == null || arr.length < 2) return;
		
		for (int i=0;ii;j--) { // 倒着将最小元素交换到起始位置
				if (arr[j] > arr[j-1]) {
					Utils.swap(arr,j,j-1);
				}
			}
		}
		
	}
	
}

public class SelectionSort {

	public static void selectionSort(int[] arr) {
		
		if (arr == null || arr.length < 2) return;
		
		for (int i=0;i 
插入排序 
public class InsertionSort {

	public static void insertionSort(int[] arr) {
		
		if (arr == null || arr.length < 2) return;
		
		for (int i=1;i=0;j--) {
//				if (arr[j+1] < arr[j]) {
//					Utils.swap(arr,j,j+1);
//				}
//			}
			
			// 优化写法
			for (int j=i-1;j>=0 && arr[j+1] 
希尔排序 
public class ShellSort {

	public static void shellSort(int[] arr) {
		
		if (arr == null || arr.length < 2) return;
		
		for (int i=arr.length/2;i>0;i/=2) { // 确定间隔
			
			// 插入排序
			for (int j=i;j-1 && tmp < arr[index]) {
					arr[index+i] = arr[index];
					index -= i;
				}
				
				arr[index+i] = tmp;
			}
		}
	}
}
 
归并排序 
	public static void mergeSort(int[] arr) {
		if (arr == null || arr.length < 2) return;
		process(arr,0,arr.length-1);
	}
	public static void process(int[] arr,int left,int right) {
		if (left == right) return;
		
		int mid = left + ((right - left) >> 1);
		process(arr,left,mid);
		process(arr,mid+1,right);
		merge(arr,left,mid,right);	
	}
	public static void merge(int[] arr,int left,int mid,int right) {
		if (left == right) return;
		
		int[] help = new int[right - left+1];
		
		int i = 0; int p1 = left; int p2 = mid+1;
		while (p1 <= mid && p2 <= right) {
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while (p1 <= mid) {
			help[i++] = arr[p1++];
		}
		while (p2 <= right) {
			help[i++] = arr[p2++];
		}
		for (int j=0;j 
快速排序 
public class QuickSort {

	public static void quickSort(int[] arr) {
		
		if (arr == null || arr.length < 2) return;
		
		process(arr,0,arr.length-1);	
	}
	
	public static void process(int[] arr,int L,int R) {
		if (L < R) {
			// 随机划分值
			int rand = (int)(Math.random() * (R-L+1));
			Utils.swap(arr,L+rand,R);
			
			int[] p = partition(arr,L,R);
			process(arr,L,p[0]);
			process(arr,p[1],R);
		}
	}
	
	public static int[] partition(int[] arr,int L,int R) {
		
		int left = L -1; // <区右边界
		int right = R; // <区左边界
		
		while (L < right) {
			
			if (arr[L] < arr[R]) {
				Utils.swap(arr,++left,L++);
			} else if (arr[L] > arr[R]) {
				Utils.swap(arr,--right,L);
			} else {
				L++;
			}
		}
		Utils.swap(arr,right,R);
		
		return new int[] {left,right+1};
	}
}
 
堆排序 
	public static void heapInsert(int[] arr,int index) {
		while (arr[index] > arr[(index-1)/2]) {
			Utils.swap(arr, 0, (index-1)/2);
			index = (index-1)/2;
		}
	}
	
	public static void heapify(int[] arr,int index,int heapSize) {
		
		int left = index * 2 + 1;
		while (left < heapSize) { // 下面还有孩子
			// 看哪个孩子大
			int largest = left+1 < heapSize && arr[left] > arr[left+1] ? left : left+1;
			
			// 看父节点和孩子哪个大
			largest = arr[index] > arr[largest] ? index : largest;
			
			if (largest == index) break;
			
			Utils.swap(arr, index, largest);
			index = largest;
			left = index * 2 + 1;
		}
	}

	public static void heapSort(int[] arr) {
		if (arr == null || arr.length <2) return;
		
		// 构建大顶堆
		for (int i=0;i 0) {
			heapify(arr,0,heapSize);
			Utils.swap(arr, 0, --heapSize);
		}
	}
 
工具类 
public class Utils {
	public static void swap(int[] arr,int n1,int n2) {
		if (n1<0 || n2<0 || n1 >= arr.length || n2 >= arr.length) return;
		
		int temp = arr[n1];
		arr[n1] = arr[n2];
		arr[n2] = temp;
	}
}
 
计数排序 
public class CountSort {
	
	public static void countSort(int[] arr) {
		if (arr == null || arr.length < 2) return;
		
		countSort(arr,0,arr.length-1);
	}

	public static void countSort(int[] arr,int L,int R) {
		
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		
		for (int i=L;i<=R;i++) {
			max = Math.max(max,arr[i]);
			min = Math.min(min,arr[i]);
		}
		
		int[] bucket = new int[max-min+1];
		
		for (int i=L;i<=R;i++) {
			int j = arr[i] - min;
			bucket[j]++;
		}
		
		for (int i=0;i 
桶排序 
public class BucketSort {

	public static void bucketSort(int[] arr) {
		
		if (arr == null || arr.length < 2) return;
		
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		
		for (int i=0;i> bucketArr = new ArrayList<>(bucketNum);
		System.out.println(bucketArr.size());
		for (int i=0;i());
		}
		
		for (int i=0;i 
基数排序 
public class RadixSort {
	
	public static void radixSort(int[] arr) {
		if (arr == null || arr.length < 2) return;
		
		radixSort(arr,0,arr.length-1,maxbits(arr));
	}
	
	public static void radixSort(int[] arr,int L,int R,int digit) {
		
		int i=0,j=0;
		// 生成辅助数组
		int[] bucket = new int[R-L+1];
		
		for (int d = 1;d <= digit;d++) {
			
			int[] count = new int[10];
			
			for (i = L;i<=R;i++) {
				j = getDigit(arr[i],d);
				count[j]++;
			}
			for (i=1;i<10;i++) {
				count[i] = count[i] + count[i-1];
			}
			for (i = R;i >= L;i--) {
				j = getDigit(arr[i],d);
				bucket[count[j]-1] = arr[i];
				count[j]--;
			}
			for (i = L,j = 0;i <= R;i++,j++) {
				arr[i] = bucket[j];
			}	
		}
	}
	
	public static int maxbits(int[] arr) {
		
		int max = Integer.MIN_VALUE;
		for (int i=0;i