冒泡、插入、归并、堆排序、快速排序的Java达成代码
发布时间:2021-11-19 14:47:56 所属栏目:教程 来源:互联网
导读:冒泡、插入、归并、堆排序、快速排序的Java实现代码,详细过程就不表了,看代码吧 import java.util.Arrays; public class Sort { static int swapTimes=0; public static void main(String[] args) { int[] numbers = { 7, 6, 5, 3, 1, 8, 9, 7, 1, 2 ,5};
冒泡、插入、归并、堆排序、快速排序的Java实现代码,详细过程就不表了,看代码吧 import java.util.Arrays; public class Sort { static int swapTimes=0; public static void main(String[] args) { int[] numbers = { 7, 6, 5, 3, 1, 8, 9, 7, 1, 2 ,5}; //*** BubbleSort Test *** //bubbleSort(numbers); //*** InsertSort Test *** //insertSort(numbers); //*** MergeSort Test *** //mergeSort(numbers); //*** HeapSort Test *** //heapSort(numbers); //*** QuickSort Test *** quickSort(numbers); System.out.println("result:"+Arrays.toString(numbers)); } /* * 插入排序 */ public static void insertSort(int[] numbers) { System.out.println("InsertSort:"+Arrays.toString(numbers)); if (numbers == null) { System.out.println("Invalid input!"); return; } for (int i = 1; i < numbers.length; i++) { int temp=numbers[i]; int j=i-1; for (; j >= 0&&numbers[j]>temp; j--) { //这个数大于比较数,就把这个数右移 numbers[j + 1] = numbers[j]; System.out.println(Arrays.toString(numbers)+"---temp="+temp); } numbers[j+1]=temp; //把比较数赋值到正确位置 System.out.println(Arrays.toString(numbers)); } } /* * 冒泡排序 */ public static void bubbleSort(int[] numbers) { System.out.println("BubbleSort:"); if (numbers == null) { System.out.println("Invalid input!"); return; } for (int i = numbers.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (numbers[j] > numbers[j + 1]) { swap(numbers, j, j + 1); } } } System.out.println("result:"); } /* * 归并排序 */ public static void mergeSort(int[] numbers){ if(numbers==null){ System.out.println("Invalid input!"); return; } mergeSort(numbers,0,numbers.length-1); } private static void mergeSort(int[] numbers, int start, int end) { if(start>=end){ return; } int mid=(start+end)>>1; mergeSort(numbers, start, mid); mergeSort(numbers, mid+1, end); merge(numbers,start,mid,end); System.out.println(Arrays.toString(numbers)+"---mid="+mid); } /* * 合并两个有序数组 */ private static void merge(int[] numbers, int start, int mid, int end) { int leftLength=mid-start+1; int rightLength=end-mid; int[] leftNumbers=new int[leftLength]; int[] rightNumbers=new int[rightLength]; for (int i = 0; i < leftLength; i++) {//将左边的元素赋给left数组 leftNumbers[i]=numbers[start+i]; } for (int j = 0; j < rightLength; j++) {//同理 rightNumbers[j]=numbers[mid+j+1]; } int pLeft=0; int pRight=0; for(int index=start;index<=end;index++){//开始merge左右数组 if(pLeft==leftLength){ //当left数组合并完了,就直接赋值right数组 numbers[index]=rightNumbers[pRight++]; }else if(pRight==rightLength){ numbers[index]=leftNumbers[pLeft++]; }else{ //左右数组都没赋值完,就要比较大小 if(leftNumbers[pLeft]<=rightNumbers[pRight]){ numbers[index]=leftNumbers[pLeft++]; }else{ numbers[index]=rightNumbers[pRight++]; } } } } /* * 堆排序 */ public static void heapSort(int[] numbers){ if(numbers==null){ System.out.println("Invalid input!"); return; } int[] heap=buildHeap(numbers); //构造小顶堆 System.out.println("build Heap:"+Arrays.toString(heap)); int index=0; while(!isHeapEmpty(heap)){ //注意,这里不能在前面的index++,因为会先算左括号内的++,造成传入的index+1 numbers[index]=popHeapTop(heap,index++); } } //将堆顶元素pop出来 private static int popHeapTop(int[] heap,int index) { int temp=heap[0]; int end=heap.length-1-index; heap[0]=heap[end]; //将最后一个数移至堆顶 heap[end]=Integer.MAX_VALUE; adjustHeap(heap, 0); //调整堆 System.out.println("current Heap:"+Arrays.toString(heap)); return temp; } private static boolean isHeapEmpty(int[] heap) { if(heap[0]==Integer.MAX_VALUE){ return true; } return false; } /* * 构造小顶堆 */ private static int[] buildHeap(int[] numbers) { int[] heap=new int[numbers.length]; for(int i=0;i<heap.length;i++){ heap[i]=numbers[i]; } for(int j=(heap.length>>1)-1;j>=0;j--){ //从有孩子的结点开始,从底向上维护堆 adjustHeap(heap,j); } return heap; } /* * 维护堆 */ private static void adjustHeap(int[] heap, int j) { int left=j<<1; int right=(j<<1)+1; int largest=j; if(left<heap.length //该左孩子下标必须在数组内 &&heap[left]!=Integer.MAX_VALUE //该元素必须未被覆盖 &&heap[j]<heap[left]){ largest=left; } if(right<heap.length &&heap[right]!=Integer.MAX_VALUE &&heap[largest]<heap[right]){ largest=right; } if(largest!=j){ swap(heap, j, largest); adjustHeap(heap, largest); //继续往下调整 } } /* * 快速排序 */ public static void quickSort(int[] numbers){ if(numbers==null){ System.out.println("Invalid input!"); return; } System.out.println("QuickSort:"); quickSort(numbers,0,numbers.length-1); } private static void quickSort(int[] numbers, int start, int end) { if(start<end){ int mid=patition(numbers,start,end); quickSort(numbers, start, mid-1); quickSort(numbers, mid+1, end); } } /* * 选一个数,将小于它的数放在左边,大于它的放在右边 */ private static int patition(int[] numbers, int start, int end) { int small=start-1; int index=start; int temp=numbers[end]; //选择数组最后一个元素作为比较数 while(index<=end){ if(numbers[index]<temp){ small++; if(index!=small){ swap(numbers, small, index); } } index++; } swap(numbers, small+1, end); return small+1; } /* * 交换数组的两个元素 */ private static void swap(int[] numbers, int a, int b) { int temp = numbers[a]; numbers[a] = numbers[b]; numbers[b] = temp; System.out.println("current numbers:" + //记录交换次数 ""+Arrays.toString(numbers)+"----swap times:"+(++swapTimes)); } } (编辑:济南站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |