go語言堆排序怎么寫 go語言map排序
堆排序怎么寫
堆排序怎么寫如下：
從策劃到設(shè)計制作，每一步都追求做到細(xì)膩，制作可持續(xù)發(fā)展的企業(yè)網(wǎng)站。為客戶提供做網(wǎng)站、網(wǎng)站設(shè)計、網(wǎng)站策劃、網(wǎng)頁設(shè)計、域名申請、虛擬空間、網(wǎng)絡(luò)營銷、VI設(shè)計、 網(wǎng)站改版、漏洞修補等服務(wù)。為客戶提供更好的一站式互聯(lián)網(wǎng)解決方案,以客戶的口碑塑造優(yōu)易品牌,攜手廣大客戶,共同發(fā)展進(jìn)步。
（1）用大根堆排序的基本思想
①
先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區(qū)
②
再將關(guān)鍵字最大的記錄R[1]（即堆頂）和無序拆舉區(qū)的最后一個記錄R[n]交換，由此得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key
③由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R[1..n-1]調(diào)整為堆。然后再次將R[1..n-1]中關(guān)鍵字最大的記錄R[1]和該區(qū)間的最后一個記錄R[n-1]交換，由此得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調(diào)整為堆。
……
直到無序區(qū)只有一個逗御譽元素為止。
（2）大根堆排序算法的基本操作：
①建堆，建堆是不斷調(diào)整堆的過程，從len/2處開始調(diào)整，一直到第一個節(jié)點，此處len是堆中元素的個數(shù)。建堆的過程是線性的過程，從len/2到0處一直調(diào)用調(diào)整堆的過程，相當(dāng)于o(h1)+o(h2)…+o(hlen/2)
其中h表示節(jié)點的深度，len/2表示節(jié)點的個數(shù)，這是一個求和的過程，結(jié)果是線性的O(n)。
②調(diào)整堆：調(diào)整堆在構(gòu)建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節(jié)點i和它的孩子節(jié)點left(i),right(i)，選出三者最大(或者最小)者，如果最大（?。┲挡皇枪?jié)點i而是它的一個孩子節(jié)點，那邊交互節(jié)點i和該節(jié)點，然后再調(diào)用調(diào)整堆過程，這是一個遞歸的過程。調(diào)整堆的過程時山段間復(fù)雜度與堆的深度有關(guān)系，是lgn的操作，因為是沿著深度方向進(jìn)行調(diào)整的。
Go語言如何給字符串排序
因為char *strings[]不是指針而是指針數(shù)組，那么
temp = strings[top];
strings[top] = strings[seek];
strings[seek] = temp;
這種交換交換的就是主調(diào)函旅散洞數(shù)中的數(shù)組中的指拆枯針，把指向掘攜字符串的指針順序改變了，當(dāng)然按次序輸出就達(dá)到排序目的了……
堆排序是穩(wěn)定的排序算法
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是堆排序算法：
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并豎弊散同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
大頂堆：每個節(jié)點的值都大于或等于其子節(jié)點的值，在堆排序算法中用于升序排列； 小頂堆：每個節(jié)點的值都小于或等于其子節(jié)點的值，在堆排序算法中用于降序排列；
堆排序的平均時間復(fù)雜度為 Ο(nlogn)。
1. 算法步驟
創(chuàng)建一個堆 H[0……n-1]；
把堆首（最大值）和堆尾互換；
把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是卜陵把新的數(shù)組頂端余氏數(shù)據(jù)調(diào)整到相應(yīng)位置；
重復(fù)步驟 2，直到堆的尺寸為 1。
2. 動圖演示
代碼實現(xiàn) JavaScript 實例 var len ; ? ? // 因為聲明的多個函數(shù)都需要數(shù)據(jù)長度，所以把len設(shè)置成為全局變量
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 arrLen arr [ left ] arr [ largest ] {
? ? ? ? ? ? largest = left
? ? }
? ? if right arrLen arr [ 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 進(jìn)行拷貝，不改變參數(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 $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 )
{
$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é)點指標(biāo)和子節(jié)點指標(biāo)
int dad = start ;
int son = dad * 2 + 1 ;
while ( son 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
Go語言 排序與搜索切片
Go語言標(biāo)準(zhǔn)庫中提供了sort包對整型，浮點型，字符串型切片進(jìn)行排序，檢查一個切片是否排好序，使用二分法搜索函數(shù)在一個有序切片中搜索一個元素等功能。
關(guān)于sort包內(nèi)的函數(shù)說明與使用，請查看
在這里簡單講幾個sort包中常用的函數(shù)
在Go語言中，對字符串的排序都是按照字節(jié)排序，也就是說在對字符串排序時是區(qū)分大小寫的。
二分搜索算法
Go語言中提供了一個使用二分搜索算法的sort.Search(size,fn)方液段灶法：每次只需要比較㏒?n個元素，其中n為切片中元素的總數(shù)。
sort.Search(size,fn)函數(shù)接受兩個參數(shù)：所處理的切片的長度和一個將目標(biāo)元素與有序切片的元素相比較的函數(shù)，該函數(shù)是一個閉包，如果該有序切片是鬧扮升序排列，那么在判斷時使用 有序切片的元素 = 目燃旁標(biāo)元素。該函數(shù)返回一個int值，表示與目標(biāo)元素相同的切片元素的索引。
在切片中查找出某個與目標(biāo)字符串相同的元素索引
分享文章：go語言堆排序怎么寫 go語言map排序
文章地址：http://m.jiaotiyi.com/article/ddpiigd.html