冒泡,选择,插入排序

Posted on | In |

冒泡排序 O(n2)

基本思想

两个数比较大小，较大的数下沉，较小的数冒起来。

过程

比较相邻的两个数据，如果第二个数小，就交换位置。
从后向前两两比较，一直到比较最前两个数据。最终最小数被交换到起始的位置，这样第一个最小数的位置就排好了。
继续重复上述过程，依次将第2.3…n-1个最小数排好位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package Sort;
import java.util.Scanner;
public class BubbleSort {
	public static void BubbleSort(int a[],int n)
	{
	    for(int i=0;i<n-1;i++)
	    {
	        for(int j=0;j<n-i-1;j++)
	        {
	            if(a[j]>a[j+1])
	            {
	                int temp=a[j];
	                a[j]=a[j+1];
	                a[j+1]=temp;

	            }

	        }

	    }
	}
	public static void main(String[] args)
	{
		
		   int[] a=new int[20];
		   Scanner in = new Scanner(System.in);
		   int n=in.nextInt();
		   for(int i=0;i<n;i++)
		    a[i]=in.nextInt();
		   BubbleSort(a,n);
		   for(int i=0;i<n;i++)
		    System.out.print(a[i]+" ");
	}
}

优化：

针对问题：
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

方案：
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

改进后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package Sort;
import java.util.Scanner;
public class BubbleSort {
	public static void BubbleSort(int a[],int n)
	{
	    for(int i=0;i<n-1;i++)
	    {
	    	boolean flag=false;
	        for(int j=0;j<n-i-1;j++)
	        {
	            if(a[j]>a[j+1])
	            {
	                int temp=a[j];
	                a[j]=a[j+1];
	                a[j+1]=temp;
	                flag=true;

	                
	            }

	        }
	        if(!flag) break;
	    }
	}
	public static void main(String[] args)
	{
		
		   int[] a=new int[20];
		   Scanner in = new Scanner(System.in);
		   int n=in.nextInt();
		   for(int i=0;i<n;i++)
		    a[i]=in.nextInt();
		   BubbleSort(a,n);
		   for(int i=0;i<n;i++)
		    System.out.print(a[i]+" ");
	}
}

选择排序 O(n2)

基本思想

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
….
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
image

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package Sort;
import java.util.Scanner;
public class SelectionSort {
	public static void SelctionSort(int a[],int n)
	{
	    for(int i=0;i<n-1;i++)
	    {
	        for(int j=i+1;j<n;j++)
	        {
	            if(a[i]>a[j])
	            {
	                int temp=a[i];
	                a[i]=a[j];
	                a[j]=temp;
	            }

	        }

	    }
	}
	public static void main(String[] args)
	{
		
		   int[] a=new int[20];
		   Scanner in = new Scanner(System.in);
		   int n=in.nextInt();
		   for(int i=0;i<n;i++)
		    a[i]=in.nextInt();
		   SelctionSort(a,n);
		   for(int i=0;i<n;i++)
		    System.out.print(a[i]+" ");
	}
}

插入排序 O(n2)

基本思想

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package Sort;
import java.util.Scanner;
public class InsertionSort {
	public static void InsertionSort(int a[],int n)
	{
	    for(int i=0;i<n-1;i++)
	    {
	        for(int j=i+1;j>0;j--)
	        {
	            if(a[j]<a[j-1])
	            {
	                int temp=a[j];
	                a[j]=a[j-1];
	                a[j-1]=temp;
	            }

	        }

	    }
	}
	public static void main(String[] args)
	{
		
		   int[] a=new int[20];
		   Scanner in = new Scanner(System.in);
		   int n=in.nextInt();
		   for(int i=0;i<n;i++)
		    a[i]=in.nextInt();
		   InsertionSort(a,n);
		   for(int i=0;i<n;i++)
		    System.out.print(a[i]+" ");
	}
}

平均时间复杂度：O(n2)