冒泡排序
public class BubbleSort { public static int[] bubbleSort(int[] array) { if (array == null) { return null; } for (int i = 0; i < array.length; i++) { for (int j = i + 1; j < array.length; j++) { if (array[i] > array[j]) { array[i] = array[i] + array[j]; array[j] = array[i] - array[j]; array[i] = array[i] - array[j]; } } } return array; } } 插入排序
public class InsertSort { public static int[] insertSort(int[] array) { if (array == null) { return null; } for (int i = 1; i < array.length; i++) { for (int j = i; (j > 0) && (array[j] < array[j - 1]); j--) { SortUtils.swap(array, j, j - 1); } } return array; } } 选择排序
public class SelectionSort { public static int[] selectionSort(int[] array) { if (array == null) { return null; } for (int i = 0; i < array.length; i++) { int lowIndex = i; for (int j = array.length - 1; j > i; j--) { if (array[j] < array[lowIndex]) { lowIndex = j; } } SortUtils.swap(array, i, lowIndex); } return array; } } Shell排序
public class ShellSort { public static int[] shellSort(int[] array) { if (array == null) { return null; } for (int i = array.length / 2; i > 2; i /= 2) { for (int j = 0; j < i; j++) { insertSort(array, j, i); } } insertSort(array, 0, 1); return array; } private static void insertSort(int[] array, int start, int inc) { for (int i = start + inc; i < array.length; i += inc) { for (int j = i; (j >= inc) && (array[j] < array[j - inc]); j -= inc) { SortUtils.swap(array, j, j - inc); } } } } 快速排序
public class QKSort { public static int[] quickSort(int[] array) { if (array != null) { return quickSort(array, 0, array.length - 1); } return null; } private static int[] quickSort(int[] array, int beg, int end) { if (beg >= end || array == null) { return null; } int p = partition(array, beg, end); quickSort(array, beg, p - 1); quickSort(array, p + 1, end); return array; } /** * 找到分界点 * @param array * @param beg * @param end * @return */ private static int partition(int[] array, int beg, int end) { int last = array[end]; int i = beg - 1; for (int j = beg; j <= end - 1; j++) { if (array[j] <= last) { i++; if (i != j) { array[i] = array[i] ^ array[j]; array[j] = array[i] ^ array[j]; array[i] = array[i] ^ array[j]; } } } if ((i + 1) != end) { array[i + 1] = array[i + 1] ^ array[end]; array[end] = array[i + 1] ^ array[end]; array[i + 1] = array[i + 1] ^ array[end]; } return i + 1; } } 堆排序
public class HeapSort { public static int[] heapSort(int[] array) { if (array == null) { return null; } MaxHeap h = new MaxHeap(); h.init(array); for (int i = 0; i < array.length; i++) { h.remove(); } System.arraycopy(h.queue, 1, array, 0, array.length); return array; } private static class MaxHeap { void init(int[] data) { this.queue = new int[data.length + 1]; for (int i = 0; i < data.length; i++) { queue[++size] = data[i]; fixUp(size); } } private int size = 0; private int[] queue; public int get() { return queue[1]; } public void remove() { SortUtils.swap(queue, 1, size--); fixDown(1); } // fixdown private void fixDown(int k) { int j; while ((j = k << 1) <= size) { if (j < size && queue[j] < queue[j + 1]) { j++; } // 不用交换 if (queue[k] > queue[j]) { break; } SortUtils.swap(queue, j, k); k = j; } } private void fixUp(int k) { while (k > 1) { int j = k >> 1; if (queue[j] > queue[k]) { break; } SortUtils.swap(queue, j, k); k = j; } } } } 归并排序
public class MergeSort { public static int[] mergeSort(int[] array) { if (array == null) { return null; } int[] temp = new int[array.length]; return mergeSort(array, temp, 0, array.length - 1); } private static int[] mergeSort(int[] array, int[] temp, int l, int r) { int mid = (l + r) / 2; if (l == r) { return null; } mergeSort(array, temp, l, mid); mergeSort(array, temp, mid + 1, r); for (int i = l; i <= r; i++) { temp[i] = array[i]; } int i1 = l; int i2 = mid + 1; for (int cur = l; cur <= r; cur++) { if (i1 == mid + 1) { array[cur] = temp[i2++]; } else if (i2 > r) { array[cur] = temp[i1++]; } else if (temp[i1] < temp[i2]) { array[cur] = temp[i1++]; } else { array[cur] = temp[i2++]; } } return array; } } 归并排序(改进)
public class MergeSortImproved { private static final int THRESHOLD = 10; public static int[] mergeSort(int[] array) { if (array == null) { return null; } int[] temp = new int[array.length]; return mergeSort(array, temp, 0, array.length - 1); } private static int[] mergeSort(int[] array, int[] temp, int l, int r) { int i, j, k; int mid = (l + r) / 2; if (l == r) { return null; } if ((mid - l) >= THRESHOLD) { mergeSort(array, temp, l, mid); } else { insertSort(array, l, mid - l + 1); } if ((r - mid) > THRESHOLD) { mergeSort(array, temp, mid + 1, r); } else { insertSort(array, mid + 1, r - mid); } for (i = l; i <= mid; i++) { temp[i] = array[i]; } for (j = 1; j <= r - mid; j++) { temp[r - j + 1] = array[j + mid]; } int a = temp[l]; int b = temp[r]; for (i = l, j = r, k = l; k <= r; k++) { if (a < b) { array[k] = temp[i++]; a = temp[i]; } else { array[k] = temp[j--]; b = temp[j]; } } return array; } private static void insertSort(int[] array, int start, int len) { for (int i = start + 1; i < start + len; i++) { for (int j = i; (j > start) && array[j] < array[j - 1]; j--) { SortUtils.swap(array, j, j - 1); } } } }
