Java实现八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序等

 import java.util.Arrays; /* * 实现了八个常用的排序算法：插入排序、冒泡排序、选择排序、希尔排序 * 以及快速排序、归并排序、堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序：时间复杂度o(n^2) public static void insertSort(int a[], int n) { for (int i = 1; i = 0 && a[j] > temp) { a[j + 1] =a[j]; --j; } a[j + 1] = temp; } } //冒泡排序：时间复杂度o(n^2) public static void bubbleSort(int a[], int n) { for (int i = n - 1; i > 0; --i) { for (int j = 0; j  a[j + 1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } } } //选择排序：时间复杂度o(n^2) public static void selectSort(int a[], int n) { for (int i = 0; i = 1; gap /= 2) { for (int i = gap; i = 0 && a[j] > temp) { a[j + gap] = a[j]; j -= gap; } a[j + gap] = temp; } } } //快速排序：时间复杂度o(nlgn) public static void quickSort(int a[], int n) { _quickSort(a, 0, n-1); } public static void _quickSort(int a[], int left, int right) { if (left = pivot) { --right; } a[left] = a[right]; while (left = 1; --i) { int temp = a[0]; a[0] = a[i]; a[i] = temp; upAdjust(a, i); } } //建立一个长度为n的大根堆 public static void builtMaxHeap(int a[], int n) { upAdjust(a, n); } //对长度为n的数组进行一次上调整 public static void upAdjust(int a[], int n) { //对每个带有子女节点的元素遍历处理，从后到根节点位置 for (int i = n / 2; i >= 1; --i) { adjustNode(a, n, i); } } //调整序号为i的节点的值 public static void adjustNode(int a[], int n, int i) { //节点有左右孩子 if (2 * i + 1 <= n) { //右孩子的值大于节点的值，交换它们 if (a[2 * i] > a[i - 1]) { int temp = a[2 * i]; a[2 * i] = a[i - 1]; a[i - 1] = temp; } //左孩子的值大于节点的值，交换它们 if (a[2 * i -1] > a[i - 1]) { int temp = a[2 * i - 1]; a[2 * i - 1] = a[i - 1]; a[i - 1] = temp; } //对节点的左右孩子的根节点进行调整 adjustNode(a, n, 2 * i); adjustNode(a, n, 2 * i + 1); } //节点只有左孩子，为最后一个有左右孩子的节点 else if (2 * i == n) { //左孩子的值大于节点的值，交换它们 if (a[2 * i -1] > a[i - 1]) { int temp = a[2 * i - 1]; a[2 * i - 1] = a[i - 1]; a[i - 1] = temp; } } } //基数排序的时间复杂度为o(distance(n+radix)),distance为位数，n为数组个数，radix为基数 //本方法是用LST方法进行基数排序，MST方法不包含在内 //其中参数radix为基数，一般为10；distance表示待排序的数组的数字最长的位数；n为数组的长度 public static void lstRadixSort(int a[], int n, int radix, int distance) { int[] newA = new int[n];//用于暂存数组 int[] count = new int[radix];//用于计数排序，保存的是当前位的值为0 到 radix-1的元素出现的的个数 int divide = 1; //从倒数第一位处理到第一位 for (int i = 0; i = 0; --j) { int radixKey = (newA[j] / divide) % radix; a[count[radixKey] - 1] = newA[j]; --count[radixKey]; } divide = divide * radix; } } } 

 public class TestEightAlgorithms { public static void printArray(int a[], int n) { for (int i = 0; i