The efficiency of sorting is generally compared from three aspects: the number of data comparisons, the number of data moves, and the amount of memory space occupied.
Let’s make a general comparison of bubble sort, selection sort, insertion sort, and quick sort. Bubble sorting algorithm is generally not used because its number of comparisons and moves is the largest among several sorting algorithms. Its only advantage is that the algorithm is simple and easy to understand, so it can be used when the amount of data is small. There will be some application value. Selection sort has the same number of comparisons as bubble sort, which is n squared, but it reduces the number of exchanges to a minimum, so it can be applied when the amount of data is small and exchanging data is more time-consuming than comparing data. Select sort.
In most cases, when the amount of data is relatively small or basically ordered, the insertion sort algorithm is the best choice. For sorting larger amounts of data, quicksort is usually the best method.
The above sorting algorithm takes up very little memory space and only requires an additional variable to temporarily store the data items during exchange. Therefore, there is no comparison in the size of the memory space occupied.
The number of comparisons of insertion sort is still n squared, but in general, it is twice as fast as bubble sort and a little faster than selection sort. It is often used in the final stages of complex sorting algorithms, such as quicksort.
Algorithm: After i-1 processing, L[1..i-1] has been sorted. The i-th pass only inserts L[i] into the appropriate position of L[1..i-1],
So that L[1..i] is an ordered sequence again. To achieve this goal, we can use sequential comparison.
First compare L[i] and L[i-1]. If L[i-1]<=L[i], then L[1..i] has been sorted and the i-th pass of processing is over;
Otherwise, exchange the positions of L[i] and L[i-1], and continue to compare L[i-1] and L[i-2] until a certain position j (1≤j≤i-1) is found.
Until L[j] ≤L[j+1]
Advantages: fewer elements are moved and only an auxiliary space is needed
Time complexity n*n
This is a good sorting method when the number n of records to be sorted is small. But when n is very large, it is inappropriate
For example: int[] values = { 5, 2, 4, 1, 3 };
Sorting process:
1st time: 2,5,4,1,3
2nd time: 2,4,5,1,3
3rd time: 1,2,4,5,3
4th time: 1,2,3,4,5
java code:
Copy the code code as follows:
public class InsertSort {
public static void main(String[] args) {
int[] values = { 5, 2, 4, 1, 3 };
sort(values);
for (int i = 0; i < values.length; ++i) {
System.out.println(values[i]);
}
}
public static void sort(int[] values) {
int temp;
int j = 0;
for (int i = 1; i < values.length; i++) {
if(values[i]<values[i-1])//The judgment here is very important. This reflects the reason why insertion sort is faster than bubble sort and selection sort.
{
temp = values[i];
//Move data backward
for (j=i-1; j>=0 && temp<values[j]; j--)
{
values[j+1] =values[j];
}
//Insert data to position j+1
values[j+1] =temp;
System.out.print("th" + (i + 1) + "th:");
for (int k = 0; k < values.length; k++) {
System.out.print(values[k]+",");
}
System.out.println("");
}
}
}
}
Second example
Copy the code code as follows:
package cn.cqu.coce.xutao;
public class zhijiecharu {
public static void main(String args[]){
int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
int i,j,k;
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
for(i=1;i<a.length;i++){
for(j=i-1;j>=0;j--)
if(a[i]>a[j])
break;
if(j!=i-1){
int temp;
temp=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];
a[k+1]=temp;
}
}
for(i=0;i<a.length;i++)
System.out.print(a[i]+"/t");
System.out.println();
}
}