堆排序算法的实习（C++）

View Code

 1 //HeapSort.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 
 7 using namespace std;
 8 
 9 //此函数为大顶堆调整函数
10 void HeapAdjust(int* arr,int start, int end)
11 {
12     int temp;//用作交换的存储单元，此算法的空间复杂度为此。
13     int j=0;//关键字较大的节点位置
14     temp = arr[start];
15     for(j = start*2 + 1; j <= end; j=(j*2+1))
16     {
17         if(j < end && arr[j] < arr[j+1])
18         {
19             ++j;
20         }
21         if(temp >= arr[j]) break;
22         arr[start] = arr[j];
23         start = j;
24     }
25     arr[start] = temp;
26 }
27 //堆排序函数
28 void HeapSort(int *a,int len)
29 {
30     for(int i =len/2-1; i >= 0; --i )
31     {
32         HeapAdjust(a,i,len-1);
33     }
34     for(int j=len-1; j >= 0; --j)
35     {
36         int tmp = a[0];
37         a[0] = a[j];
38         a[j] = tmp;
39         HeapAdjust(a,0,j-1);
40     }
41 }
42 int _tmain(int argc, _TCHAR* argv[])
43 {
44     int a[20]={-1,23,5456,21,784,12,46,89,21213,687,32,-12,8,0,123,-34,2332,3333,5674,1111};
45     HeapSort(a,20);
46     for(int i=0; i < 20;++i)
47     {
48         cout<<a[i]<<"  ";
49     }
50     cout<<endl;
51     return 0;
52 }
53 
54

HeapSort.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

//此函数为大顶堆调整函数
void HeapAdjust(int* arr,int start, int end)
{
    int temp;//用作交换的存储单元，此算法的空间复杂度为此。
    int j=0;//关键字较大的节点位置
    temp = arr[start];
    for(j = start*2 + 1; j <= end; j=(j*2+1))
    {
        if(j < end && arr[j] < arr[j+1])
        {
            ++j;
        }
        if(temp >= arr[j]) break;
        arr[start] = arr[j];
        start = j;
    }
    arr[start] = temp;
}
//堆排序函数
void HeapSort(int *a,int len)
{
    for(int i =len/2-1; i >= 0; --i )
    {
        HeapAdjust(a,i,len-1);
    }
    for(int j=len-1; j >= 0; --j)
    {
        int tmp = a[0];
        a[0] = a[j];
        a[j] = tmp;
        HeapAdjust(a,0,j-1);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    int a[20]={-1,23,5456,21,784,12,46,89,21213,687,32,-12,8,0,123,-34,2332,3333,5674,1111};
    HeapSort(a,20);
    for(int i=0; i < 20;++i)
    {
        cout<<a[i]<<"  ";
    }
    cout<<endl;
    return 0;
}