建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
淺談堆排序
堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種**選擇排序，**它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序。
創(chuàng)新互聯(lián)是專業(yè)的翁牛特網(wǎng)站建設公司，翁牛特接單;提供網(wǎng)站設計、成都網(wǎng)站制作,網(wǎng)頁設計,網(wǎng)站設計,建網(wǎng)站,PHP網(wǎng)站建設等專業(yè)做網(wǎng)站服務;采用PHP框架,可快速的進行翁牛特網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!
堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
-
大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列；
-
小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；
堆排序的平均時間復雜度為 Ο(nlogn)。
1. 算法步驟
-
創(chuàng)建一個堆 H[0……n-1]；
-
把堆首（最大值）和堆尾互換；
-
把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應位置；
-
重復步驟 2，直到堆的尺寸為 1。
2. 動圖演示
代碼實現(xiàn)
JavaScript
實例
var len; // 因為聲明的多個函數(shù)都需要數(shù)據(jù)長度，所以把len設置成為全局變量
function buildMaxHeap(arr) { // 建立大頂堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆調(diào)整
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 進行拷貝，不改變參數(shù)內(nèi)容
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) {
// 建立父節(jié)點指標和子節(jié)點指標
int dad = start;
int son = dad * 2 + 1;
while (son if (son + 1 if (arr[dad] > arr[son]) //如果父節(jié)點大於子節(jié)點代表調(diào)整完畢，直接跳出函數(shù)
return;
else { // 否則交換父子內(nèi)容再繼續(xù)子節(jié)點和孫節(jié)點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
int i;
// 初始化，i從最後一個父節(jié)點開始調(diào)整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先將第一個元素和已排好元素前一位做交換，再重新調(diào)整，直到排序完畢
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) {
// 建立父節(jié)點指標和子節(jié)點指標
int dad = start;
int son = dad * 2 + 1;
while (son if (son + 1 if (arr[dad] > arr[son]) // 如果父節(jié)點大於子節(jié)點代表調(diào)整完畢，直接跳出函數(shù)
return;
else { // 否則交換父子內(nèi)容再繼續(xù)子節(jié)點和孫節(jié)點比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
// 初始化，i從最後一個父節(jié)點開始調(diào)整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先將第一個元素和已經(jīng)排好的元素前一位做交換，再從新調(diào)整(剛調(diào)整的元素之前的元素)，直到排序完畢
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;
}
本文名稱：淺談堆排序
本文鏈接：http://www.dlmjj.cn/article/dpoohgo.html
