简单插入排序
1 public class QuickSort { 2 private static void quickSort(int [] a, int low, int high){ 3 if (low >= high){ 4 return; 5 } 6 int i = low; 7 int j = high; 8 int temp = a[i]; 9 while (i < j){ 10 while (i <j && a[j] >= temp){ 11 j--; 12 } 13 if (i < j){ 14 a[i++] = a[j]; 15 } 16 while (i < j && a[i] < temp){ 17 i++; 18 } 19 if (i < j){ 20 a[j--] = a[i]; 21 } 22 } 23 a[i] = temp; 24 quickSort(a, low, i -1); 25 quickSort(a, i + 1, high); 26 } 27 public static void main(String [] args){ 28 int [] a = {9,2,5,3,1,4,8,0,7,6}; 29 quickSort(a, 0, a.length-1); 30 for (int anA : a) { 31 System.out.print(anA + " "); 32 } 33 } 34 }
选择排序
1 public class SelectSort { 2 private static void sortSelect(int [] a ){ 3 int i; 4 int j; 5 int temp = 0; 6 int flag = 0; 7 for (i = 0; i < a.length; i++){ 8 temp = a[i]; 9 flag = i; 10 for (j = i +1; j <a.length; j++){ 11 if (a[j] < temp){ 12 temp = a[j]; 13 flag = j; 14 } 15 } 16 if (flag != i){ 17 a[flag] = a[i]; 18 a[i] = temp; 19 } 20 } 21 } 22 public static void main(String [] args){ 23 int [] a = {3,1,5,4,2,7,8,6,0,9}; 24 sortSelect(a); 25 for (int i = 0; i < a.length; i++){ 26 System.out.print(a[i] + " "); 27 } 28 } 29 }
冒泡排序
1 public class BubbleSort { 2 private static void bubbleSort(int [] a) { 3 int n = a.length; 4 for (int i = 0; i < n - 1; i++){ 5 for (int j = n -1; j > i; j--){ 6 if (a[j-1] > a[j]){ 7 int temp = a[j-1]; 8 a[j-1] = a[j]; 9 a[j] = temp; 10 } 11 } 12 } 13 } 14 public static void main(String [] args){ 15 int [] a = {9,2,5,3,1,4,8,0,7,6}; 16 bubbleSort(a); 17 for (int anA : a) { 18 System.out.print(anA + " "); 19 } 20 } 21 }
快速排序
1 public class QuickSort { 2 private static void quickSort(int [] a, int low, int high){ 3 if (low >= high){ 4 return; 5 } 6 int i = low; 7 int j = high; 8 int temp = a[i]; 9 while (i < j){ 10 while (i <j && a[j] >= temp){ 11 j--; 12 } 13 if (i < j){ 14 a[i++] = a[j]; 15 } 16 while (i < j && a[i] < temp){ 17 i++; 18 } 19 if (i < j){ 20 a[j--] = a[i]; 21 } 22 } 23 a[i] = temp; 24 quickSort(a, low, i -1); 25 quickSort(a, i + 1, high); 26 } 27 public static void main(String [] args){ 28 int [] a = {9,2,5,3,1,4,8,0,7,6}; 29 quickSort(a, 0, a.length-1); 30 for (int anA : a) { 31 System.out.print(anA + " "); 32 } 33 } 34 }
希尔排序
1 public class ShellSort { 2 public static void shellSort(int[] a){ 3 int length = a.length; 4 for (int gap = length/2; gap > 0; gap /= 2){ 5 for (int i = 0; i < gap; i++) { 6 for (int j = i + gap; j < length; j += gap){ //每个子序列都从第二个开始 7 if (a[j] < a[j - gap]){ 8 int temp = a[j]; 9 int k = j; 10 while ( k >= gap && a[k-gap] > temp){ 11 a[k] = a[k-gap]; 12 k -= gap; 13 } 14 a[k] = temp; 15 } 16 } 17 } 18 } 19 20 } 21 public static void main(String[] args){ 22 int [] a = {9,2,5,3,10,1,4,8,0,7,6}; 23 shellSort(a); 24 for (int anA : a) { 25 System.out.print(anA + " "); 26 } 27 } 28 }
归并排序
1 public class MergeSort { 2 public static void merge(int [] a, int start, int median, int end){ 3 int i; 4 int j; 5 int k; 6 int n1 = median - start + 1; 7 int n2 = end - median; 8 int[] L = new int[n1]; 9 int[] R = new int[n2]; 10 for (i = 0, k = start; i < n1; i++, k++){ 11 L[i] = a[k]; 12 } 13 for (i = 0, k = median + 1; i < n2; i++, k++){ 14 R[i] = a[k]; 15 } 16 for (k = start, i = 0, j = 0; i < n1 && j < n2; k++){ 17 if (L[i] < R[j]) { 18 a[k] = L[i]; 19 i++; 20 } else { 21 a[k] = R[j]; 22 j++; 23 } 24 } 25 while (i < n1){ 26 a[k] = L[i]; 27 i++; 28 k++; 29 } 30 while (j < n2){ 31 a[k] = R[j]; 32 j++; 33 k++; 34 } 35 } 36 public static void mergeSort(int[] a, int start, int end){ 37 if (start < end){ 38 int median = (start + end) / 2; 39 mergeSort(a, start, median); 40 mergeSort(a, median + 1, end); 41 merge(a, start, median, end); 42 } 43 } 44 45 public static void main(String[] args){ 46 int [] a = {9,2,5,3,10,1,4,8,0,7,6}; 47 mergeSort(a, 0, a.length-1); 48 for (int anA : a) { 49 System.out.print(anA + " "); 50 } 51 } 52 }
堆排序
1 public class HeapSort { 2 private static void maxHeapDown(int[] a, int start, int end){ 3 int father = start; 4 int child = 2 * father + 1; // 左孩子 5 while (child <= end){ 6 if (child < end && a[child] < a[child + 1]){ 7 child++; // 如果右孩子大，将左孩子变为右孩子 8 } 9 if (a[father] >= a[child]){ 10 break; 11 }else { 12 int tmp = a[father]; 13 a[father] = a[child]; 14 a[child] = tmp; 15 } 16 father = child; 17 child = 2 * father + 1; 18 } 19 } 20 private static void heapSortAsc(int[] a){ 21 int i; 22 int n = a.length; 23 for (i = n / 2 -1; i >= 0; i--){ // 从最后一个非终端节点开始，逐个向上遍历 24 maxHeapDown(a, i, n-1); 25 } 26 for (i = n - 1; i > 0; i--){ 27 int tmp = a[0]; 28 a[0] = a[i]; 29 a[i] = tmp; 30 maxHeapDown(a, 0, i-1); 31 } 32 } 33 public static void main(String[] args){ 34 int[] a = {9,2,5,4,7,3,8,0,1,6}; 35 heapSortAsc(a); 36 for (int i :a){ 37 System.out.print(i + " "); 38 } 39 } 40 }
基数排序
1 public class RadixSort { 2 private static int getMax(int[] a ){ 3 int max = a[0]; 4 for (int i : a){ 5 if (i > max){ 6 max = i; 7 } 8 } 9 return max; 10 } 11 private static void countSort(int[] a, int exp){ 12 int[] output = new int[a.length]; 13 int[] buckets = new int[10]; 14 for (int anA : a) { 15 buckets[(anA / exp) % 10]++; 16 } 17 for (int i : buckets) 18 System.out.print(i + " "); 19 System.out.println(); 20 for (int i = 1; i < 10; i++){ 21 buckets[i] += buckets[i - 1]; 22 } 23 for (int i : buckets) 24 System.out.print(i + " "); 25 System.out.println(); 26 for (int i = a.length - 1; i >= 0; i--){ 27 output[buckets[(a[i] / exp) % 10] - 1] = a[i]; 28 buckets[(a[i] / exp) % 10]--; 29 } 30 for (int i = 0; i < a.length; i++){ 31 a[i] = output[i]; 32 } 33 output = null; 34 buckets = null; 35 } 36 private static void radixSort(int[] a){ 37 int max = getMax(a); 38 for (int exp = 1; max / exp > 0; exp *= 10){ 39 countSort(a, exp); 40 } 41 } 42 public static void main(String[] args){ 43 int[] a = {53, 3, 542, 748, 14, 214, 154, 63, 616}; 44 radixSort(a); 45 for (int i : a){ 46 System.out.print(i + " "); 47 } 48 } 49 }