Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

本文实例汇总了Java各种排序算法。分享给大家供大家参考，具体如下：

1. 冒泡排序：

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
  show(a);
  bubbleSort(a);
  show(a);
 }
 private static void bubbleSort(int[] a) {
  for(int i=0;i<a.length-1;i++){
   for(int j=0;j<a.length-i-1;j++){
    if(a[j]>a[j+1]){
     int tmp = a[j];
     a[j] = a[j+1];
     a[j+1] = tmp;
    }
   }
  }
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

2. 快速排序(无重复值)：

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,3,12,23,110};
  show(a);
  quickSort(a,0,a.length-1);
  show(a);
 }
 private static void quickSort(int[] a, int start, int end) {
  if (start>=end)
   return;
  int i=start;
  int j=end;
  int index = start;
  while(i<j){
   while(a[j]>a[index]){
    j--;
   }
   index = swap(a,j,index);
   while(a[index]>a[i]){
    i++;
   }
   index = swap(a,i,index);
  }
  quickSort(a, start, index-1);
  quickSort(a, index+1, end);
 }
 private static int swap(int[] a, int n, int index) {
  int tmp = a[n];
  a[n] = a[index];
  a[index] = tmp;
  return n;
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

3. 快速排序（可含重复值）

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,345};
  show(a);
  quickSort2(a,0,a.length-1);
  show(a);
 }
 private static void quickSort2(int[] a, int start, int end) {
  if (start>=end)
   return;
  int i=start;
  int j=end;
  int index = end;
  while(i<j){
   while(a[j]>a[index]){
    j--;
   }
   if (j!=index && a[j]==a[index]){
    index = swap(a,--j,index);
   }else{
    index = swap(a,j,index);
   }
   while(a[index]>a[i]){
    i++;
   }
   if (i!=index && a[i]==a[index]){
    index = swap(a,++i,index);
   }else{
    index = swap(a,i,index);
   }
  }
  quickSort2(a, start, index-1);
  quickSort2(a, index+1, end);
 }
 private static int swap(int[] a, int n, int index) {
  int tmp = a[n];
  a[n] = a[index];
  a[index] = tmp;
  return n;
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

4. 堆排序

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
  show(a);
  heapSort(a);
  show(a);
 }
 private static void heapSort(int[] a) {
  //建立最大堆
  int size = a.length;
  for(int i=size/2-1;i>=0;i--){
   createBigHeap(a,i,size-1);
  }
  //排序
  for(int j=0;j<size-1;j++){
   int tmp=a[0];
   a[0]=a[size-1-j];
   a[size-1-j]=tmp;
   createBigHeap(a,0,size-2-j);
  }
 }
 private static void createBigHeap(int[] a, int start, int end) {
  int tmp = a[start];
  int j = 2*start+1;
  while(j<=end){
   if (j<end && a[j]<a[j+1]){
    j++;
   }
   if (a[j]>tmp){
    a[start] = a[j];
    start = j;
    j = 2*j+1;
   }else{
    break;
   }
  }
  a[start] = tmp;
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

5. 插入排序

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1,3};
  show(a);
  insertSort(a);
  show(a);
 }
 private static void insertSort(int[] a) {
  for(int i=0;i<a.length-1;i++){
   int n = i+1;
   int tmp = a[n];
   for(int j=i;j>=0;j--){
    if(tmp<a[j]){
     a[n] = a[j];
     n=j;
    }
   }
   if (a[n]!=tmp)
    a[n] = tmp;
  }
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

6. 折半插入排序

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,7,345,2,2,7,2,7,23,2,345,7,32,5,4,-1,3,7,2,3,2,3,4,2,1,2,4,5,3,345,3,2};
  show(a);
  insertSort2(a);
  show(a);
 }
 private static void insertSort2(int[] a) {
   for(int i=0;i<a.length-1;i++){
    int n = i+1;
    int tmp = a[n];
    if (tmp>a[i])
     continue;
    int low = 0;
    int high = i;
    int mid = (high+low)/2;
    while(high>=low){
     mid = (high+low)/2;
     if(tmp<a[mid]){
      high = mid -1;
     }else if(tmp>a[mid]){
      low = mid + 1;
     } else{
      low=mid;
      break;
     }
    }
    for(int j=n;j>mid;j--){
     a[j] = a[j-1];
    }
    a[low] = tmp;
   }
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

7. 希尔排序

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1,3,2,3,5,7,8,90,1};
  show(a);
  shellSort(a);
  show(a);
 }
 private static void shellSort(int[] a) {
  shellSort(a,a.length);
 }
 private static void shellSort (int[] a, int n){
   int i, j, k, temp, gap;
   int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
      213331,543749,1355339,3501671,8810089,21521774,
      58548857,157840433,410151271,1131376761,2147483647 };
   for (k=0; gaps[k]<n; k++);
   while (--k >= 0){
    gap = gaps[k];
    for (i=gap; i<n; i++){
     temp = a[i];
     j = i;
     while (j>=gap && a[j-gap]>temp){
      a[j] = a[j-gap];
      j = j-gap;
     }
     a[j] = temp;
    }
   }
  }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

8. 选择排序

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1};
  show(a);
  selectSort(a);
  show(a);
 }
 private static void selectSort(int[] a) {
  for (int i = 0; i < a.length-1; i++) {
   int min = i;
   for (int j = i+1; j < a.length; j++) {
    if (a[j]<a[min])
     min = j;
   }
   if (min!=i){
    int tmp = a[i];
    a[i] = a[min];
    a[min] = tmp;
   }
  }
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

9. 归并排序

public class SortTest {
 public static void main(String[] args) {
  int[] a = {345,7,32,5,4,-1,3,2,3,5,7,8,90,1,432,1};
  show(a);
  mergeSort(a);
  show(a);
 }
 private static void mergeSort(int[] a) {
  //找出中间值
  int mid = a.length/2;
  //申请空间存储中间索引以左的值
  int[] left = setValue(a,0,mid);
  if (left.length>1){//继续拆分左边，直到元素值为1个
   mergeSort(left);
  }
  //申请空间存储中间索引以右的值
  int[] right = setValue(a,mid,a.length);
  if (right.length>1){//继续拆分右边，直到元素值为1个
   mergeSort(right);
  }
  //将左右值合并
  merge(a,left,right);
 }
 private static void merge(int[] a , int[] left, int[] right) {
  int i=0,j=0,k=0;
  for(;i<left.length && j<right.length;){
   if (left[i]<right[j]){
    a[k++] = left[i++];
   }else{
    a[k++] = right[j++];
   }
  }
  for(;i<left.length;i++){
   a[k++] = left[i];
  }
  for(;j<right.length;j++){
   a[k++] = right[j];
  }
 }
 private static int[] setValue(int[] a, int start,int length) {
  int[] x = new int[length-start];
  for (int i = 0; i < x.length; i++) {
   x[i] = a[start++];
  }
  return x;
 }
 private static void show(int[] a) {
  System.out.println(Arrays.toString(a));
 }
}

汇总：

public class SortUtil {
 public final static int DESC = -1;
 public final static int ASC = 1;
 /**
  * 冒泡排序
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void bubbleSort(int[] a,int sort) {
  if (sort==ASC)
   bubbleSortAsc(a);
  else
   bubbleSortDesc(a);
 }
 public static void bubbleSortAsc(int[] a) {
  for(int i=0;i<a.length-1;i++){
   for(int j=0;j<a.length-i-1;j++){
    if(a[j]>a[j+1]){
     int tmp = a[j];
     a[j] = a[j+1];
     a[j+1] = tmp;
    }
   }
  }
 }
 public static void bubbleSortDesc(int[] a) {
  for(int i=0;i<a.length-1;i++){
   for(int j=0;j<a.length-i-1;j++){
    if(a[j]<a[j+1]){
     int tmp = a[j];
     a[j] = a[j+1];
     a[j+1] = tmp;
    }
   }
  }
 }
// ----------------华-丽-的-功-能-分割-线-----------------------
 /**
  * 快速排序（不允许有重复值）
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void quickNoRepeatSort(int[] a,int sort) {
  if (sort==ASC)
   quickNoRepeatSortAsc(a, 0, a.length-1);
  else
   quickNoRepeatSortDesc(a, 0, a.length-1);
 }
 private static void quickNoRepeatSortAsc(int[] a, int start, int end) {
  if (start >= end)
   return;
  int i = start;
  int j = end;
  int index = start;
  while (i < j) {
   while (a[j] > a[index]) {
    j--;
   }
   index = swap(a, j, index);
   while (a[index] > a[i]) {
    i++;
   }
   index = swap(a, i, index);
  }
  quickNoRepeatSortAsc(a, start, index - 1);
  quickNoRepeatSortAsc(a, index + 1, end);
 }
 private static void quickNoRepeatSortDesc(int[] a, int start, int end) {
  if (start >= end)
   return;
  int i = start;
  int j = end;
  int index = start;
  while (i < j) {
   while (a[j] < a[index]) {
    j--;
   }
   index = swap(a, j, index);
   while (a[index] < a[i]) {
    i++;
   }
   index = swap(a, i, index);
  }
  quickNoRepeatSortDesc(a, start, index - 1);
  quickNoRepeatSortDesc(a, index + 1, end);
 }
 /**
  * 快速排序（允许有重复值）
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void quickSort(int[] a,int sort) {
  if (sort==ASC)
   quickSortAsc(a, 0, a.length-1);
  else
   quickSortDesc(a, 0, a.length-1);
 }
 private static void quickSortAsc(int[] a, int start, int end) {
  if (start >= end)
   return;
  int i = start;
  int j = end;
  int index = end;
  while (i < j) {
   while (a[j] > a[index]) {
    j--;
   }
   if (j != index && a[j] == a[index]) {
    index = swap(a, --j, index);
   } else {
    index = swap(a, j, index);
   }
   while (a[index] > a[i]) {
    i++;
   }
   if (i != index && a[i] == a[index]) {
    index = swap(a, ++i, index);
   } else {
    index = swap(a, i, index);
   }
  }
  quickSortAsc(a, start, index - 1);
  quickSortAsc(a, index + 1, end);
 }
 private static void quickSortDesc(int[] a, int start, int end) {
  if (start >= end)
   return;
  int i = start;
  int j = end;
  int index = end;
  while (i < j) {
   while (a[j] < a[index]) {
    j--;
   }
   if (j != index && a[j] == a[index]) {
    index = swap(a, --j, index);
   } else {
    index = swap(a, j, index);
   }
   while (a[index] < a[i]) {
    i++;
   }
   if (i != index && a[i] == a[index]) {
    index = swap(a, ++i, index);
   } else {
    index = swap(a, i, index);
   }
  }
  quickSortDesc(a, start, index - 1);
  quickSortDesc(a, index + 1, end);
 }
 private static int swap(int[] a, int n, int index) {
  int tmp = a[n];
  a[n] = a[index];
  a[index] = tmp;
  return n;
 }
// ----------------华-丽-的-功-能-分割-线------------------
 /**
  * 堆排序
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void heapSort(int[] a,int sort){
  if (sort==ASC)
   heapSortAsc(a);
  else
   heapSortDesc(a);
 }
 public static void heapSortAsc(int[] a) {
  // 建立最大堆
  int size = a.length;
  for (int i = size / 2 - 1; i >= 0; i--) {
   createBigHeap(a, i, size - 1);
  }
  // 排序
  for (int j = 0; j < size - 1; j++) {
   int tmp = a[0];
   a[0] = a[size - 1 - j];
   a[size - 1 - j] = tmp;
   createBigHeap(a, 0, size - 2 - j);
  }
 }
 private static void createBigHeap(int[] a, int start, int end) {
  int tmp = a[start];
  int j = 2 * start + 1;
  while (j <= end) {
   if (j < end && a[j] < a[j + 1]) {
    j++;
   }
   if (a[j] > tmp) {
    a[start] = a[j];
    start = j;
    j = 2 * j + 1;
   } else {
    break;
   }
  }
  a[start] = tmp;
 }
 public static void heapSortDesc(int[] a) {
  // 建立最小堆
  int size = a.length;
  for (int i = size / 2 - 1; i >= 0; i--) {
   createSmallHeap(a, i, size - 1);
  }
  // 排序
  for (int j = 0; j < size - 1; j++) {
   int tmp = a[0];
   a[0] = a[size - 1 - j];
   a[size - 1 - j] = tmp;
   createSmallHeap(a, 0, size - 2 - j);
  }
 }
 private static void createSmallHeap(int[] a, int start, int end) {
  int tmp = a[start];
  int j = 2 * start + 1;
  while (j <= end) {
   if (j < end && a[j] > a[j + 1]) {
    j++;
   }
   if (a[j] < tmp) {
    a[start] = a[j];
    start = j;
    j = 2 * j + 1;
   } else {
    break;
   }
  }
  a[start] = tmp;
 }
// ----------------华-丽-的-功-能-分割-线---------------------
 /**
  * 插入排序
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void insertSort(int[] a,int sort){
  if (sort==ASC){
   insertSortAsc(a);
  }else{
   insertSortDesc(a);
  }
 }
 public static void insertSortAsc(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
   int n = i + 1;
   int tmp = a[n];
   for (int j = i; j >= 0; j--) {
    if (tmp < a[j]) {
     a[n] = a[j];
     n = j;
    }
   }
   if (a[n] != tmp)
    a[n] = tmp;
  }
 }
 public static void insertSortDesc(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
   int n = i + 1;
   int tmp = a[n];
   for (int j = i; j >= 0; j--) {
    if (tmp > a[j]) {
     a[n] = a[j];
     n = j;
    }
   }
   if (a[n] != tmp)
    a[n] = tmp;
  }
 }
// ----------------华-丽-的-功-能-分割-线--------------------
 /**
  * 折半插入排序
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void halfInsertSort(int[] a,int sort){
  if (sort==ASC){
   halfInsertSortAsc(a);
  }else{
   halfInsertSortDesc(a);
  }
 }
 public static void halfInsertSortAsc(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
   int n = i + 1;
   int tmp = a[n];
   if (tmp > a[i])
    continue;
   int low = 0;
   int high = i;
   int mid = (high + low) / 2;
   while (high >= low) {
    mid = (high + low) / 2;
    if (tmp < a[mid]) {
     high = mid - 1;
    } else if (tmp > a[mid]) {
     low = mid + 1;
    } else {
     low = mid;
     break;
    }
   }
   for (int j = n; j > mid; j--) {
    a[j] = a[j - 1];
   }
   a[low] = tmp;
  }
 }
 public static void halfInsertSortDesc(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
   int n = i + 1;
   int tmp = a[n];
   if (tmp < a[i])
    continue;
   int low = 0;
   int high = i;
   int mid = (high + low) / 2;
   while (high >= low) {
    mid = (high + low) / 2;
    if (tmp > a[mid]) {
     high = mid - 1;
    } else if (tmp < a[mid]) {
     low = mid + 1;
    } else {
     low = mid;
     break;
    }
   }
   for (int j = n; j > mid; j--) {
    a[j] = a[j - 1];
   }
   a[low] = tmp;
  }
 }
// ----------------华-丽-的-功-能-分割-线----------------------
 /**
  * 希尔排序
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void shellSort(int[] a,int sort){
  if (sort==ASC){
   shellSortAsc(a,a.length);
  }else{
   shellSortDesc(a,a.length);
  }
 }
 public static void shellSortAsc(int[] a, int n) {
  int i, j, k, temp, gap;
  int[] gaps = { 1, 5, 13, 43, 113, 297, 815, 1989, 4711, 11969, 27901,
    84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
    58548857, 157840433, 410151271, 1131376761, 2147483647 };
  for (k = 0; gaps[k] < n; k++)
   ;
  while (--k >= 0) {
   gap = gaps[k];
   for (i = gap; i < n; i++) {
    temp = a[i];
    j = i;
    while (j >= gap && a[j - gap] > temp) {
     a[j] = a[j - gap];
     j = j - gap;
    }
    a[j] = temp;
   }
  }
 }
 public static void shellSortDesc(int[] a, int n) {
  int i, j, k, temp, gap;
  int[] gaps = { 1, 5, 13, 43, 113, 297, 815, 1989, 4711, 11969, 27901,
    84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,
    58548857, 157840433, 410151271, 1131376761, 2147483647 };
  for (k = 0; gaps[k] < n; k++)
   ;
  while (--k >= 0) {
   gap = gaps[k];
   for (i = gap; i < n; i++) {
    temp = a[i];
    j = i;
    while (j >= gap && a[j - gap] < temp) {
     a[j] = a[j - gap];
     j = j - gap;
    }
    a[j] = temp;
   }
  }
 }
// ----------------华-丽-的-功-能-分割-线---------------------
 /**
  * 选择排序
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void selectSort(int[] a,int sort){
  if (sort==ASC){
   selectSortAsc(a);
  }else{
   selectSortDesc(a);
  }
 }
 public static void selectSortAsc(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
   int min = i;
   for (int j = i + 1; j < a.length; j++) {
    if (a[j] < a[min])
     min = j;
   }
   if (min != i) {
    int tmp = a[i];
    a[i] = a[min];
    a[min] = tmp;
   }
  }
 }
 public static void selectSortDesc(int[] a) {
  for (int i = 0; i < a.length - 1; i++) {
   int max = i;
   for (int j = i + 1; j < a.length; j++) {
    if (a[j] > a[max])
     max = j;
   }
   if (max != i) {
    int tmp = a[i];
    a[i] = a[max];
    a[max] = tmp;
   }
  }
 }
// ----------------华-丽-的-功-能-分割-线---------------------
 /**
  * 归并排序
  *
  * @param a sort Array
  * @param sort SortUtil.ASC,SortUtil.DESC
  */
 public static void mergeSort(int[] a,int sort){
  // 找出中间值
  int mid = a.length / 2;
  // 申请空间存储中间索引以左的值
  int[] left = setValue(a, 0, mid);
  if (left.length > 1) {// 继续拆分左边，直到元素值为1个
   mergeSort(left,sort);
  }
  // 申请空间存储中间索引以右的值
  int[] right = setValue(a, mid, a.length);
  if (right.length > 1) {// 继续拆分右边，直到元素值为1个
   mergeSort(right,sort);
  }
  if (sort==ASC){
   mergeAsc(a, left, right);
  }else{
   mergeDesc(a, left, right);
  }
 }
 private static void mergeAsc(int[] a, int[] left, int[] right) {
  int i = 0, j = 0, k = 0;
  for (; i < left.length && j < right.length;) {
   if (left[i] < right[j]) {
    a[k++] = left[i++];
   } else {
    a[k++] = right[j++];
   }
  }
  for (; i < left.length; i++) {
   a[k++] = left[i];
  }
  for (; j < right.length; j++) {
   a[k++] = right[j];
  }
 }
 private static void mergeDesc(int[] a, int[] left, int[] right) {
  int i = 0, j = 0, k = 0;
  for (; i < left.length && j < right.length;) {
   if (left[i] > right[j]) {
    a[k++] = left[i++];
   } else {
    a[k++] = right[j++];
   }
  }
  for (; i < left.length; i++) {
   a[k++] = left[i];
  }
  for (; j < right.length; j++) {
   a[k++] = right[j];
  }
 }
 private static int[] setValue(int[] a, int start, int length) {
  int[] x = new int[length - start];
  for (int i = 0; i < x.length; i++) {
   x[i] = a[start++];
  }
  return x;
 }
}

希望本文所述对大家Java程序设计有所帮助。