选择排序
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 + " "); } } }
