这篇文章主要为大家详细介绍了快速排序和堆排序的多种语言的实现（JavaScript、Python、Go语言、Java、C++），感兴趣的小伙伴可以了解一下
快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
算法步骤
- 从数列中挑出一个元素，称为 “基准”（pivot）;
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
动图演示
JavaScript代码实现
function quickSort(arr,left,right){ var len = arr.length, partitionIndex, left = typeof left != 'number' ? 0 : left, right = typeof right != 'number' ? len - 1 : right; if(left pivot){ --high; } arr[low] = arr[high]; while(low python代码实现
def quickSort(arr,left=None,right=None): left = 0 if not isinstance(left,(int,float)) else left right = len(arr)-1 if not isinstance(right,(int,float)) else right if left
Go代码实现
func quickSort(arr []int) []int{ return _quickSort(arr,0,len(arr)-1) } func _quickSort(arr []int,left,right int) []int{ if left C++代码实现
Partition1(int A[],int low,int high){ int pivot = A[low]; while(low = pivot){ --high; } A[low] = A[high]; while(low Java代码实现
public class QuickSort implements IArraySort{ @Override public int[] sort(int[] sourceArray) throws Exception{ //对arr进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray,sourceArray.length); return quickSort(arr,0,arr.length - 1); } private int[] quickSort(int[] arr, int left, int right){ if(left 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 Ο(nlogn)。
算法步骤
1.将待排序序列构建成一个堆 H[0……n-1]，根据（升序降序需求）选择大顶堆或小顶堆；
2.把堆首（最大值）和堆尾互换；
3.把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4.重复步骤 2，直到堆的尺寸为 1。
动图演示
JavaScript代码实现
var len; //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量 function buildMaxHeap(arr){ //建立大顶堆 len = arr.length; for(var i = Math.floor(len/2);i>=0;i--){ heapify(arr,i); } } function heapify(arr,i){ //堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if(left arr[largest]){ largest = left; } if(right arr[largest]){ largest = right; } if(largest != i){ swap(arr,i,largest); heapify(arr,largest); } } function swap(arr,i,j){ var temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } function heapSort(arr){ buildMaxHeap(arr); for(var i = arr.length-1; i > 0; i--){ swap(arr,0,i); len--; heapify(arr,0); } return arr; } Python代码实现
def buildMaxHeap(arr): import math for i in range(math.floor(len(arr)/2),-1,-1): heapify(arr,i) def heapify(arr,i): left = 2*i+1 right = 2*i+2 largest = i if leftarr[largest]: largest = left if right arr[largest]: largest = right if largest != i: swap(arr,i,largest) heapify(arr,largest) def swap(arr,i,j): arr[i],arr[j] = arr[j],arr[i] def heapSort(arr): global arrLen aeeLen = len(arr) buildMasxHeap(arr) for i in range(len(arr)-1,0,-1): swap(arr,0,i) arrLen -= 1 heapify(arr,0) return arr
Go代码实现
func heapSort(arr []int) []int { arrLen := len(arr) buildMaxHeap(arr, arrLen) for i := arrLen - 1; i >= 0; i-- { swap(arr, 0, i) arrLen -= 1 heapify(arr, 0, arrLen) } return arr } func buildMaxHeap(arr []int, arrLen int) { for i := arrLen / 2; i >= 0; i-- { heapify(arr, i, arrLen) } } func heapify(arr []int, i, arrLen int) { left := 2*i + 1 right := 2*i + 2 largest := i if left arr[largest] { largest = left } if right arr[largest] { largest = right } if largest != i { swap(arr, i, largest) heapify(arr, largest, arrLen) } } func swap(arr []int, i, j int) { arr[i], arr[j] = arr[j], arr[i] } Java代码实现
public class HeapSort implements IArraySort{ @Override public int[] sort(int[] sourceArray) throws Exception{ //对arr进行拷贝，不改变参数内容 int[] arr = Array.copyOf(sourceArray,sourceArray.length); int len = arr.length; buildMaxHeap(arr,len); for(int i = len - 1; i > 0; i--){ swap(arr,0,i); len--; heapify(arr,0,len); } return arr; } private void buildMaxHeap(int[] arr,int i , int len){ int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if(left arr[largest]){ largest = left; } if(right arr[largest]){ largest = right; } if(largest != i){ swap(arr,i,largest); heapify(arr,length,len); } } private void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } 到此这篇关于Java实现快速排序和堆排序的示例代码的文章就介绍到这了,更多相关Java 排序内容请搜索0133技术站以前的文章或继续浏览下面的相关文章希望大家以后多多支持0133技术站！
以上就是Java实现快速排序和堆排序的示例代码的详细内容，更多请关注0133技术站其它相关文章！
