java:排序算法代码

落日映苍穹つ 2022-08-18 13:23 124阅读 0赞

package com.sort;
    
    /*选择排序
     * 每一轮比较得出一个最小值
    */
    public class ChoseSort
    {
    	//对数组进行从小到大排序
    	public static void sort(int[] arr)
    	{
    		for(int i = 0; i < arr.length - 1; i++) //当前元素
    		{
    			for(int j = i+1; j < arr.length; j++)  //和它后面的元素进行比较，得出最小值
    			{
    				if(arr[i] > arr[j])
    				{
    					int tmp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = tmp;
    				}
    			}
    		}
    		
    	}
    	
    	//打印数组
    	public static void print(int[] arr)
    	{
    		for(int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] + " ");
    		}
    		
    		System.out.println();
    	}
    	
    	
    	
    	public static void main(String[] args)
    	{
    		int[] arr = {4,6,1,9,3,5};
    		sort(arr);
    		
    		print(arr);
    	}
    
    }

<pre name="code" class="java">package com.sort;
    
    /*冒泡排序
     * 
     * 相邻两元素进行比较，大的元素往后放，每一轮遍历得出一个最大值
     * */
    
    public class PopSort 
    {
    	//冒泡排序
    	public static void sort(int[] arr)
    	{
    		for(int i = 0; i < arr.length -1; i++)  //比较的次数
    		{
    			for(int j = 0; j < arr.length - 1 - i; j++)  //当前元素与它后面的元素比较
    			{
    				if(arr[j] > arr[j+1])
    				{
    					int tmp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = tmp;
    				}
    			}
    		}
    			
    	}
    	
    	//打印数组
    	public static void print(int[] arr)
    	{
    		for(int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] + " ");
    		}
    		
    		System.out.println();
    	}
    	
    	public static void main(String[] args)
    	{
    		int[] arr = {5,3,1,9,8,2};
    		sort(arr);
    		
    		print(arr);
    
    	}
    }

<pre name="code" class="java">package com.sort;
    
    /*
     * 插入排序，如同插纸牌
     * */
    
    public class InsertSort 
    {
    	//插入排序
    	public static void sort(int[] arr)
    	{
    		for(int i = 1; i < arr.length; i++)   //从第二个元素开始遍历
    		{
    			int tmp = arr[i];  //保存当前要插入的元素
    			int j = i-1;  //从当前位置的前一个位置开始，从后往前
    			 
    			while(j >= 0 && arr[j] > tmp)  //从下标i-1开始从后往前，大于arr[i]的元素右移一位
    			{
    				arr[j+1] = arr[j];
    				j--;
    			}
    			
    			arr[j+1] = tmp;  //arr[i]填在空位上
    		}
    	}
    
    	//打印数组
    	public static void print(int[] arr)
    	{
    		for(int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] + " ");
    		}
    		
    		System.out.println();
    	}
    	
    	public static void main(String[] args)
    	{
    		int[] arr = {6,1,2,9,8,7};
    		sort(arr);
    		
    		print(arr);
    	}
    }

package com.sort;  
  
  
/\*  
 \* 快速排序：  
 \*  1.先从数列中取出一个数作为基准数  
 \*  2.分区：根据该基准值，把比该基准值大的数放在右边，比基准值小的数放在左边  
 \*  3.重复前两步，直到每个区间只剩一个元素  
 \* \*/  
  
public class FastSort   
\{  
//快速排序,参数：arr:数组， low:数组区域的最小下标，high:数组区域的最大下标  
public static void sort(int\[\] arr, int low, int high)  
\{  
if(low >= high)   //如果区域里只剩一个元素，退出  
\{  
return;  
\}  
  
int i = low;  //记录最小下标  
int j = high;  //记录最大下标  
  
int index = arr\[i\];  //把区域的第一个元素作为基准值  
  
//分两路遍历---从前往后，从后往前，按基准值分区  
while(i < j)  
\{  
//从后往前遍历，找到元素arr\[j\] < 基准值  
while(i < j && arr\[j\] >= index)  
\{  
j --;  
\}  
if(i < j)  //arr\[j\]补在arr\[i\]位置上  
\{  
arr\[i\] = arr\[j\];  
i++;  
\}  
  
//从前往后遍历，找到元素arr\[i\] > 基准值  
while(i < j && arr\[i\] < index)  
\{  
i ++;  
\}  
if(i < j)  //arr\[i\]补在arr\[j\]位置上  
\{  
arr\[j\] = arr\[i\];  
j--;  
\}  
  
arr\[i\] = index;  //基准值补在arr\[i\]位置上  
  
sort(arr, low, i-1);  //递归的对分区元素排序  
sort(arr, i+1, high);  
  
\}  
\}  
  
//打印数组  
public static void print(int\[\] arr)  
\{  
for(int i = 0; i < arr.length; i++)  
\{  
System.out.print(arr\[i\] + " ");  
\}  
  
System.out.println();  
\}  
  
public static void main(String\[\] args)  
\{  
int\[\] arr = \{9,2,1,8,6,7\};  
sort(arr, 0, arr.length-1);  
  
print(arr);  
\}  
  
  
\}

package com.sort;
    
    /*
     * 归并排序：
     * 
     *1.递归的进行折半，将一个数组分成两个数组A,B
     *2.如果两个数组都是有序的，则可以很容易把它们合并成一个数组
     *3.怎样保证两个数组是有序的呢？当每个数组中只有一个元素时，可以认定它们是有序的
     * */
    
    public class GuibingSort 
    {
    	//合并两个有序数列arr[first,mid],（mid,end]
    	public static void merge(int[] arr, int first, int mid, int end)
    	{
    		//分别保存arr[first,mid]和(mid,end]
    		int[] A = new int[mid-first+1];
    		int[] B = new int[end-mid];
    		
    		//用A保存arr[first,mid]
    		for(int i = first,j = 0; i <= mid; i++)
    		{
    			A[j++] = arr[i];
    		}
    		
    		//用B保存arr(mid,end]
    		for(int i = mid+1, j = 0; i <= end; i++)
    		{
    			B[j++] = arr[i];
    		}
    		
    		//将有序数组A,B进行合并成arr[first,end]
    		int i = 0;
    		int j = 0;
    		int k = first;
    		
    		//遍历数组A、B,逐一比较，将较小的元素存放在arr中
    		while(i < A.length && j < B.length)
    		{
    			if(A[i] <= B[j])
    			{
    				arr[k++] = A[i++];
    			}
    			else
    			{
    				arr[k++] = B[j++];
    			}
    		}
    		
    		//数组A、B剩下的片段，加入arr中
    		if(i < A.length)
    		{
    			for(int m = i; m < A.length; m++)
    			{
    				arr[k++] = A[m];
    			}
    		}
    		
    		if(j < B.length)
    		{
    			for(int m = j; m < B.length; m++)
    			{
    				arr[k++] = B[m];
    			}
    		}
    	}
    	
    	//打印数组
    	public static void print(int[] arr)
    	{
    		for(int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] +" ");
    		}
    		
    		System.out.println();
    	}
    	
    	//归并排序
    	public static void mergeSort(int[] arr, int first, int end)
    	{
    		if(first < end)  //当数组序列中的元素个数大于1时（也就是说：递归的终止条件是，每个序列中只有一个元素）
    		{
    			int mid = (first + end) / 2; //递归折半
    			mergeSort(arr, first, mid);
    			mergeSort(arr, mid+1, end);
    			merge(arr, first, mid, end); //合并
    		}
    	}
    	
    	
    	public static void main(String[] args)
    	{
    		int[] arr = new int[]{5, 1, 7, 3, 9, 0};
    		
    		mergeSort(arr, 0, arr.length-1);
    		
    		print(arr);
    	}
    
    }

package com.sort;
    
    /*希尔排序：（缩小增量排序）
     * 1.根据步长对数组元素进行分组
     * 2.每组内的元素进行插入排序
     * 3.步长逐渐减小，当步长为1时，进行插入排序后，完成排序
     * 出发点：插入排序对基本有序的数组，效率较高
     * */
    
    public class ShellSort
    {
    	//希尔排序
    	public static void ShellSort(int[] arr)
    	{
    		//gap:分组的步长,在这规定步长每组减半
    		for(int gap = arr.length / 2; gap > 0; gap /= 2)
    		{
    			for(int i = 0; i < gap; i++)  //每一组内进行插入排序
    			{
    				for(int j = i + gap; j < arr.length; j += gap)
    				{
    					int tmp = arr[j];
    					int k = j - gap;
    					
    					while(k >= 0 && arr[k] > tmp)
    					{
    						arr[k+gap] = arr[k];
    						k -= gap;
    					}
    					
    					arr[k+gap] = tmp;
    				}
    			}	
    			
    		}
    			
    	}
    	
    	//打印数组
    	public static void print(int[] arr)
    	{
    		for(int i = 0; i < arr.length; i++)
    		{
    			System.out.print(arr[i] +" ");
    		}
    		
    		System.out.println();
    	}
    	
    	
    	public static void main(String[] args)
    	{
    		int[] arr = new int[]{3, 8, 2, 5, 9, 0};
    		
    		ShellSort(arr);
    		
    		print(arr);
    	}
    
    }

package com.sort;
    
    /*堆排序，从大到小排序
     * 1.把一位数组构建成堆，父节点大于左右儿子节点，第0节点为最小元素节点
     * 2.第0节点与最后一个节点交换，就得到了最小元素，然后在堆序列化
     * 3.重复2
     * */
    
    public class heapSort 
    {
    	//构建堆
    	public static void buildHeap(int[] arr)
    	{
    		int len = arr.length;  //数组元素个数
    		
    		for(int i = len/2 - 1; i >= 0; i--)
    		{
    			heapify(arr, i, len-1);
    		}
    	}
    	
    	//堆化数组arr[]，i为当前元素下标，n为元素个数
    	public static void heapify(int[] arr, int i, int n)
    	{
    	    int temp = arr[i];  
    	    int j = 2 * i + 1;  //左孩子
    	    while (j < n)  
    	    {  
    	        if (j + 1 < n && arr[j + 1] < arr[j]) //如果有右孩子，在左右孩子中找最小的  
    	            j++;  
    	  
    	        if (arr[j] >= temp)  //如果最小的孩子都比它小，退出循环
    	            break;  
    	        else        //与最小的孩子交换
    	        {
    	            arr[i] = arr[j];     //把较小的子结点往上移动,替换它的父结点  
    		        i = j;  
    		        j = 2 * i + 1; 	
    	        }
    	     
    	    }  
    	    
    	    arr[i] = temp;  
    	}
    	
    	//堆排序
    	public static void HeapSort(int[] arr)
    	{
    		buildHeap(arr);
    		
    		for(int i = arr.length - 1; i >= 0; i--)
    		{
    			int tmp = arr[0];    //第0元素为最小元素，交换到最后面
    			arr[0] = arr[i];
    			arr[i] = tmp;
    			
    			heapify(arr, 0, i-1);  //数组堆序列换，次小元素升至0位置
    		}
    	}
    	
    	
    	//打印数组
    	public static void print(int[] arr)
    	{
    		for(int i = 0; i < arr.length; i ++)
    		{
    			System.out.print(arr[i] +" ");
    		}
    		
    		System.out.println();
    	}
    	
    	public static void main(String[] args)
    	{
    		int[] arr = {5,4,9,8,7,6,0,1,3,2};
    		print(arr);
    		
    		//构建堆
    		buildHeap(arr);
    		print(arr);
    		
    		HeapSort(arr);
    		print(arr);
    	}
    
    }