{
for (int i = size/2; i >= 0; --i)
{
HeapAdjust(arr,i,size);
}
}
/*堆排序*/
void HeapSort(int *arr, int size)
{
BulidHeap(arr,size);
for (int i = size - 1; i > 0; --i)
{
swap(&arr[0], &arr[i]);
HeapAdjust(arr,0,i);
}
}
int main(int argc, char const *argv[])
{
int size = 10;
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
HeapSort(arr, size);
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
#include
void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
/*堆调整*/
void HeapAdjust(int *arr,int i,int size){
int lchild = 2*i+1; //节点i的左子节点
int rchild = 2*(i+1); //节点i的右子节点
int max = i;
if (i <= size/2) //只对非叶节点进行调整
{
if (lchild < size && arr[lchild] > arr[max])
{
max = lchild;
}
if (rchild < size && arr[rchild] > arr[max])
{
max = rchild;
}
if (max != i)
{
swap(&arr[i],&arr[max]);
HeapAdjust(arr,max,size);//对调整过的max节点重新进行堆调整
}
}
}
/*建立无序大顶堆*/
void BulidHeap(int *arr,int size)
{
for (int i = size/2; i >= 0; --i)
{
HeapAdjust(arr,i,size);
}
}
/*堆排序*/
void HeapSort(int *arr, int size)
{
BulidHeap(arr,size);
for (int i = size - 1; i > 0; --i)
{
swap(&arr[0], &arr[i]);
HeapAdjust(arr,0,i);
}
}
int main(int argc, char const *argv[])
{
int size = 10;
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
HeapSort(arr, size);
for (int i = 0; i < size; ++i)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
归并排序：
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列的排序算法。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。它将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法步骤：
归并操作的工作原理如下：第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾。
例如：
如 设有数列{6，202，100，301，38，8，1}
初始状态：[6] [202] [100] [301] [38] [8] [1] 比较次数
i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]3
i=2[ 6 100 202 301 ] [ 1 8 38 ]4
i=3 [ 1 6 8 38 100 202 301 ]4
总计： 11次
时间复杂度：
将参加排序的初始序列分成长度为1的子序列进行第一趟排序，得到 n / 2 个长度为 2 的各自有序的子序列（若n为奇数，还会存在一个最后元素的子序列），再调用排序函数进行第二趟排序，得到 n / 4 个长度为 4 的各自有序的子序列， 第 i 趟排序就是两两归并长度为 2^(i-1) 的子序列得到 n / (2^i) 长度为 2^i 的子序列，直到最后只剩一个长度为n的子序列。由此看出，一共需要 log2n 趟排序，每一趟排序的时间复杂度是 O(n), 由此可知 该算法的总的时间复杂度是是 O(n log2n)。
空间复杂度：
归并排序算法需要和原数据规模一样大的辅助空间 ，因此其空间复杂度是 O(n)。
算法稳定性：
归并（Merge）排序法是一个稳定的排序算法。
[cpp]
#include
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int tmp[10];
void Merge(int begin,int middle,int end)
{
int i = begin;
int j = middle + 1;
int k = begin;
while(i <= middle && j <= end)
{
if (arr[i] <= arr[j] )
{
tmp[k++] = arr[i++];
}
else
{
tmp[k++] = arr[j++];
}
}
while(i <= middle)
{
tmp[k++] = arr[i++];
}
while(j <= end)
{
tmp[k++] = arr[j++];
}
for (k = begin; k <= end; ++k)
{
arr[k] = tmp[k];
}
}
void MergeSort(int begin,int end)
{
if (begin < end)
{
int middle = (begin + end) / 2;
MergeSort(begin,middle);
MergeSort(middle + 1,end);
Merge(begin,middle,end);
}
}
int main(int argc, char const *argv[])
{
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ",arr[i] );
}
printf("\n");
MergeSort(0,len - 1)