Java 排序算法总结(冒泡,选择,插入,希尔)

╰+哭是因爲堅強的太久メ 2022-08-07 08:36 138阅读 0赞

亲手写了四个数组排序的算法实现代码，记录下，后面再补充其他排序算法^\_^

Java数组排序总结(冒泡,选择,插入,希尔)

实现代码：

public class SortAll 
    {
    	public static void main(String args[])
    	{
    		int[] m = {11,23,435,232,44,3421,454,45,4543,66,4654,53,34};
    		 
    		System.out.println("------冒泡排序（Bubble Sort）-----"); 
    		maoPao(m);
    		System.out.println();
    		 
    		System.out.println("------选择排序（Selection sort）-----");
    		xuanZe(m);
    		System.out.println();
    		
    		System.out.println("------插入排序（insertion sort）-----");
    		chaRu(m);
    		System.out.println();
    		
    		System.out.println("------希尔排序（Shell sort）-----");
    		shell(m);
    		System.out.println();
    	} 
    	
    	//它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
    	//走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
    	public static void maoPao(int[] m)
    	{
    		for(int i=0;i<m.length;i++)
    		{
    			for(int j=i+1;j<m.length;j++)
    			{
    				int a = m[i];
    				if(m[i]>m[j])
    				{
    					m[i] = m[j];
    					m[j] = a; 
    				}
    			}
    		}
    		
    		for(int i=0;i<m.length;i++)
    		{
    			System.out.print(m[i]+" ");
    		}
    	}
    	
    	//每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
    	//选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
    	public static void xuanZe(int[] m)
    	{
    		for(int i=0;i<m.length;i++)
    		{
    			int index = i;
    			for(int j=i;j<m.length;j++)
    			{ 
    				// 找出最小的那个数的下标
    				if(m[index]>m[j])
    				{
    					index = j;
    				} 
    			}
    			int a = m[i];
    			m[i] = m[index];
    			m[index] = a;
    		}
    		for(int i:m)
    		{
    			System.out.print(i+" ");
    		}
    	}
    	
    	//	插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。
    	//	是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
    	//	而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
    	public static void chaRu(int[] m)
    	{
    		// i从1开始，第一个数看成已经排过序了
    		for(int i=1;i<m.length;i++)
    		{
    			for(int j=i;j>0;j--)
    			{
    				if(m[j]<m[j-1])
    				{
    					int a = m[j];
    					m[j] = m[j-1];
    					m[j-1] = a;
    				}
    			}
    		}
    		
    		for(int i:m)
    		{
    			System.out.print(i+" ");
    		}
    	}
    	
    	// 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；
    	// 当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。
    	public static void shell(int[] m)
    	{
    		for(int increment = m.length;increment>0;increment /= 2)
    		{
    			for(int i=increment;i<m.length;i++)
    			{
    				int a = m[i];
    				int j = 0;
    				for(j=i;j>=increment;j-=increment)
    				{
    					if(a<m[j-increment])
    					{
    						m[j] = m[j-increment];
    					}
    					else
    					{
    						break;
    					}
    					m[j] = a;
    				} 
    			}
    		}
    		
    		for(int i:m)
    		{
    			System.out.print(i+" ");
    		}
    	}
    	
    }

测试结果：

------冒泡排序（Bubble Sort）-----
    11 23 34 44 45 53 66 232 435 454 3421 4543 4654 
    ------选择排序（Selection sort）-----
    11 23 34 44 45 53 66 232 435 454 3421 4543 4654 
    ------插入排序（insertion sort）-----
    11 23 34 44 45 53 66 232 435 454 3421 4543 4654 
    ------希尔排序（Shell sort）-----
    11 23 34 44 45 53 66 232 435 454 3421 4543 4654