Java语言学习八（排序）

比眉伴天荒 2023-07-19 08:08 40阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70]  
排序在编程中经常用到，排序的算法与编程语言无关，所有编程语言都可以使用这些算法实现排序，常用的排序算法包括冒泡排序、选择排序、快速排序和插入排序，近期由于出现大数据分布计算的思想，出现了归并排序，就是将多个有序集合，合并在一起再次优化排序的算法。排序需要使用数组，使用嵌套循环将数组中的元素相互比较，并且互换位置，达到排序目的。不同的排序算法是对数组元素比较和互换的方法不同。

## 冒泡排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 5]

## 选择排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 10]

## 快速排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 12]

public class Test 
    { 
    	public static void main(String[] args) throws Exception
    	{ 
    		int[] a = { 5,8,2,3,9,5,11,7};
    		quickSort(a,0,a.length-1);
    	}
    
    	public static int findFirstElePos(int[] a,int low,int high)
    	{ 
    		int temp = a[low];
    		while(low<high)
    		{ 
    			//从高端向低端查找,只要元素比temp大，高端指针前移
    			while(a[high]>=temp && high>low)
    			{ 
    				high--;
    			}
    			//互换从高端查询到第一个小于temp的元素下标
    			a[low] = a[high];
    			//再从低端向高端查找，只要元素比temp下，低端指针后移
    			while(a[low]<=temp && high>low)
    			{ 
    				low++;
    			}
    			//互换从低端查询到第一个大于temp元素的下标
    			a[high] = a[low];
    		}
    		a[high] = temp;
    		printDim(temp, a);
    		return high;
    	}
    
    	public static void quickSort(int[] a,int low,int high)
    	{ 
    		if(low>high)
    			return;
    		int position = findFirstElePos(a,low,high);
    		quickSort(a,low,position-1);
    		quickSort(a,position+1,high);
    	}
    
    	public static void printDim(int ele,int[] a)
    	{ 
    		System.out.print("元素ele="+ele+":\t");
    		for(int i=0;i<a.length;i++)
    			System.out.print(a[i]+"\t");
    		System.out.println();
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 13]

## 插入排序 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 14]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 16]

public class Test 
    { 
    	public static void main(String[] args) throws Exception
    	{ 
    		int[] a = { 5,8,2,3,9,11,7};
    		for(int i=1;i<a.length;i++)
    		{ 
    			for(int j=0;j<i;j++)
    			{ 
    				int temp = a[i];
    				if(a[j]>temp)
    				{ 
    					a[i] = a[j];
    					a[j] = temp;
    					
    				}
    			}
    			printDim(i,a);
    		}
    
    	}
    
    	public static void printDim(int loop,int[] a)
    	{ 
    		System.out.print("外循环i="+loop+":\t");
    		for(int i=0;i<a.length;i++)
    			System.out.print(a[i]+"\t");
    		System.out.println();
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 17]

## 归并排序 ##

归并排序是将多个已经排序的结果集，合并在一起并重新排序的优化算法，这有利于大量数据分布式排序，最后合并排序。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 18]

import java.util.*;
    
    public class Test 
    { 
    
    	public static void main(String[] args)
    	{ 
    		int[] dim1 = { 2,3,5,1,23,6,79,34,23,4,7};
    		int[] dim2 = { 78,34,65,32,65,77,32,76,1,9};
    		chooseSort(dim1);
    		printDim(dim1);
    		bubbleSort(dim2);
    		printDim(dim2);
    		int[] result = new int[dim1.length+dim2.length];
    		mergeSort(result,dim1,dim2);
    		printDim(result);
    	}
    
    	public static void mergeSort(int[] result,int[] dim1,int[] dim2)
    	{ 
    		int pos1 = 0;
    		int pos2 = 0;
    		int len = 0;
    		int pos = 0;
    		while(pos<result.length)//循环条件，如果合并数组没有全部填满，继续循环
    		{ 
    			for(;pos1<dim1.length;pos1++)//查询第一个数组，从0开始遍历
    			{ 
    				if(pos2==dim2.length)//如果第二个数组已经全部添加到合并数组中，将第一个数组剩余元素全部添加到合并数组
    				{ 
    					len++;
    				}
    				else
    				{ 
    					if(dim1[pos1]<=dim2[pos2])//比较第一个数组指向元素与第二个数组指向元素大小，决定从哪个数组中填充数据到合并数组
    					{ 
    						len++;
    					}
    					else
    						break;
    				}
    			}
    			if(len>0)//如果第一个数组指向元素，比较小，选定为填充的数据
    			{ 
    				for(int i=pos1-len;i<pos1;i++)//向合并数组填充数据，添加len个元素
    				{ 
    					result[pos] = dim1[i];
    					pos++;
    				}
    				len = 0;
    			}
    			for(;pos2<dim2.length;pos2++)//查询第二个数组，从0开始遍历
    			{ 
    				if(pos1 == dim1.length)//如果第一个数组已经全部添加到合并数组中，将第二个数组剩余元素全部添加到合并数组
    				{ 
    					len++;
    				}
    				else
    				{ 
    					if(dim2[pos2]<=dim1[pos1])//比较第二个数组指向元素与第一个数组指向元素大小，决定从哪个数组中填充数据到合并数组
    					{ 
    						len++;
    					}
    					else
    						break;
    				}
    			}
    			if(len>0)//如果第二个数组指向元素，比较小，选定为填充的数据
    			{ 
    				for(int i=pos2-len;i<pos2;i++)//向合并数组填充数据，添加len个元素
    				{ 
    					result[pos] = dim2[i];
    					pos++;
    				}
    				len = 0;
    			}
    		}
    	}
    
    	//选择排序
    	public static void chooseSort(int[] a)
    	{ 
    		for(int i=0;i<a.length;i++)//外循环从0开始循环全部数组元素
    		{ 
    			for(int j=i+1;j<a.length;j++)//内循环从i+1开始查找，数组中最大元素，并放到数组最后
    			{ 
    				if(a[i]>a[j])
    				{ 
    					int temp = a[i];
    					a[i] = a[j];
    					a[j] = temp;
    				}
    			}
    		}
    	}
    
    	//冒泡排序
    	public static void bubbleSort(int[] a)
    	{ 
    		for(int i=0;i<a.length;i++)//外循环从0开始循环全部数组元素
    		{ 
    			for(int j=0;j<a.length-i-1;j++)//比较数组相邻的数组元素
    			{ 
    				if(a[j]>a[j+1])
    				{ 
    					int temp = a[j+1];
    					a[j+1] = a[j];
    					a[j] = temp;
    				}
    			}
    		}
    	}
    
    	public static void printDim(int[] a)
    	{ 
    		for(int i=0;i<a.length;i++)
    			System.out.print(a[i]+"\t");
    		System.out.println();
    	}
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 19]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70]: /images/20230528/db2ca411e2b5486a8ff5b52483771dee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 1]: /images/20230528/faf548deda324f3c8ac4dd8a44b67eab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 2]: /images/20230528/cc9999e73aff4bc8b0a0b0b9e7c7f4fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 3]: /images/20230528/3d9f03a233e1455688028b4223cfe7f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 4]: /images/20230528/3f9c654e5da443cba7ace108021a6f9a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 5]: /images/20230528/9786e549ac4440daa50c0a3439439494.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 6]: /images/20230528/95b3ea5c5f3e40ae89f544be5cab6e38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 7]: /images/20230528/feb901d45f7844c6a3ee337490acede8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 8]: /images/20230528/c589e8440240484693b3d4603f4c1db4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 9]: /images/20230528/2f92f618bc244bcb8359be21ac9faf6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 10]: /images/20230528/48595fa14e3b43b296696e76005b0dcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 11]: /images/20230528/161ab709846c42368a80c2d15bc7594f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 12]: /images/20230528/b85aed20f2be40128fccc03ce28b0e94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 13]: /images/20230528/1d796a5003e940859e7854959a91da12.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 14]: /images/20230528/454a9093112a444688f29432f5fd53f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 15]: /images/20230528/0ac61908e2404333bb371124e9759372.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 16]: /images/20230528/b1dc334d84d04d95b4c205367568e7e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 17]: /images/20230528/103fffe329714954a55b307adc6f4248.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 18]: /images/20230528/4f606136a1d9481e91815c559ce95502.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FpeGlhbmdfY2hlbg_size_16_color_FFFFFF_t_70 19]: /images/20230528/ea72cba6231e4b53beed03ae7e653ccc.png