对数组中的数从小到大排序,使用多种方法排序(冒泡排序,选择排序,快速排序)

秒速五厘米 2024-04-17 23:16 36阅读 0赞

## 对数组中的数从小到大排序,使用多种方法排序(冒泡排序,选择排序,快速排序) ##

package com.zr.demo01;
    
    import java.util.Arrays;
    
    //对数组中的数从小到大排序,使用多种方法排序(冒泡排序,选择排序,快速排序)
    public class Eleventh {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] arr=new int[] {9,8,11,54,87,6,44,3};
    		
    		/*
    		//冒泡排序
    		System.out.println("冒泡排序:");
    		System.out.println("排序前:"+Arrays.toString(arr));//排序前:[9, 8, 11, 54, 87, 6, 44, 3]
    		bubbleSort(arr);
    		System.out.println("排序后:"+Arrays.toString(arr));//排序后:[3, 6, 8, 9, 11, 44, 54, 87]
    		*/
    		
    		/*
    		//选择排序
    		System.out.println("选择排序:");
    		System.out.println("排序前:"+Arrays.toString(arr));//排序前:[9, 8, 11, 54, 87, 6, 44, 3]
    		choiceSort(arr);
    		System.out.println("排序后:"+Arrays.toString(arr));//排序后:[3, 6, 8, 9, 11, 44, 54, 87]
    		*/
    		
    		//快速排序
    		System.out.println("快速排序:");
    		System.out.println("排序前:"+Arrays.toString(arr));//排序前:[9, 8, 11, 54, 87, 6, 44, 3]
    		quickSort(arr, 0, arr.length-1);
    		System.out.println("排序后:"+Arrays.toString(arr));//排序后:[3, 6, 8, 9, 11, 44, 54, 87]
    
    	}
    	
    	/**
    	 * 冒泡排序:相邻两个数比较
    	 * 9 8 11 54 87 6 44 3
    	 * 8 9 11 54 6 44 3 87  得到最大的数87,第1次循环,比较7次
    	 * 8 9 11 6 44 3 54 87 得到倒数第二大的数54,第2次循环,比较6次
    	 * 8 9 6 11 3 44 54 87 得到倒数第三大的数44,第3次循环,比较5次
    	 * 8 6 9 3 11 44 54 87 得到倒数第四大的数11,第4次循环,比较4次
    	 * 6 8 3 9 11 44 54 87 得到倒数第五大的数9,第5次循环,比较3次
    	 * 6 3 8 9 11 44 54 87 得到倒数第六大的数8,第6次循环,比较2次
    	 * 3 6 8 9 11 44 54 87 得到倒数第七大的数6,第7次循环,比较1次
    	 * 一共有8个数,循环7次就可以排序完
    	 * 这就是冒泡排序
    	 */
    	public static void bubbleSort(int[] arr) {
    		//循环(arr.length-1)次
    		for(int i=0;i<arr.length-1;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;
    				}
    			}
    		}
    	}
    	
    	/**
    	 * 选择排序:选取最大的数
    	 * 9 8 11 54 87 6 44 3
    	 * 3 8 11 54 87 6 44 9 第1次循环,获取最小的数3,与9更换位置
    	 * 3 6 11 54 87 8 44 9 第2次循环,获取倒数第二小的数6,与8更换位置
    	 * 3 6 8 54 87 11 44 9 第3次循环,获取倒数第三小的数8,与11更换位置
    	 * 3 6 8 9 87 11 44 54 第4次循环,获取倒数第四小的数9,与54更换位置
    	 * 3 6 8 9 11 87 44 54 第5次循环,获取倒数第五小的数11,与87更换位置
    	 * 3 6 8 9 11 44 87 54 第6次循环,获取倒数第六小的数44,与87更换位置
    	 * 3 6 8 9 11 44 54 87 第7次循环,获取倒数第七小的数54,与87更换位置
    	 * 一共有8个数,循环7次
    	 * 这就是选择排序
    	 */
    	public static void choiceSort(int[] arr) {
    		for (int i = 0; i < arr.length-1; i++) {
    			//最小的数的下标
    			int k=i;
    			for (int j = i; j < arr.length; j++) {
    				//如果arr[k]不是最小数,则改变k值
    				if (arr[k]>arr[j]) {
    					k=j;
    				}
    			}
    			//交换数
    			int temp=arr[k];
    			arr[k]=arr[i];
    			arr[i]=temp;
    		}
    	}
    	
    	/**
    	 * 快速排序
    	 * @param arr
    	 */
    	public static void quickSort(int[] arr,int start,int end) {
    		//如果开始下标>=结束下标,直接结束函数
    		if (start>=end) {
    			return;
    		}
    		//小下标
    		int low=start;
    		//大下标
    		int high=end;
    		//默认第一个数为关键字
    		int key=arr[low];
    		
    		while(low<high) {
    			
    			while(arr[high]>=key&&low<high) {//双保险
    				high--;
    			}
    			int temp1=arr[low];
    			arr[low]=arr[high];
    			arr[high]=temp1;
    			
    			while(arr[low]<=key&&low<high) {//双保险
    				low++;
    			}
    			int temp2=arr[low];
    			arr[low]=arr[high];
    			arr[high]=temp2;
    		}
    		//对小的部分快速排序
    		quickSort(arr, start, low-1);
    		//对大的部分快速排序
    		quickSort(arr, high+1, end);
    		
    	}
    
    }