生活随笔
收集整理的這篇文章主要介紹了
算法-排序-k排序（算法导论第三版第八章思考题8-5）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
算法-排序-k排序
算法導論第三版第八章思考題8-5
時間復雜度Θ(nlg(n/k))。
利用最小堆完成，把元素分成k個堆，每個堆大小?n/k?。
利用堆作為子排序穩定，也可以采用其他排序作為子排序，子排序的算法時間復雜度保證在Θ(klgk)就行。
#include "k_sort_heap.h"
int left_k_sort(int parent
)
{return (parent
<< 1) + 1;
}
int right_k_sort(int parent
)
{return (parent
<< 1) + 2;
}
void heapify_k_sort(int *array
,int heap_size
,int parent_index
)
{int smallest
= parent_index
;int left
= left_k_sort(parent_index
);int right
= right_k_sort(parent_index
);if(left
< heap_size
&& array
[left
]< array
[smallest
]){smallest
= left
;}if(right
< heap_size
&& array
[right
] < array
[smallest
]){smallest
= right
;}if(smallest
!= parent_index
){int temp
= array
[parent_index
];array
[parent_index
] = array
[smallest
];array
[smallest
] = temp
;heapify_k_sort(array
,heap_size
,smallest
);}
}
void build_k_sort_heap(int *array
,int length
)
{for (int i
= length
/2 - 1; i
>=0; --i
) {heapify_k_sort(array
,length
,i
);}
}
int extra_minimum(int *array
,int & heap_size
)
{int minimum
= array
[0];array
[0] = array
[heap_size
-1];heap_size
--;heapify_k_sort(array
,heap_size
,0);return minimum
;
}
void k_sort(int *array
,int length
,int k
)
{int initial_heap_size
= length
/k
+ (length
% k
== 0 ? 0 : 1);int *heap
= new int [initial_heap_size
];int current_heap_size
= 0;for (int i
= 0; i
< k
; ++i
) {for (int j
= 0; j
< initial_heap_size
; ++j
){if(i
+ (j
* k
) < length
){heap
[j
] = array
[i
+ (j
* k
)];current_heap_size
++;}}build_k_sort_heap(heap
,current_heap_size
);int j
= 0;while (current_heap_size
>0){array
[i
+ (j
* k
)] = extra_minimum(heap
,current_heap_size
);j
++;}}delete[] heap
;
}
總結
以上是生活随笔為你收集整理的算法-排序-k排序（算法导论第三版第八章思考题8-5）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
