用java代码实现各种经典排序算法

￡神魔★判官ぃ 2022-05-19 13:09 211阅读 0赞

1、交换类排序：冒泡排序 ，时间复杂度O(n2，n的2次方)，稳定型排序。

package SoreAlgorithm;
    
    public class SortAlgorithm {
    	public static void main(String args[]) {
    		int[] arr = {4,2,5,6,1,7};
    		System.out.print("排序前的数组为：");
    		for(int i=0; i<arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}		
    		System.out.println();
    		bubbleSort(arr); //冒泡排序
    		System.out.print("排序后是数组为：");
    		for(int i=0; i<arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    		
    	}
    	public static void bubbleSort(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 temp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = temp;
    			}	
    			}			
    		}
    	}
    
    }

2、交换类排序：快速排序 ，时间复杂度O(nlog2n)，不稳定型排序。利用递归实现。

//主类
    package SortAlgorithm;
    
    public class SortAlgorithm {
    	public static void main(String args[]) {
    		int[] arr = {4,2,5,6,1,7};
    		System.out.print("排序前的数组为：");
    		for(int i=0; i<arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}		
    		System.out.println();
    //		new BubbleSort().bubbleSort(arr); //冒泡排序
    		new QuickSort().quickSort(arr,0,5);//快速排序
    		System.out.print("排序后是数组为：");
    		for(int i=0; i<arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    		
    	}
    
    }

//快速排序代码
    package SortAlgorithm;
    
    public class QuickSort {
    	
    	 public static void quickSort(int[] a, int l, int r) { 
    		 int temp;
    		 int i=l;
    		 int j=r;
    	     if(l < r) {
    	    	 temp = a[l];
    	    	 //下面这个循环完成了一趟排序，即将数组中小于temp的元素放在左边，
    	    	 //大于temp的元素放在右边
    	    	 while(i!=j) {
    	    		 while(j>i && a[j]>temp) {//从右向左扫描找到一个小于temp的元素
    	    			 --j;
    	    		 }
    	    		 if(i<j) {
    	    			 a[i] = a[j];
    	    			 ++i;
    	    		 }
    	    		 while(i<j && a[i]<temp) {//从左向右扫描找到一个大于temp的元素
    	    			 ++i;
    	    		 }
    	    		 if(i<j) {
    	    			 a[j] = a[i];
    	    			 --j;
    	    		 }
    	    	 }
    	    	 a[i] = temp;
    	    	 quickSort(a, l, i-1);
    	    	 quickSort(a, i+1, r);
    	     }    
    	    }  
    
    }

3、插入类排序：直接插入排序，时间复杂度为O(n2，n的2次方)，稳定型排序。

主类与2中主类相同，只是调用一下下面的插入排序类中插入排序方法。

package SortAlgorithm;
    
    public class InsertSort {
    	public void insertSort(int[] a,int n) {//a数组元素个数为n
    		int i,j,temp;
    		for(i=0; i<n; ++i) {
    			temp = a[i];
    			j = i-1;
    			//下面这个循环完成了从待排序之前的元素开始扫描，如果大于待排序元素，则后移一位
    			while(j>=0 && temp<a[j]) {
    				a[j+1] = a[j];
    				--j;						
    			}
    			a[j+1] = temp;
    		}
    		
    	}
    
    }

4、选择类排序：直接选择排序，时间复杂度为O(n2，n的2次方)，不稳定型排序。

主类与2中主类相同，只是调用一下下面的直接选择排序类中直接选择排序方法。

package SoreAlgorithm;
    
    public class SelectSort {
    	public void selectSort(int[] a,int n) {
    		int i,j,k,temp;
    		for(i=0; i<n; ++i) {
    			k = i;//k指向有序序列的最后一个元素
    			//下面这个是关键循环，它从无序序列中挑选出一个最小元素
    			for(j=i+1; j<n; ++j) {
    				if(a[k]>a[j]) {
    					k = j;
    				}				
    			}
    			temp = a[i];
    			a[i] = a[k];
    			a[k] = temp;
    		}
    	}
    
    }