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

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));  } }

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));  } } 

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));  } } 

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));  } } 

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));  } } 

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));  } } 

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));  } } 

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));  } } 

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;  } }