Skip to content

Latest commit

 

History

History
257 lines (203 loc) · 5.38 KB

7.heapSort.md

File metadata and controls

257 lines (203 loc) · 5.38 KB

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

  1. 创建一个堆 H[0……n-1]；

  2. 把堆首（最大值）和堆尾互换；

  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

  4. 重复步骤 2，直到堆的尺寸为 1。

2. 动图演示

动图演示

3. JavaScript 代码实现

varlen;// 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量functionbuildMaxHeap(arr){// 建立大顶堆len=arr.length;for(vari=Math.floor(len/2);i>=0;i--){heapify(arr,i);}}functionheapify(arr,i){// 堆调整varleft=2*i+1,right=2*i+2,largest=i;if(left<len&&arr[left]>arr[largest]){largest=left;}if(right<len&&arr[right]>arr[largest]){largest=right;}if(largest!=i){swap(arr,i,largest);heapify(arr,largest);}}functionswap(arr,i,j){vartemp=arr[i];arr[i]=arr[j];arr[j]=temp;}functionheapSort(arr){buildMaxHeap(arr);for(vari=arr.length-1;i>0;i--){swap(arr,0,i);len--;heapify(arr,0);}returnarr;}

4. Python 代码实现

defbuildMaxHeap(arr): importmathforiinrange(math.floor(len(arr)/2),-1,-1): heapify(arr,i) defheapify(arr, i): left=2*i+1right=2*i+2largest=iifleft<arrLenandarr[left] >arr[largest]: largest=leftifright<arrLenandarr[right] >arr[largest]: largest=rightiflargest!=i: swap(arr, i, largest) heapify(arr, largest) defswap(arr, i, j): arr[i], arr[j] =arr[j], arr[i] defheapSort(arr): globalarrLenarrLen=len(arr) buildMaxHeap(arr) foriinrange(len(arr)-1,0,-1): swap(arr,0,i) arrLen-=1heapify(arr, 0)    returnarr

5. Go 代码实现

funcheapSort(arr []int) []int { arrLen:=len(arr) buildMaxHeap(arr, arrLen) fori:=arrLen-1; i>=0; i-- { swap(arr, 0, i) arrLen-=1heapify(arr, 0, arrLen) } returnarr } funcbuildMaxHeap(arr []int, arrLenint) { fori:=arrLen/2; i>=0; i-- { heapify(arr, i, arrLen) } } funcheapify(arr []int, i, arrLenint) { left:=2*i+1right:=2*i+2largest:=iifleft<arrLen&&arr[left] >arr[largest] { largest=left } ifright<arrLen&&arr[right] >arr[largest] { largest=right } iflargest!=i { swap(arr, i, largest) heapify(arr, largest, arrLen) } } funcswap(arr []int, i, jint) { arr[i], arr[j] =arr[j], arr[i] }

6. Java 代码实现

publicclassHeapSortimplementsIArraySort { @Overridepublicint[] sort(int[] sourceArray) throwsException { // 对 arr 进行拷贝，不改变参数内容int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); intlen = arr.length; buildMaxHeap(arr, len); for (inti = len - 1; i > 0; i--) { swap(arr, 0, i); len--; heapify(arr, 0, len); } returnarr; } privatevoidbuildMaxHeap(int[] arr, intlen) { for (inti = (int) Math.floor(len / 2); i >= 0; i--) { heapify(arr, i, len); } } privatevoidheapify(int[] arr, inti, intlen) { intleft = 2 * i + 1; intright = 2 * i + 2; intlargest = i; if (left < len && arr[left] > arr[largest]) { largest = left; } if (right < len && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); heapify(arr, largest, len); } } privatevoidswap(int[] arr, inti, intj) { inttemp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

7. PHP 代码实现

functionbuildMaxHeap(&$arr) { global$len; for ($i = floor($len/2); $i >= 0; $i--) { heapify($arr, $i); } } functionheapify(&$arr, $i) { global$len; $left = 2 * $i + 1; $right = 2 * $i + 2; $largest = $i; if ($left < $len && $arr[$left] > $arr[$largest]) { $largest = $left; } if ($right < $len && $arr[$right] > $arr[$largest]) { $largest = $right; } if ($largest != $i) { swap($arr, $i, $largest); heapify($arr, $largest); } } functionswap(&$arr, $i, $j) { $temp = $arr[$i]; $arr[$i] = $arr[$j]; $arr[$j] = $temp; } functionheapSort($arr) { global$len; $len = count($arr); buildMaxHeap($arr); for ($i = count($arr) - 1; $i > 0; $i--) { swap($arr, 0, $i); $len--; heapify($arr, 0); } return$arr; }
close