两种交换排序代码实现(冒泡排序+快速排序【可多种方式优化】)

系统管理员 2022-05-26 12:57 183阅读 0赞

**交换排序**

**1、冒泡排序**

**2、快速排序【可多种方式优化】**

交换排序

1、冒泡排序

afsaf

package sort;
    
    public class BubbleSort {
    	
    	//普通冒泡排序
    	public static void sortA(int[] arr,int n){
    		int tmp;//临时变量
    		int compare=0;//比较趟数
    		int count=0;//比较次数
    		int change=0;//交换位置次数
    		for(int i=0;i<n-1;i++){
    			compare++;
    			for(int j=n-1;j>i;j--){//冒泡排序，从后往前
    				count++;
    				if(arr[j-1]>arr[j]){
    					change++;
    					tmp=arr[j-1];
    					arr[j-1]=arr[j];
    					arr[j]=tmp;
    				}
    			}
    		}
    		System.out.println("比较趟数"+compare);
    		System.out.println("比较次数"+count);
    		System.out.println("交换位置次数"+change);
    	}
    
    	
    	//改进后的冒泡排序
    	public static void sortMore(int[] arr,int n){
    		int tmp;//临时变量
    		int compare=0;//比较趟数
    		int count=0;//比较次数
    		int change=0;//交换位置次数
    		boolean flag=true;
    		for(int i=0;i<n-1;i++){
    			compare++;
    			
    			flag=false;
    			for(int j=n-1;j>i;j--){//冒泡排序，从后往前
    				count++;
    				
    				if(arr[j-1]>arr[j]){
    					change++;
    					tmp=arr[j-1];
    					arr[j-1]=arr[j];
    					arr[j]=tmp;
    					flag=true;//某一趟中存在元素的交换，说明未排好序
    				}
    			}
    			//判断是否还存在比较的情况
    			if(!flag){//某一趟中不存在元素的交换，说明已经排好序了
    				break;//结束for循环
    			}
    //			if(flag==false){
    //				break;//结束for循环
    //			}
    //			System.out.println("比较ing..");
    		}
    		System.out.println("比较趟数"+compare);
    		System.out.println("比较次数"+count);
    		System.out.println("交换位置次数"+change);
    	}
    	
    	public static void main(String[] args) {
    		//普通冒泡排序
    		int  arr[]={4,5,6,3,1,9,0,8,7,2};
    		sortA(arr,arr.length);
    		System.out.println("排序后：");
    		for(int i=0;i<arr.length;i++){
    			System.out.print(arr[i]+" ");
    		}
    		System.out.println("\n------------------------------------------");
    		
    		//改进后的冒泡排序
    		int  arr2[]={4,5,6,3,1,9,0,8,7,2};
    		sortMore(arr2,arr2.length);
    		System.out.println("排序后：");
    		for(int i=0;i<arr2.length;i++){
    			System.out.print(arr2[i]+" ");
    		}
    		
    	}
    }

2、快速排序【优化】

package sort;
    
    //快速排序
    public class QuickSort {
    
    	//交换两个元素的值
    	public static void swap(int[] arr,int low,int high){
    		int temp=arr[low];
    		arr[low]=arr[high];
    		arr[high]=temp;
    	}
    	
    	//确立基本点+排序
    	public static int partition(int[] arr,int low,int high){
    		int point=low;//基本点的值
    		
    		//目标   基本点  ，左边的值，都比arr[point]小； 右边的值，都比arr[point]大
    		while(low<high){
    			//右边扫描，小的值，交换操作
    			while(low<high && arr[point]<arr[high]){
    				high--;//从右边开始扫描，过滤比arr[point]大的值，知道遇到比arr[point]小的值
    			}
    			swap(arr,point,high);//交换元素位置
    			point=high;//大值位置【point记录--交换后的位置】
    			
    			//左边扫描，打的值，交换操作
    			while(low<high && arr[point]>arr[low]){
    				low++;
    			}
    			swap(arr,low,point);//交换元素位置
    			point=low;//小值位置【point记录--交换后的位置】
    		}
    		return point;//【point记录--交换后的位置】
    	}
    	
    	
    	public static void sort(int[] arr,int low,int high){
    		if(low<high){//循环终止条件
    			
    			//确立基本点，进行排序【小于基本点的，放左边，大于基本点的，放右边】
    			int point=partition(arr,low,high);
    			
    			sort(arr,low,point-1);//左边遍历
    //			sort(arr,low,point);//左边遍历
    			sort(arr,point+1,high);//右边遍历
    		}
    	}
    	
    	
    	
    	public static void main(String[] args) {
    		int i;
    		int a[] = { 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 };
    
    		sort(a, 0,a.length-1);
    
    		System.out.println("快速排序--排序后的结果是:");
    		for (i = 0; i < 10; i++) {
    			System.out.print(a[i] + " ");
    		}
    		System.out.println("\n");
    
    	}
    
    }