This article summarizes various sorting algorithms in Java. Share it for your reference, as follows:
1. Bubble sort:
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. Quick sort (no duplicate values):
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. Quick sort (can include repeated values)
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. Heap sorting
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) { //Create maximum heap size = a.length; for(int i= size/2-1;i>=0;i--){ createBigHeap(a,i,size-1); } //Sorting 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. Insert sort
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. Fold half insert sort
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. Hill sort
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,2 1521774, 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. Select Sort
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. Ordering
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) { //Find out the intermediate value int mid = a.length/2; //Application for space storage The middle index is with the left value int[] left = setValue(a,0,mid); if (left.length>1){//Continue to split the left until the element value is 1 mergeSort(left); } // Apply space to store the middle index with the right value int[] right = setValue(a,mid,a.length); if (right.length>1){//Continue to split the right side until the element value is 1 mergeSort(right ); } //Merge the left and right values 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)); } }Summary:
public class SortUtil { public final static int DESC = -1; public final static int ASC = 1; /** * Bubble sort* @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; } } } } // -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Ability-Segment-Line------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 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 inde x = 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 qui ckNoRepeatSortDesc(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); } /** * Quick sort (repeat value allowed) * * @param a sort Array * @param sort SortUtil.ASC,SortUtil.DESC */ publi c 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 voi d 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 i nt 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) { // Create maximum heap int size = a.length; for (int i = size / 2 - 1; i >= 0; i--) { createBigHeap(a, i , size - 1); } // Sort 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) { // Create minimum heap int size = a.length; for (int i = size / 2 - 1; i >= 0; i--) { createSmallHeap(a, i, size - 1); } // Sort 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; } // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------ /** * Insert sort* * @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; } } // -- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- * Half insert sort* * @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; } } // ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------- /** * Hill sort* * @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[] gap = { 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) { ga p = 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; } } } // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --- /** * Select sort* * @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; } } } // -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -Function-Segmentation-line---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- SortUtil.DESC */ public static void mergeSort(int[] a,int sort){ // Find the intermediate value int mid = a.length / 2; // Apply for space to store the intermediate index with the left value int[] left = setValue(a, 0, mid); if (left.length > 1) {// Continue to split the left until the element value is 1 mergeSort(left,sort); } // Apply for space to store the value of the middle index to the right int[] right = setValue(a, mid, a.length); if (right.length > 1) {// Continue to split the right side until the element value is 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; } }I hope this article will be helpful to everyone's Java programming.