Java中几种排序算法

怼烎@ 2023-06-04 06:54 52阅读 0赞

1、冒泡排序算法  
通过多次比较（相邻两个数）和交换来实现排序

public class bubble { 
    	public static void bubbleSort(int[] a) { 
    		 int temp;
    		 for (int i = 1; i < a.length; i++) { 
                  //将相邻两个数进行比较，较大的数往后冒泡
            	  for (int j = 0; j < a.length - i; j++) { 
            		  if (a[j] > a[j + 1]) { 
                       //交换相邻两个数
            			  temp=a[j];
            			  a[j]=a[j+1];
            			  a[j+1]=temp;
            		  }
            	  }
    		 }
    	 } 
    	public static void main(String[] args) { 
    	
    		int[] mao= { 213,123,342,543,12,67,98,320,421,4,15,54,27,34,17};
    		System.out.print("排序前的数组为：\n");  //输出排序前的数组
    		for(int i=0;i<mao.length;i++)
    		{ 
    			System.out.print(mao[i]+" ");
    		}
    		System.out.print("\n");
    		bubbleSort(mao);					//排序操作
    		System.out.print("排序后的数组为：\n");
    		for(int i=0;i<mao.length;i++)
    		{ 
    			System.out.print(mao[i]+" ");  //输出排序后的数组
    		}
    		System.out.print("\n");
    	}
    }

2、直接插入排序  
通过对未排序的数据执行逐个插入至合适的位置而完成排序

public class straight{ 
    	public static void straightInsertion(int[] arr) { 
            int current;//要插入的数
            //从1开始第一次一个数不需要排序
            for (int i = 1; i < arr.length; i++) { 
                current = arr[i];
                int j = i - 1;    //序列元素个数
                //从后往前循环，将大于当前插入数的向后移动
                while (j >= 0 && arr[j] > current) { 
                    arr[j + 1] = arr[j];  //元素向后移动
                    j--;
                }
                arr[j + 1] = current;  //找到位置，插入当前元素
            }
        }
    }

3、快速选择排序  
通过多次比较和交换来实现排序。首先设定一个分界值，将所有数值与分界值比较，左小右大，比较和交换数据值进而完成排序

public class quick{ 
    	static void quickSort(int[] arr,int left,int right)	{ 
    	    int f,t,rtemp,ltemp;
    	    ltemp=left;
    	    rtemp=right;
    	    f=arr[(left+right)/2];		//分界值
    		while(ltemp<rtemp)
    		{ 
    	        while(arr[ltemp]<f)
    			{ 
    				++ltemp;
    			}
    	        while(arr[rtemp]>f) 
    			{ 
    				--rtemp;
    			}
    	        if(ltemp<=rtemp)
    	        { 
    				t=arr[ltemp];
    		        arr[ltemp]=arr[rtemp];
    	    	    arr[rtemp]=t;
    				rtemp--;
    	        	ltemp++;
    			}
    	    }
    	    if(left<rtemp) 
    		{ 
    			quickSort(arr,left,ltemp-1);		//递归调用
    		}
    	    if(ltemp<right) 
    		{ 
    			quickSort(arr,rtemp+1,right);		//递归调用
    		}
    	}
    }

4、希尔排序，又称Shell排序或缩小增量排序  
(1)将有n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1个数据为一对。  
(2)一次循环使每一个序列对排好顺序。  
(3)然后，再变为n/4个序列，再次排序。  
(4)不断重复上述过程，随着序列减少最后变为一个，也就完成了整个排序。

public class shell{ 
    	static void shellSort(int[] a){ 
    	    int h,temp,x=0;
    	    for(int r=a.length/2;r>=1;r/= 2)	//划组排序
    		{ 
    	    	for(int i=r;i<a.length;i++)
    	    	{ 
    				temp=a[i];
    				int j=i-r;
    				while(j>=0 && temp<a[j])
    				{ 
    					a[j+r]=a[j];
    					j-=r;
    				}
    				a[j+r]=temp;
    			}
    			x++;
    		}
    	}
    }

5、堆排序  
构造堆结构、堆排序输出来实现排序

public class pratice { 
    	public static void heapSort(int a[],int n)			
    	{ 
    	    int i,j,h,k;
    	    int t;
    	    for(i=n/2-1;i>=0;i--)    //将a[0,n-1]建成大根堆
    		{ 
    			while(2*i+1<n) 		//第i个结点有右子树 
    			{ 
    				j=2*i+1 ;
    				if((j+1)<n)
    				{             
    				    if(a[j]<a[j+1])			//右左子树小于右子树，则需要比较右子树
    				        j++; 				//序号增加1，指向右子树 
    				}
    				if(a[i]<a[j])				//比较i与j为序号的数据
    				{             
    				    t=a[i];  				//交换数据 
    					a[i]=a[j];
    					a[j]=t;            
    					i=j ;					//堆被破坏，需要重新调整
    				}
    				else 					//比较左右子结点均大则堆未破坏，不再需要调整
    				{ 
    					break;
    				}
    			}
    		}
    		//输出构成的堆
    		System.out.print("原数据构成的堆:");		
    		for(h=0;h<n;h++)
    		{ 
    			System.out.print(" "+a[h]);				//输出
    		}
    		System.out.print("\n");
    	    for(i=n-1;i>0;i--)
    	    { 
    	        t=a[0];							//与第i个记录交换
    	        a[0] =a[i];
    	        a[i] =t;
    			k=0;
    			while(2*k+1<i) 					//第i个结点有右子树 
    			{ 
    				j=2*k+1 ;
    				if((j+1)<i)
    				{             
    				    if(a[j]<a[j+1])			//右左子树小于右子树，则需要比较右子树
    					{ 
    				        j++; 				//序号增加1，指向右子树 
    					}
    				}
    				if(a[k]<a[j])				//比较i与j为序号的数据
    				{             
    				    t=a[k];  				//交换数据 
    					a[k]=a[j];
    					a[j]=t;            
    					k=j ;					//堆被破坏，需要重新调整
    				}
    				else 					//比较左右子结点均大则堆未破坏，不再需要调整
    				{ 
    					break;
    				}
    			}
    	    }
    	}
    }

6、归并排序  
两两合并，进行比较、交换来实现排序

public class marge { 
    	public static void mergeOne(int a[],int b[],int n,int len){  //完成一遍合并的函数 
    	    int i,j,k,s,e;
    	    s=0;
    	    while(s+len<n)  
    	    { 
    	        e=s+2*len-1;
    	        if(e>=n) 						//最后一段可能少于len个结点 
    			{ 
    	            e=n-1;
    			}
    			//相邻有序段合并
    			k=s;
    			i=s;
    			j=s+len;
    			while(i<s+len && j<=e) 			//如果两个有序表都未结束时，循环比较 
    			{ 
    				if(a[i]<=a[j])				//如果较小的元素复制到数组b中 
    				{ 
    				   b[k++]=a[i++];
    				}
    				else
    				{ 
    					b[k++]=a[j++];
    				}
    			}
    			while(i<s+len)					//未合并的部分复制到数组b中 
    			{ 
    				b[k++]=a[i++];
    			}
    			while(j<=e)
    			{ 
    			   b[k++]=a[j++]; 				//未合并的部分复制到数组b中 
    			}
    	        s=e+1; 						//下一对有序段中左段的开始下标 
    	    }
    	    if(s<n) 							//将剩余的一个有序段从数组A中复制到数组b中
    		{ 
    	        for(;s<n;s++)
    			{ 
    	            b[s]=a[s];
    			}
    		}
    	}
    	static void mergeSort(int a[],int n)				//合并排序
    	{ 
    		int h,count,len,f;
    		count=0;							//排序步骤
    	    len=1;     						//有序序列的长度 
    	    f=0;								//变量f作标志
    	    int[] p=new int[n];
    	    while(len<n)
    	    { 
    	        if(f==1)   						//交替在A和P之间合并 
    			{ 
    	            mergeOne(p,a,n,len);			//p合并到a
    			}
    	        else
    			{ 
    	            mergeOne(a,p,n,len);			//a合并到p
    			}
    	        len=len*2;						//增加有序序列长度
    	        f=1-f; 							//使f值在0和1之间切换 
    
    			count++;
    			System.out.printf("第"+count+"步排序结果:");	//输出每步排序的结果
    			for(h=0;h<SIZE;h++)
    			{ 
    				System.out.printf(" "+a[h]);			//输出
    			}
    			System.out.print("\n");
    
    	    }
    	    if(f==1)								//如果进行了排序
    		{ 
    	        for(h=0;h<n;h++)					//将内存p中的数据复制回数组a
    			{ 
    	            a[h]=p[h];
    			}
    		}
    	}
    }

拓展：几种算法的比较  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ5NTY3OA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDQ5NTY3OA_size_16_color_FFFFFF_t_70]: /images/20230601/1fc6978b81a34ad9a1971a3e142558e2.png