两种选择排序代码实现(直接选择排序+堆排序)

快来打我* 2022-05-26 12:57 170阅读 0赞

**选择排序**

**1、直接选择排序**

**2、堆排序**

1、直接选择排序

package sort;
    
    //选择排序
    public class SelectSort {
    
    	public static void sortA(int[] arr,int n){
    		int tmp;//临时变量
    		int min;//记录最小值的下标
    		int compare=0;//比较次数
    		int change=0;//移动位置次数
    		for(int i=0;i<n-1;i++){
    			min=i;//默认当前i为最小
    			for(int j=i+1;j<n;j++){//记录最小的值的下标，然后放在第一个位置
    				compare++;//比较次数
    				if(arr[j]<arr[min]){
    					min=j;
    				}
    			}
    			//判断min的值是否改变，如果改变了，则进行交换位置
    			if(min!=i){//min=j
    				change++;
    				tmp=arr[i];
    				arr[i]=arr[min];
    				arr[min]=tmp;
    			}
    		}
    		System.out.println("比较次数："+compare);
    		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]+" ");
    		}
    	}
    }

2、堆排序

package sort; //1.初始化大根堆 //2.将最大的数放在最后一个位置n-i处，重复多次操作即可完成 public class MyHeapSort { //调整堆排序（仅是调整过程，建立在大顶堆已构建的基础上） public static void adjustHeap(int[] array,int i,int len){ int k=2*i;//左子节点 int temp;//临时变量 while(k<len){ temp=array[i];//临时变量存放父结点的值 //k 左子结点 //k+1 右子节点 //判断左右子节点谁大，记录谁 if(k+1<len && array[k]<array[k+1]){ k++;//记录右子结点 } //儿子结点 > 父亲结点 if(array[k]>temp){ array[i]=array[k];//父亲结点 记录最大值 i=k; } else break;//筛选结束【退出while循环】 k=2*i;//下一个左子结点 //将temp值放到最终的位置 array[i]=temp;//子结点，记录父亲节点的较小值【相当于array[i] 与 array[k] 的值进行了交换】 } } //堆排序 public static void heapSort(int[] array){ int len=array.length;//数组长度 //1.构造初始化堆 for(int i=len/2;i>=0;i--){ //从第一个非叶子结点从下至上，从右至左调整结构 adjustHeap(array,i,len);//调整堆 } //2.重新进行堆排序[使得堆有序] int temp; for(int i=len-1;i>0;i--){//i=0处有放元素 //先调整元素 swap(array,0,i);//将堆顶元素与末尾元素进行交换【使得末尾元素最大，因为交换前，堆顶元素最大】 //重新调整堆 adjustHeap(array,0,i); } } /** * 交换元素 */ public static void swap(int []arr,int a ,int b){ int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } public static void main(String[] args) { // int array[] = { 21, 50, 20, 40, 70, 19, 80, 30, 60,99 }; int array[] = {11,7,18,3,5,4,10,9,88,77}; System.out.println("排序之前："); for (int element : array) { System.out.print(element + " "); } heapSort(array); System.out.println("\n排序之后："); for (int element : array) { System.out.print(element + " "); } } }