選擇排序--選擇排序和堆排序

選擇排序：

基本思想：每一趟(第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;
  }
}