浅谈堆排序

堆排序是利用这种数据结构而设计的一种排序算法,堆排序是一种**选择排序,**它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

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

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

1. 算法步骤

  1. 创建一个堆 H[0……n-1];
  2. 把堆首(最大值)和堆尾互换;
  3. 把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
  4. 重复步骤 2,直到堆的尺寸为 1。

2. 动图演示

堆排序是什么?堆排序是什么?堆排序是什么?堆排序是什么?

代码实现

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 left  arr[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
   arrLen = len(arr)
   buildMaxHeap(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 = Arrays.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 len) {
       for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
           heapify(arr, i, len);
       }
   }

   private void heapify(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, largest, len);
       }
   }

   private void swap(int[] arr, int i, int j) {
       int temp = arr[i];
       arr[i] = arr[j];
       arr[j] = temp;
   }

}

PHP

实例

function buildMaxHeap(&$arr)
{
   global $len;
   for ($i = floor($len/2); $i >= 0; $i--) {
       heapify($arr$i);
   }
}

function heapify(&$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);
   }
}

function swap(&$arr$i$j)
{
   $temp = $arr[$i];
   $arr[$i] = $arr[$j];
   $arr[$j] = $temp;
}

function heapSort($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;
}

C

实例

#include
#include

void swap(int *a, int *b) {
   int temp = *b;
   *b = *a;
   *a = temp;
}

void max_heapify(int arr[], int start, int end) {
   // 建立父節點指標和子節點指標
   int dad = start;
   int son = dad * 2 + 1;
   while (son if (son + 1 if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢,直接跳出函數
           return;
       else { // 否則交換父子內容再繼續子節點和孫節點比較
           swap(&arr[dad], &arr[son]);
           dad = son;
           son = dad * 2 + 1;
       }
   }
}

void heap_sort(int arr[], int len) {
   int i;
   // 初始化,i從最後一個父節點開始調整
   for (i = len / 2 - 1; i >= 0; i--)
       max_heapify(arr, i, len - 1);
   // 先將第一個元素和已排好元素前一位做交換,再重新調整,直到排序完畢
   for (i = len - 1; i > 0; i--) {
       swap(&arr[0], &arr[i]);
       max_heapify(arr, 0, i - 1);
   }
}

int main() {
   int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
   int len = (int) sizeof(arr) / sizeof(*arr);
   heap_sort(arr, len);
   int i;
   for (i = 0; i printf("%d ", arr[i]);
   printf("\n");
   return 0;
}

C++

实例
#include
#include
using namespace std;

void max_heapify(int arr[], int start, int end) {
   // 建立父節點指標和子節點指標
   int dad = start;
   int son = dad * 2 + 1;
   while (son if (son + 1 if (arr[dad] > arr[son]) // 如果父節點大於子節點代表調整完畢,直接跳出函數
           return;
       else { // 否則交換父子內容再繼續子節點和孫節點比較
           swap(arr[dad], arr[son]);
           dad = son;
           son = dad * 2 + 1;
       }
   }
}

void heap_sort(int arr[], int len) {
   // 初始化,i從最後一個父節點開始調整
   for (int i = len / 2 - 1; i >= 0; i--)
       max_heapify(arr, i, len - 1);
   // 先將第一個元素和已经排好的元素前一位做交換,再從新調整(刚调整的元素之前的元素),直到排序完畢
   for (int i = len - 1; i > 0; i--) {
       swap(arr[0], arr[i]);
       max_heapify(arr, 0, i - 1);
   }
}

int main() {
   int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
   int len = (int) sizeof(arr) / sizeof(*arr);
   heap_sort(arr, len);
   for (int i = 0; i ' ';
   cout return 0;
}

以上就是良许教程网为各位朋友分享的Linux系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

img
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

电子邮件地址不会被公开。 必填项已用*标注

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部