# **排序演算法**

# **Bubble Sort 氣泡排序法**

排序原理 : 從最右邊開始，兩兩比較，將較小的數字交換至左邊，第一輪結束後換到最左邊的就是整個數列最小的數字，這個數字就固定了不參與排序。接下來每一輪的做法都一樣直到排序結束。
* 時間複雜度 : О(n²)
* 空間複雜度 : O(1)
* 執行結果 : TLE

#include <stdio.h>

int main(void) 
{   
   int arr[] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37}; 
   int arr_len = sizeof(arr) / sizeof(int);
  
   printf("原本的\n");
   
   for(int i = 0; i < arr_len; i++) // 輸出
   {
      printf("%4d", arr[i]);
   } 
                   
   for(int pass = 1; pass < arr_len; pass++) // 全部有幾次
   {                    
      for (int i = 0; i < arr_len - pass; i++) // 還沒排序的部分
      {                     
         if (arr[i] > arr[i + 1]) // 判斷大小
         {
            int hold = arr[i]; // 交換                                  
            arr[i] = arr[i + 1];                             
            arr[i + 1] = hold;                               
         }                                       
      }                                   
   }                                      

   printf("\n排序後\n");

   for(int i = 0; i < arr_len; i++) // 輸出
   {
      printf("%4d", arr[i]);
   } 

   printf("");
}

# **Selection Sort 選擇排序法**

排序原理 : 找出數列中最小的值，將其與數列最左邊的數字交換並固定不再參與排序。下一輪一樣重複步驟直到排序完畢。
* 時間複雜度 : О(n²)
* 空間複雜度 : O(1)
* 執行結果 : TLE

#include <stdio.h>

void swap(int *x, int *y) // 交換
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

void selection_Sort(int arr[], int n) // 排序
{
	int min_index;

	for(int check_idx = 0; check_idx < n - 1; check_idx++) // 總共做幾次，以i做為比較的索引值
  {
		min_index = check_idx;
		for(int current_idx = check_idx + 1; current_idx < n; current_idx++) // 拿第i項去比較未排序的部分
    {
			if (arr[current_idx] < arr[min_index]) // 找出未排序部分的最小值
      {
					min_index = current_idx;
			}
		}
		swap(&arr[min_index], &arr[check_idx]); // 最小值與第i項交換
	}
}

void print_Array(int arr[], int size) // 輸出
{
	int i;
	for(i = 0; i < size; i++)
  {
    printf("%d ", arr[i]);
  }
	printf("\n");
}

int main()
{
	int arr[] = {64, 25, 12, 22, 11};
	int n = sizeof(arr) / sizeof(arr[0]);
  printf("排序前 \n");
  print_Array(arr, n);
	selection_Sort(arr, n);
	printf("排序後 \n");
	print_Array(arr, n);
	return 0;
}

# **Insertion Sort 插入排序法**

排序原理 : 先將數列中最左邊的數字固定，接下來每一輪都選取除了固定數字的最左邊的數字與已固定的數字進行比較，小於就往左邊移動，反之大於此輪結束並固定。以此類推直到排序結束。
* 時間複雜度 : О(n²)
* 空間複雜度 : O(1)
* 執行結果 : TLE

#include <math.h>
#include <stdio.h>

void insertion_Sort(int arr[], int n) // 排序
{
	int current_turn, current_num, check_num;
  
	for(current_turn = 1; current_turn < n; current_turn++) // 預設第一個數字為已排序，從第二個數字向右取數字進行比較
  {
		current_num = arr[current_turn];
		check_num = current_turn - 1;
    
		while(check_num >= 0 && arr[check_num] > current_num) // 如果左邊的數字比較大，將其向右平移
    {
			arr[check_num + 1] = arr[check_num];
			check_num = check_num - 1;
		}
    
		arr[check_num + 1] = current_num; // 將數字放進平移後產生的空格中
	}
}

void print_Array(int arr[], int n) // 輸出
{
	int i;
	for (i = 0; i < n; i++)
  {
    printf("%d ", arr[i]);
  }
	printf("\n");
}

int main()
{
	int arr[] = { 12, 11, 13, 5, 6 };
	int arr_len = sizeof(arr) / sizeof(arr[0]);
  printf("排序前\n");
  print_Array(arr, arr_len);
	insertion_Sort(arr, arr_len);
  printf("排序後\n");
	print_Array(arr, arr_len);

	return 0;
}

# **Quick Sort 快速排序法**

排序原理 : 選取數列中的一個數字當成基準值，較大的數字往基準值的右邊放，較小的數字往基準值的左邊放，分類完之後再以同樣的方式對分堆進行排序直到排序結束。
* 時間複雜度 : O(n*log n) ~ О(n²)
* 空間複雜度 : O(log n)
* 執行結果 : TLE

#include <stdio.h>

void swap(int* a, int* b) // 交換
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 
  
int partition (int arr[], int low, int high) 
{ 
    int compare_value = arr[high]; // 以最右邊的數字當作基準值
    int left = (low - 1); // 左邊分堆的範圍 

    for(int current_index = low; current_index <= high - 1; current_index++)
    {
        if(arr[current_index] < compare_value) // 如果當前數字小於基準值就分到左邊
        {
            left++; // 左邊分堆的長度+1
            swap(&arr[left], &arr[current_index]); // 把數字分到左邊
        }
    }
    // 因為分完左邊的之後，剩下再右邊的都是比基準值大的
    swap(&arr[left + 1], &arr[high]); // 把基準值插到兩堆中間
    return (left + 1); // 回傳基準值的索引值
} 
  
void quick_Sort(int arr[], int low, int high) // 排序
{ 
    if (low < high) 
    { 
        int mid = partition(arr, low, high); // 分成左右(小大)兩堆並取得基準值的索引值
  
        quick_Sort(arr, low, mid - 1); // 將左邊分堆再進行quickSort一次
        quick_Sort(arr, mid + 1, high); // 將右邊分堆再進行quickSort一次
    } 
} 
  
void print_Array(int arr[], int n) // 輸出
{
    int i;
    for (i = 0; i < n; i++)
    {
       printf("%d ", arr[i]);    
    }
    printf("\n");
}
  
int main() 
{ 
    int arr[] = {10, 7, 8, 9, 1, 5}; 
    int arr_len = sizeof(arr) / sizeof(arr[0]); 
    printf("排序前\n");
    print_Array(arr, arr_len); 
    quick_Sort(arr, 0, arr_len - 1); 
    printf("排序後\n");
    print_Array(arr, arr_len); 
    return 0; 
}

# **結論**
理論上來說快速排序法是有機會AC的，但我的程式碼取得的基準值是極端值，這樣等於只排了一個，每次右邊都沒東西，就沒有所謂的分堆，因而導致TLE。

速度 : 快速排序法 > 選擇排序法 > 插入排序法 > 氣泡排序法
記憶體 : 快速排序法 > 氣泡排序法, 選擇排序法, 插入排序法