The quick sorting method mainly uses Arrays.sort() to implement it.
The bubble method is to use traversal arrays to compare, and to traverse the minimum or maximum values one by one through continuous comparison.
The selection sorting method is to use the first data of the array as the largest or smallest value, and then output an ordered array through a comparison loop.
Insert sorting is to select the data in an array and sort it in the end by constantly inserting and comparing it.
The code copy is as follows:
package com.firewolf.sort;
public class MySort {
/**
* @param args
*/
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("insert sort result: ");
mySort.printArray(array);
System.out.println();
mySort.bubbleSort(array);
System.out.print("Bubble sort result: ");
mySort.printArray(array);
mySort.qsort(array);
System.out.println();
System.out.print("Quick sort 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);
}
/**
* Direct insert sort
* Basic idea: In the set of numbers to be sorted, assuming that the previous (n-1)[n>=2] numbers are already in order, now you need to insert the nth number into the ordered number in the preceding order. This makes these n numbers also sorted in order. Repeat this cycle until all are arranged in order
*/
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]; //Move the overall value greater than temp one unit
}
array[j+1]=temp;
}
}
/**
* Bubble sort
* Basic idea: In the set of numbers to be sorted, compare and adjust the two adjacent numbers from top to bottom to make larger numbers to Sink, smaller ones rise up. That is, whenever two adjacent numbers are compared and found that their sorting is opposite to the sorting requirements, they are interchanged.
*/
public void bubbleSort(int[] array) {
int temp;
for(int i=0;i<array.length;i++){//Number of trips
for(int j=0;j<array.length-i-1;j++){//Number of comparisons
if(array[j]>array[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
/**
* Quick sort
* Basic idea: Select a benchmark element, usually the first element or the last element, and through a scan, divide the sequence to be sorted into two parts. Some are smaller than the benchmark element, and some are greater than or equal to the benchmark element. At this time, the benchmark element is The correct position after sorting it, and then the two divided parts are recursively sorted in the same way.
* @param array
*/
public void qsort(int array[]){
if(array.length>1){
_qsort(array,0,array.length-1);
}
}
/**
* Quick sorting for one trip
* @param array
*/
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);
}
}
/**
* Get the intermediate value
*/
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;
}
/**
* Simple selection sort
* Basic idea: among the set of numbers to be sorted, select the smallest number and exchange it with the number in the first position; then find the smallest number and exchange it with the second position among the remaining numbers, and then loop in this way Until the penultimate number is compared with the last number.
* @param array
*/
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 first divides the number to be sorted into several groups according to a certain increment d (n/2, n is the number of numbers to be sorted), and the subscripts recorded in each group are different from d. For each group All elements are sorted directly, then grouped with a smaller increment (d/2), and then sorted directly in each group. When the increment is reduced to 1, the sorting is completed after the direct insertion sort is performed.
* @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=id;
temp=array[i];
for(;j>=0&&temp<array[j];j-=d){
array[j+d]=array[j];
}
array[j+d]=temp;
}
}
if(d==1)
break;
}
}
/**
* Print all elements in the array
*/
public void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
}
Here are some examples of sorting methods used separately
Quick sorting using the sorting method with Arrays
The code copy is as follows:
import java.util.Arrays;
public class Test2{
public static void main(String[] args){
int[] a={5,4,2,4,9,1};
Arrays.sort(a); //Sort
for(int i: a){
System.out.print(i);
}
}
}
Bubble sorting algorithm
The code copy is as follows:
public static int[] bubbleSort(int[] args){//Bubble sorting 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;
}
Select the sorting algorithm
The code copy is as follows:
public static int[] selectSort(int[] args){//Select 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;
}
Insert sorting algorithm
The code copy is as follows:
public static int[] insertSort(int[] args){//Insert sorting 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;
}
The above are four sorting methods in Java. Different methods have different efficiencies. The following is a comparison of different algorithms and a large O representation during data exchange.
Bubble sort: Comparison O(N2) Data exchange O(N2)
Select Sort: Compare O(N2) Data Exchange O(N)
Insert sort: Compare O(N2) Copy data O(N)
In practical applications, we should try to choose efficient algorithms.