Java综合整理堆排序 快速排序 归并排序
程序员文章站
2022-06-18 11:55:20
目录堆排序快速排序递归非递归归并排序递归非递归堆排序 时间复杂度:0(n*log(n)) 空间复杂度:0(1) 稳定性:不稳定private static void heapsort...
堆排序
- 时间复杂度:0(n*log(n))
- 空间复杂度:0(1)
- 稳定性:不稳定
private static void heapsort(int[] arr) { //建堆 crearheap(arr); for (int i = 0; i < arr.length-1; i++) { int heapsize=arr.length-i; swap(arr,heapsize-1,0); heapsize--; shiftdown(arr,heapsize,0); } system.out.println(arrays.tostring(arr)); } private static void crearheap(int[] arr) { // 从后往前遍历(右边非叶子节点开始), 依次进行向下调整 for (int i = (arr.length-1-1)/2; i >=0 ; i--) { shiftdown(arr,arr.length,i); } } //向下调整,形成大堆 private static void shiftdown(int[] arr, int size, int i) { int parent = i; int child = parent*2+1; while (child<size){ if (child +1< size && arr[child +1]> arr[child]){ child=child+1; } if (arr[child]>arr[parent]){ swap(arr,child,parent); }else { break; } parent=child; child=parent*2+1; } } //交换 private static void swap(int[] arr, int child, int parent) { int tmp =arr[child]; arr[child] =arr[parent]; arr[parent]=tmp; }
快速排序
- 时间复杂度:o(n^ logn) 最坏的时候o(n^2) 和基准值密切相关
- 空间复杂度:0(logn) 最坏的时候o(n)
- 稳定性:不稳定
递归
private static void quick(int[] arr) { quicksorthelper(arr,0,arr.length-1); system.out.println(arrays.tostring(arr)); } private static void quicksorthelper(int[] arr, int left, int right) { if (left>=right){ //区间只有一个元素,或者零个元素 return; } int index = partition(arr,left,right); quicksorthelper(arr,left,index-1); quicksorthelper(arr,index+1,right); } private static int partition(int[] arr, int left, int right) { int i=left; int j=right; int basevalue=arr[right]; while (i<j){ while (i<j && arr[i]<=basevalue){ i++; } while (i<j && arr[j]>=basevalue){ j--; } if (i<j){ swap(arr,i,j); } } swap(arr,i,right); return i; } private static void swap(int[] arr, int i, int j) { int tmp =arr[i]; arr[i]=arr[j]; arr[j]=tmp; }
非递归
public static void quicksortbyloop(int[] arr) { stack<integer> stack =new stack<>(); stack.push(0); stack.push(arr.length-1); while (!stack.isempty()){ int right = stack.pop(); int left = stack.pop(); if (left>=right){ continue; } int index = partition(arr,left,right); //右子树 stack.push(index+1); stack.push(right); //左子树 stack.push(left); stack.push(index-1); } system.out.println(arrays.tostring(arr)); } private static int partition(int[] arr, int left, int right) { int basevalue =arr[right]; int i =left; int j =right; while (i<j){ while (i<j && arr[i]<=basevalue){ i++; } while (i<j && arr[j]>=basevalue){ j--; } if (i<j){ swap(arr,i,j); } } swap(arr,i,right); return i; } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
归并排序
- 时间复杂度:o(nlogn)
- 空间复杂度:o(n) 如果是链表,可以为o(1)
- 稳定性:稳定
递归
public static void mergesort(int[] arr){ mergesorthelper(arr,0,arr.length); system.out.println(arrays.tostring(arr)); } private static void mergesorthelper(int[] arr, int left, int right) { if (right-left<=1){ return; } int mid = (right+left)/2; mergesorthelper(arr,left,mid); mergesorthelper(arr,mid,right); merge(arr,left,mid,right); } private static void merge(int[] arr, int left, int mid, int right) { int cur1 =left; int cur2 =mid; //两个数组合并后的结果 int[] output=new int[right-left]; int outputindex=0; while (cur1<mid && cur2<right){ if (arr[cur1]<=arr[cur2]) { output[outputindex++] = arr[cur1++]; }else { output[outputindex++] = arr[cur2++]; } } while (cur1<mid){ output[outputindex++] = arr[cur1++]; } while (cur2<right){ output[outputindex++] = arr[cur2++]; } for (int i = 0; i < right-left ; i++) { arr[left+i] = output[i]; } }
非递归
public static void mergesortbyloop(int[] arr){ // gap 当前每个组中的元素个数. for (int gap =1;gap<arr.length;gap*=2){ for (int i = 0; i <arr.length ; i+=2*gap) { //相当于把两个长度为 gap 的相邻组进行了合并 int left =i; int mid =i+gap; int right=i+2*gap; if (mid > arr.length){ mid =arr.length; } if (right>arr.length){ right=arr.length; } merge(arr,left,mid,right); } } system.out.println(arrays.tostring(arr)); }
到此这篇关于java综合整理堆排序 快速排序 归并排序的文章就介绍到这了,更多相关java 排序算法内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
下一篇: 比特币开发人员选择匿名的必要性
推荐阅读
-
Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)
-
快速排序 Vs. 归并排序 Vs. 堆排序——谁才是最强的排序算法
-
选择排序、冒泡排序、插入排序、归并排序、快速排序的Java实现以及优化
-
经典排序算法java实现 排序算法java选择排序快速排序归并排序
-
用Python代码实现插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序
-
Java 排序算法整合(冒泡,快速,希尔,拓扑,归并)
-
Java综合整理堆排序 快速排序 归并排序
-
稳定性分析与Java实现:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序
-
排序算法总结(冒泡、选择、插入、希尔、快速、归并、基数、堆排序)
-
直接插入排序 希尔排序 冒泡排序 快速排序 直接选择排序 堆排序 归并排序 基数排序的算法分析和具体实现