[数据结构与算法]十大经典排序算法-纯代码-java版

时间复杂度、空间复杂度、算法稳定性

冒泡排序

public class BubbleSort{

	public static void bubbleSort(int[] arr) {
	
		if (arr == null || arr.length < 2) return;
		
		for (int i=0;i<arr.length;i++) { // 在哪个范围上进行这一轮
			for (int j=arr.length-1;j>i;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<arr.length;i++) {
			
			int min=i;
			for (int j=i+1;j<arr.length;j++) {
				
//				if (arr[j] < arr[min]) {
//					min = j;
//				}
				
				// 优化写法
				min = arr[j] < arr[min] ? j : min;
			}
			Utils.swap(arr,i,min);
		}
	}
}

插入排序

public class InsertionSort {

	public static void insertionSort(int[] arr) {
		
		if (arr == null || arr.length < 2) return;
		
		for (int i=1;i<arr.length;i++) { // 第一位元素必定有序，所以从第二位开始
			
//			for (int j=i-1;j>=0;j--) {
//				if (arr[j+1] < arr[j]) {
//					Utils.swap(arr,j,j+1);
//				}
//			}
			
			// 优化写法
			for (int j=i-1;j>=0 && arr[j+1]<arr[j];j--) {
				Utils.swap(arr,j+1,j);
			}
		}
	}
}

希尔排序

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<arr.length;j++) {
				
				int tmp = arr[j];
				int index = j-i;
				
				while (index>-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<help.length;j++) {
			// left+j
			arr[left+j] = help[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<arr.length;i++) {
			heapInsert(arr,i);
		}
		// 将堆顶元素和末尾元素交换，然后断开
		int heapSize = arr.length;
		Utils.swap(arr, 0, --heapSize);
		
		while (heapSize > 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<bucket.length;i++) {
			while (bucket[i] != 0) {
				arr[L++] = min+i;
				bucket[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<arr.length;i++) {
			max = Math.max(max,arr[i]);
			min = Math.min(min,arr[i]);
		}
		
		int bucketNum = ((max-min)/arr.length)+1;
		
		ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
		System.out.println(bucketArr.size());
		for (int i=0;i<bucketNum;i++) {
			bucketArr.add(new ArrayList<Integer>());
		}
		
		for (int i=0;i<arr.length;i++) {
			int num = (arr[i] - min) / arr.length;
			bucketArr.get(num).add(arr[i]);
		}
		
		for (int i=0;i<bucketArr.size();i++) {
			Collections.sort(bucketArr.get(i));
		}
		
		int index = 0;
		for (int i=0;i<bucketArr.size();i++) {
			for (int j=0;j<bucketArr.get(i).size();j++) {
				arr[index++] = bucketArr.get(i).get(j);
			}
		}
	}
}

基数排序

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<arr.length;i++) {
			max = Math.max(max,arr[i]);
		}
		int res = 0;
		
		while (max != 0) {
			res++;
			max /= 10;
		}
		
		return res;
	}
	
	public static int getDigit(int k,int d) {
		
		while (k != 0 && --d != 0) {
			k /= 10;
		}
		
		return d == 0 ? k % 10 : 0;
	}
}