arr[i]=arr[index];
arr[index]=temp;
}
}
}
// Heap Sort,小根堆
void HeapSort(int *arr,int length)
{
// 调整数组生成小根堆
for (int i=length/2;i>=1;i--)
{
HeapAdjust(arr,i,length);
}
for (int i=length;i>1;--i)
{
// 交换堆头的元素和最后一个
int temp=arr[1];
arr[1]=arr[i];
arr[i]=temp;
// 重新调整堆为小根堆
HeapAdjust(arr,1,i-1);
}
}
// HeapAdjust
void HeapAdjust(int *arr, int s,int end)
{
int rloc=arr[s];
for (int j=2*s;j<=end;j=j*2)
{
if (j
{
j++; // 找到两个兄弟节点中最小的节点
}
if (!(arr[j]
break;
}
arr[s]=arr[j];
s=j;
}
arr[s]=rloc;
}
// Merge Sort
void MergeSort(int *arr, int *arr2, int left, int right)
{
if (left==right)
{
arr2[left]=arr[left];
return;
}
if (left
int mid=(left+right)/2;
MergeSort(arr,arr2,left,mid);
MergeSort(arr,arr2,mid+1,right);
Merge(arr,arr2,left,mid,right);
}
}
// Merge Array
void Merge(int *arr, int *arr2, int left, int mid, int right)
{
// 将数组保存到暂存空间中
for (int k=left;k<=right;k++)
{
arr2[k]=arr[k];
}
int s1=left;
int s2=mid+1;
int t=left;
while(s1<=mid&&s2<=right)
{
if (arr2[s1]<=arr2[s2])
{
arr[t++]=arr2[s1++];
}
else
{
arr[t++]=arr2[s2++];
}
}
while(s1<=mid) arr[t++]=arr2[s1++];
while(s2<=right) arr[t++]=arr2[s2++];
}