Java array sort example of bubble sort quick sort hill sort selection sort
- 2020-04-01 03:08:34
- OfStack
Quicksort mainly USES one of the arrays.sort () methods in Arrays.
Bubble method is the use of traversal groups for comparison, through the continuous comparison of the minimum or maximum value one by one traversal out.
The selection sort method takes the first data of an array as the largest or smallest value, and then outputs an ordered array through a comparison loop.
Insertion sort is to select the data in an array, and sort it at the end by continuous insertion comparison.
package com.firewolf.sort;
public class MySort {
public static void main(String[] args) {
int array[] = {45,32,54,12,43,65,11,3,43,6,33,90,44,1,178};
MySort mySort = new MySort();
mySort.insertSort(array);
System.out.print(" Insertion sort result : ");
mySort.printArray(array);
System.out.println();
mySort.bubbleSort(array);
System.out.print(" Bubble sort results : ");
mySort.printArray(array);
mySort.qsort(array);
System.out.println();
System.out.print(" Quicksort result : ");
mySort.printArray(array);
mySort.shellSort(array);
System.out.println();
System.out.print(" Hill sort result : ");
mySort.printArray(array);
mySort.selectSort(array);
System.out.println();
System.out.print(" Select sort result : ");
mySort.printArray(array);
}
public void insertSort(int[] array){
int temp=0;
for(int i=1;i<array.length;i++){
int j=i-1;
temp=array[i];
for(;j>=0&&temp<array[j];j--){
array[j+1]=array[j]; //Moves the value greater than temp back by one unit.
}
array[j+1]=temp;
}
}
public void bubbleSort(int[] array) {
int temp;
for(int i=0;i<array.length;i++){//Train number
for(int j=0;j<array.length-i-1;j++){//More times
if(array[j]>array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
public void qsort(int array[]){
if(array.length>1){
_qsort(array,0,array.length-1);
}
}
private void _qsort(int[] array,int low,int high){
if(low < high){
int middle = getMiddle(array, low, high);
_qsort(array,low,middle-1);
_qsort(array, middle+1, high);
}
}
private int getMiddle(int[] array,int low,int high){
int tmp = array[low];
while(low < high){
while(low < high && array[high] >= tmp)
high--;
array[low] = array[high];
while(low<high && array[low]<=tmp)
low++;
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public void selectSort(int[] array){
int position=0;
for(int i=0;i<array.length;i++){
int j=i+1;
position=i;
int temp=array[i];
for(;j<array.length;j++){
if(array[j]<temp){
temp=array[j];
position=j;
}
}
array[position]=array[i];
array[i]=temp;
}
}
/**
* Hill sort (minimum incremental sort)
* Basic idea: the algorithm starts with a set of Numbers to be sorted by an increment d ( n/2,n Is the number of Numbers to be sorted) into groups with different subscripts of the records in each group d. Direct insert sort of all the elements in each group, and then use a smaller increment ( d/2 ) group it, and then directly insert sort into each group. When the delta goes to zero 1 , after the direct insertion sort, the sort is completed.
* @param array
*/
public void shellSort(int[] array){
double d1=array.length;
int temp=0;
while(true){
d1= Math.ceil(d1/2);
int d=(int) d1;
for(int x=0;x<d;x++){
for(int i=x+d;i<array.length;i+=d){
int j=i-d;
temp=array[i];
for(;j>=0&&temp<array[j];j-=d){
array[j+d]=array[j];
}
array[j+d]=temp;
}
}
if(d==1)
break;
}
}
public void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
}
The following is an example of several sorting methods used separately
Use the sort method of Arrays with quicksort
import java.util.Arrays;
public class Test2{
public static void main(String[] args){
int[] a={5,4,2,4,9,1};
Arrays.sort(a); //sorting
for(int i: a){
System.out.print(i);
}
}
}
Bubble sort algorithm
public static int[] bubbleSort(int[] args){//Bubble sort algorithm
for(int i=0;i<args.length-1;i++){
for(int j=i+1;j<args.length;j++){
if (args[i]>args[j]){
int temp=args[i];
args[i]=args[j];
args[j]=temp;
}
}
}
return args;
}
Selection sorting algorithm
public static int[] selectSort(int[] args){//Selection sorting algorithm
for (int i=0;i<args.length-1 ;i++ ){
int min=i;
for (int j=i+1;j<args.length ;j++ ){
if (args[min]>args[j]){
min=j;
}
}
if (min!=i){
int temp=args[i];
args[i]=args[min];
args[min]=temp;
}
}
return args;
}
Insertion sort algorithm
public static int[] insertSort(int[] args){//Insertion sort algorithm
for(int i=1;i<args.length;i++){
for(int j=i;j>0;j--){
if (args[j]<args[j-1]){
int temp=args[j-1];
args[j-1]=args[j];
args[j]=temp;
}else break;
}
}
return args;
}
Those are the four sorts in Java. The efficiency of different methods is different. The following is the comparison of different algorithms and the big O representation of data exchange.
Bubble sort: compare O(N2) data exchange O(N2)
Selection sort: compare O(N2) data exchange O(N)
Insertion sort: compare O(N2) replication data O(N)
In practice, we should try our best to choose an efficient algorithm.