Java对各种排序算法的实现，Java排序算法实现,冒泡排序 ```java

Java对各种排序算法的实现，Java排序算法实现,冒泡排序 ```java

冒泡排序 ```java 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;      }  }

 插入排序 ```java    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) &amp;&amp; (array[j] < array[j - 1]); j--) {                      SortUtils.swap(array, j, j - 1);                  }              }              return array;          }      }  

选择排序```java 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排序```java    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) &amp;&amp; (array[j] < array[j - inc]); j -= inc) {                      SortUtils.swap(array, j, j - inc);                  }              }          }      }  

快速排序```java 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;      }}

堆排序```java    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 &amp;&amp; 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;                  }              }          }      }  

归并排序```java 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;      }  }

归并排序(改进)```java    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) &amp;&amp; array[j] < array[j - 1]; j--) {                      SortUtils.swap(array, j, j - 1);                  }              }          }      }