[ 資料結構 -- 手撕排序算法第四篇 ] 選擇排序

 手撕排序算法系列之第四篇：選擇排序。

從本篇文章開始，我會介紹并分析常見的幾種排序，大緻包括​​直接插入排序​​​，​​冒泡排序​​​，​​希爾排序​​，選擇排序，堆排序，快速排序，歸并排序等。​

本篇主要來手撕選擇排序~~  

目錄

1.常見的排序算法 

2.直接選擇排序

3.選擇排序的實作

4.選擇排序測試

5.選擇排序時間複雜度

6.選擇排序的特性總結

1.常見的排序算法

1.1選擇排序

選擇排序的基本思想：

每一次從待排序的資料元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完 。 

​

2.直接選擇排序

2.1基本思想（一次選一個數）

1、我們周遊一遍數組選出一個最小的數字。

2、讓第一個數字和這個數字交換（預設升序排序），此時最小的數字就來到了第一個位置。

3、重複1操作選出第二小的數字，讓第二個數字和這個次小的數字交換，此時最小的數字就來到了第二個位置.....循環選擇排序，直至排序完成。

分析圖解：

​

2.2基本思想（一次選兩個數）

 這個方法每次隻選擇一個數字，顯然有點大材小用。因為既然每次要選擇數字，我們不妨每次選擇2個數字。具體步驟如下：

1、我們周遊一遍數組選出一個最小的數字和一個最大的數字。

2、選擇完成後讓最小的數字放到第一個位置，最大的數字放到最後的位置。

3、當左邊left大于等于右邊right時說明排序完成

​

3.選擇排序的實作

為了提高選擇的效率，我們這裡所選擇的是每次選兩個數，一個最大數一個最小數。這裡我們需要有一個非常非常重要的細節需要把控。

如果有這麼一種特殊的情況，在原數組中第一個位置的數字是整個數組最大的數字，那麼按照我們之前的邏輯挪動還能得到我們想要的結果嗎？結果是不能，具體分析看下圖過程解析。

​ 

 是以為了避免此類問題造成結果出錯，我們需要在程式中加一個修正，修正的邏輯如下：

如果最左邊的left位置和max重疊，我們讓min位置的值指派給max位置，因為在第一次最小數字和left交換的時候，最大的數字被交換到了min位置。畫圖邏輯如下

​

3.1選擇排序實作代碼

//選擇排序
void SelectSort(int* a, int n)
{
  int left = 0, right = n - 1;
  while (left < right)
  {
    int mini = left, maxi = left;
    for (int i = left + 1; i <= right; ++i)
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
  
    Swap(&a[left], &a[mini]);
    //如果left和maxi重疊,修正一下maxi即可
    if (left == maxi)
      maxi = mini;
    Swap(&a[right], &a[maxi]);

    left++;
    right--;
  }
}      

4.選擇排序測試

//選擇排序
void SelectSort(int* a, int n)
{
  int left = 0, right = n - 1;
  while (left < right)
  {
    int mini = left, maxi = left;
    for (int i = left + 1; i <= right; ++i)
    {
      if (a[i] < a[mini])
      {
        mini = i;
      }
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
  
    Swap(&a[left], &a[mini]);
    //如果left和maxi重疊,修正一下maxi即可
    if (left == maxi)
      maxi = mini;
    Swap(&a[right], &a[maxi]);

    left++;
    right--;
  }
}
//列印數組
void PrintArray(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
}

//選擇排序
void TestSelectSort()
{
  int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
  SelectSort(a, sizeof(a) / sizeof(int));
  PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
  //選擇排序
  TestSelectSort();

  return 0;
}      

測試結果：

​

5.選擇排序時間複雜度

選擇排序的時間複雜度是O(n^2)。

無論是順序還是逆序，選擇排序的時間複雜度都是O(n^2)，這是因為在每遍篩選數組時，都要周遊數組選出最大和最小的數組，每一次周遊即是O(n)。即使是自身有序的數組，但是計算機是不知道的，還是要周遊一遍選出最小和最大的。是以綜上所述選擇排序的時間複雜度是O(n^2)。 

6.選擇排序的特性總結

直接選擇排序的特性總結：

1. 直接選擇排序思考非常好了解，但是效率不是很好。實際中很少使用

2. 時間複雜度：O(N^2)

3. 空間複雜度：O(1)