排序算法-之选择排序（直接选择排序，堆排序）
一、排序算法分为：
1.插入排序（直接插入排序&希尔排序）
2.选择排序（直接选择排序&堆排序）
3.交换排序（冒泡排序&快速排序）
4.归并排序
二，选择排序----直接选择排序
1.算法代码
//选择排序
//直接选择排序
void SelectSort(int* a,size_t n)
{
assert(a);
size_t left = 0;//下标
size_t right = n-1;
while(left<right)
{
size_t min = left;//下标
size_t max = left;;
for(size_t i=left;i<=right;++i)
{
if(a[min] > a[i])
min = i;
if(a[max]<a[i])
max = i;
}
swap(a[min],a[left]);//将最小的数放到左边
//修正
if(max == left)//?有好几种情况
max = min;
swap(a[max],a[right]);
++left;
--right;
}
}
////测试代码
void PrintArray(int* a,size_t n)
{
for(size_t i=0;i<n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void SelectSortTest()
{
int a[]={2,5,4,0,9,3,6,8,7,1};
PrintArray(a,sizeof(a)/sizeof(a[0]));
SelectSort(a,sizeof(a)/sizeof(a[0]));
PrintArray(a,sizeof(a)/sizeof(a[0]));
}
2.时间复杂度
最好情况：O（n^2）
最坏情况：O（n^2）
平均时间复杂度：O（n^2）
空间复杂度：O（1）
3.稳定性
选择排序是不稳定的（把最小值换到已排序的末尾导致的），每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。
三.选择排序----堆排序
1.算法代码
//堆排序2.时间复杂度
void AdjustDown(int* a,size_t root,size_t n)
{
size_t parent = root;
size_t child = parent*2+1;
while(child<n)
{
if((child+1)<n && a[child+1]>a[child])
{
++child;
}
if(a[child]>a[parent])
{
swap(a[child],a[parent]);
parent = child;
child = parent*2+1;
}
else
{
break;
}
}
}
void HeapSort(int* a,size_t n)
{
assert(a);//????
for(int i=(n-2)/2;i>=0;--i)
{
AdjustDown(a,i,n);
}
size_t end=n-1;
while(end>0)
{
swap(a[0],a[end]);
AdjustDown(a,0,--end);
}
}
////测试代码
void PrintArray(int* a,size_t n)
{
for(size_t i=0;i<n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
void HeapSortTest()
{
int a[]={2,5,4,0,9,3,6,8,7,1};
PrintArray(a,sizeof(a)/sizeof(a[0]));
HeapSort(a,sizeof(a)/sizeof(a[0]));
PrintArray(a,sizeof(a)/sizeof(a[0]));
}
最好情况：O（nlogn）
最坏情况：O（nlogn）
平均时间 复杂度：O（nlogn）
空间复杂度：（O(1)）
3.稳定性
堆排序是不稳定的，因为利用的排序空间仍然是初始的序列，并未开辟新的空间，算法是不稳定的，与初始序列无关。