选择排序--选择排序和堆排序

选择排序：

基本思想：每一趟(第i趟，i=0,1，…，n-2)在后面n-i个待排序的数据元素集合中选出关键码最小的数据元素，作为有序元素序列的第i个元素。待到第n-2趟做完，待排序元素集合中只剩下1 个元素，排序结束。

一、选择排序

每一次在一组数中选最大的放到最后,然后再在剩余的数中选次大的数放到倒数第二个位置,直到这组数选完为止;(以升序为例)

void SelectSort(int *array, size_t size)
{
  for (size_t i = 0; i < size - 1; i++)
  {
    size_t maxPos = 0;
    for (size_t j = 1; j < size - i; j++)
    {
      if (array[j]>array[maxPos])
        maxPos = j;
    }
    if (maxPos != size - i - 1)
      swap(array[maxPos], array[size - i - 1]);
  }
}      

时间复杂度O(N^2)

稳定性：不稳定

优化：

的简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。

改进后，对n个数据进行排序,最多只需进行[n/2]趟循环即可。

1、首先标记最大和最小的位置的下标

2、判断最左位置下标的数和最小值下标的数比较,如果大则两者相交换,否则向后移动；

  判断最右位置下标的数和最大值下标的数比较,如果小则交换.

代码如下：

void SelectSortOP(int *array, size_t size)
{
  size_t begin = 0;
  size_t end = size - 1;
  while (begin < end)
  {
    size_t minPos = begin;
    size_t maxPos = begin;
    size_t i = begin + 1;

    while (i <= end)
    {
      if (array[i] < array[minPos])
        minPos = i;
      if (array[i]>array[maxPos])
        maxPos = i;
      i++;
    }

    if (maxPos!=end)
      swap(array[maxPos], array[end]);
    if (minPos == end)
      minPos = maxPos;
    
    if (minPos != begin)
      swap(array[minPos], array[begin]);
    ++begin;
    --end;
  }
}      

二、堆排序

我们知道堆其实就是一颗完全二叉树或者我们可以看成是近似完全二叉树，

1、父节点的值大于或者等于任何一个子节点的值

2、左右子树都是堆

堆排序就是一种选择排序,我们以大堆为例,我们把堆顶与最后的位置交换,然后其余的元素继续调整建堆,再把堆顶的元素和倒数第二个位置的元素进行交换,直到所有的数有序。

1、创建堆---升序：大堆    

     降序：小堆

2、堆排序

用堆顶元素和最后一个元素交换

调整堆---

找左右孩子中最大的child，

检测child是否比parent大-->child>parent--交换--继续调整       child<parent--退出

//堆排
void AdjustDown(int *array, size_t size, size_t parent)
{
  //默认左孩子最小
  size_t child = parent * 2 + 1;

  while (child < size)
  { 
    if (child + 1 < size && array[child + 1] > array[child])
      child++;
    if (array[child]>array[parent])
    {
      swap(array[child], array[parent]);
      parent = child;
      child = parent * 2 + 1;
    }
    else
      break;
  }
}

void HeapSort(int *array, size_t size)
{
  //创建堆
  for (int root = (size - 2) >> 1; root >= 0; root--)
    AdjustDown(array, size, root);

  //堆排序
  size_t end = size - 1;
  while (end > 0)
  {
    swap(array[0], array[end]);
    AdjustDown(array, end, 0);
    --end;
  }
}