2. Exchange sort (bubble sort, quick sort)
3. Select sort (select sort, heap sort)
4. Merge and sort
[](
)1, Insert sort
=========================================================================
Insertion sorting is an internal sorting method, which moves the internal elements to be sorted to the appropriate position by inserting
That is, all elements are regarded as two parts, one is ordered and the other is disordered. At the beginning, the ordered part is one element, while the disordered part is n-1 elements. When sorting, the first element in the disordered sequence is compared with the ordered queue, and it is placed in an appropriate position to form a new ordered table.
//Insert sort
public static void insertionSort(int []array){
for(int i=1;i<array.length;i++){
int tmp=array[i];
int j=i-1;
for(;j>=0;j--){
if(array[j]>tmp){//
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=tmp;
}
}
The average time complexity of insertion sorting is O (n^2), the best case is O (n), the worst case is O (n^2), the space complexity is O (1), stability: stable
[](
)2, Hill sort
=========================================================================
Hill sort is an optimized insertion sort. A group of data is divided into n groups, and then exchanged within the group,
The value of a given group can be a fixed value, which is generally the length of the array divided by two
public static void shellSort(int []array){
int []drr={5,2,1};
for (int i = 0; i <drr.length ; i++) {
shell(array,drr[i]);
}
}
public static void shell(int []array,int gap){
for(int i=gap;i<array.length;i++){
int tmp=array[i];
int j=i-gap;
for(;j>=0;j=j-gap){
if(array[j]>tmp){
array[j+gap]=array[j];
}else {
break;
}
}
array[j+gap]=tmp;
}
}
The average time complexity of hill sorting is O (n^1.3~1.5), the best case is O (n), and the worst case is n square. The spatial complexity is O (1).
Stability: unstable.
[](
)3, Bubble sorting
=========================================================================
Optimizing bubble sorting is to insert a boolean variable to check whether it is exchanged. If there is no exchange, it indicates that it has been orderly and exits.
public static void bubbleSort(int []array){
for(int i=0;i<array.length-1;i++){
boolean flg=false;
for(int j=0;j<array.length-1-i;j++){
if(array[j]>array[j+1]){
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
flg=true;
}
}
if(flg==false){
break;
}
}
}
The time complexity of bubble sorting is O (n^2). The best case is O (n), that is, the array is an ordered traversal without exchanging elements. The spatial complexity is O (1) stability: stability
[](
)4, Select sort
=========================================================================
public static void selectSort(int []array){
for(int i=0;i<array.length;i++){
for(int j=i+1;j<array.length;j++){
if(array[j]<array[i]){
int tmp=array[j];
array[j]=array[i];
array[i]=tmp;
}
}
}
}
The time complexity of sorting is the best and worst. The space complexity is O (n^2). Stability: unstable
[](
)5, Heap sort
========================================================================
Heap sorting is to create a heap first. The root of each subtree of the heap is the largest, then exchange the tail element with the root, then rebuild the heap, find the largest number again, put it at the root, and continue the exchange
//Heap sorting should be done from small to large (you can know that the top is the largest)
public static void heapSort(int []array){
createHeap(array);
int end=array.length-1;
// while() {/ / create a lot of loops. Each time, it is the node with the largest header and the largest exchange tail
while (end>0){
int tmp=array[0];
array[0]=array[end];
array[end]=tmp;
adjust(array,0,end);
end--;
}
}
public static void adjust(int []array,int parent,int len){
int child=2*parent+1;
while(child<len){
if(child+1<len&&array[child+1]>array[child]){
> **This article has been[CodeChina Open source project: [first tier big factory] Java Analysis of interview questions+Core summary learning notes+Real project practice+Latest explanation Video]](https://codechina.csdn.net/m0_60958482/java-p7), self-taught programming route and a series of technical articles are continuously updated**