- 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;
- }
- }
- 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);
- }
- }
- }
- }
来源: http://www.phpxs.com/code/1001858/