八、堆排序
堆排序是比快速排序更加复杂的一种排序算法。堆排序使用到了堆这样一种数据结构。首先我们需要搞清楚什么是堆结构。堆是一种类似完全二叉树，同时又满足如下条件的数据结构：所有子节点的值总是小于(大于)父节点。所有子节点的值都小于父节点的堆叫大顶堆，所有子节点都大于父节点的堆叫小顶堆。
二叉树你应该比较熟悉，下图就是一个小顶堆的示例：
此二叉树中任何一个子节点的值都是大于父节点。如何将数列构造成这样一个堆结构呢，其实十分简单，将数列按照从上到下，从左到右的原则来构造完全二叉树即可。例如如下数列[1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34]如果将其构造成堆如下图所示：
正常情况下，这个由数组映射成的二叉树并不符合我们堆的要求，否则也就不需要我们用算法来排序了。要让这个二叉树符合要求，我们需要进行整理，即从末节点开始进行调整，例如先从12，98，34中找到最小的，放在现在12所在的位置，然后从64，46，34中找到最小的元素进行上浮，接着再一层层上浮上去，直到堆顶元素为所有元素中的最小元素。整理完成后，我们只需要将堆顶元素和最后一个元素进行交换，之后除掉最后一个元素再进行堆整理，整理完成后再将顶元素(此时为第2小)与倒数第二个元素交换，依次进行下去，即可完成数列的排序。
用文字描述堆排序步骤如下：
1.先将数列整理成符合要求的堆。
2.将首末元素交换。
3.除掉最后一个元素在进行堆的整理。
4.重复进行2和3，直到数列排序完成。
JavaScript实现的堆排序算法：
var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//堆排序
//堆调整 大顶
function store(array,index,end){
let top = array[index];
let left;
let right;
if (index*2+1<=end) {
left = index*2+1;
}else{
//没有左子树 说明已经是叶子节点
//无需调整直接return
return;
}
if (index*2+2<=end) {
right = index*2+2;
}else{
//没有右子树 调整左子树即可
if (array[left]>top) {
array[index] = array[left];
array[left] = top;
top = array[index];
}
return;
}
//找出堆单元中的最大值
if (array[left]>top) {
array[index] = array[left];
array[left] = top;
top = array[index];
}
if (array[right]>top) {
array[index] = array[right];
array[right] = top;
top = array[index];
}
}
function sort(array,end){
//先将堆进行调整 倒叙调整
let i = end;
while(i>=0){
store(array,i,end)
i--;
}
//根节点一定是最大的 放最后 再进行堆整理
let temp = array[end];
array[end] = array[0];
array[0] = temp;
end--;
if (end>0) {
sort(array,end);
}else{
return;
}
}
sort(array, array.length-1);
console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]
C语言实现的堆排序算法：
#include <stdio.h>
void store(int array[],int index,int end){
int top = array[index];
int left;
int right;
if (index*2+1<=end) {
left = index*2+1;
}else{
//没有左子树 说明已经是叶子节点
//无需调整直接return
return;
}
if (index*2+2<=end) {
right = index*2+2;
}else{
//没有右子树 调整左子树即可
if (array[left]>top) {
array[index] = array[left];
array[left] = top;
top = array[index];
}
return;
}
//找出堆单元中的最大值
if (array[left]>top) {
array[index] = array[left];
array[left] = top;
top = array[index];
}
if (array[right]>top) {
array[index] = array[right];
array[right] = top;
top = array[index];
}
}
void mySort(int array[],int end){
//先将堆进行调整 倒叙调整
int i = end;
while(i>=0){
store(array,i,end);
i--;
}
//根节点一定是最大的 放最后 再进行堆整理
int temp = array[end];
array[end] = array[0];
array[0] = temp;
end--;
if (end>0) {
mySort(array,end);
}else{
return;
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
mySort(a,10);
for(int i = 0;i<11;i++){
printf("%d\n",a[i]);
}
return 0;
}
需要注意，大顶堆排序完成后为升序，小顶堆排序完成后为降序。
九、归并排序
归并排序的核心并不是交换元素的顺序，而是将数列分成多个有序小数列，将相邻的小数列进行归并。文字描述归并排序步骤如下：
1.把长度为n的数列分成长度为1的n个数列。
2.相邻数列进行排序归并。
3.重复操作2，直到所有数列归并成1个整体。
JavaScript实现的归并排序算法：
var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];
//归并排序
function mergeArray(arrL,arrR){
var tempArray = new Array();
let i = 0;
let j = 0;
while(i<arrL.length && j<arrR.length){
if (arrL[i]<arrR[j]) {
tempArray.push(arrL[i]);
i++;
}else{
tempArray.push(arrR[j]);
j++;
}
}
while(i<arrL.length){
tempArray.push(arrL[i]);
i++;
}
while(j<arrR.length){
tempArray.push(arrR[j]);
j++
}
return tempArray;
}
function sort(array){
if (array.length>1) {
let arrL = array.slice(0,Math.floor(array.length/2));
let arrR = array.slice(Math.floor(array.length/2),array.length);
if (arrL.length>1) {
arrL = sort(arrL);
}
if (arrR.length>1) {
arrR = sort(arrR);
}
return mergeArray(arrL,arrR);
}
return array;
}
console.log(sort(array)); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]
C语言实现的归并排序算法：
#include <stdio.h>
void merge(int array[],int temp[],int start,int end,int middle){
int i=start,j=middle+1,k=start;
while(i<middle+1 && j<end+1){
if(array[i]<array[j]){
temp[k++] = array[i++];
}else {
temp[k++] = array[j++];
}
}
while(i<middle+1){
temp[k++] = array[i++];
}
while(j<end+1){
temp[k++] = array[j++];
}
for(i=start;i<=end;i++){
array[i] = temp[i];
// printf("%d,",temp[i]);
}
}
void sort(int array[],int temp[],int start,int end){
int middle;
if(start<end){
middle = (start+end)/2;
sort(array, temp, start, middle);
sort(array, temp, middle+1, end);
merge(array, temp, start, end, middle);
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};
int b[11] = {0};
sort(a,b,0,10);
for(int i = 0;i<11;i++){
printf("%d\n",a[i]);
}
return 0;
}
