# 初階排序

排序演算法

	#include <iostream>
	#include <vector>
	#include <algorithm>

	using namespace std;

	// Bubble Sort mark:3-4
	void bubbleSort(vector<int>& arr) {
	int n = arr.size();
	for (int i = 0; i < n - 1; i++) {
	for (int j = 0; j < n - i - 1; j++) {
	if (arr[j] > arr[j + 1]) {
	swap(arr[j], arr[j + 1]);
	}
	}
	}
	}

	// Selection Sort
	// 1. 先選這輪的最小
	// 2. 跟 i 交換
	void selectionSort(vector<int>& arr) {
	int n = arr.size();
	for (int i = 0; i < n - 1; i++) {
	int minIndex = i;
	for (int j = i + 1; j < n; j++) {
	if (arr[j] < arr[minIndex]) {
	minIndex = j;
	}
	}
	swap(arr[i], arr[minIndex]);
	}
	}

	// Insertion Sort
	// 1. 依序給這一輪的 value
	// 2. value 跟前面的比
	// 3. 放到完成的位置
	void insertionSort(vector<int>& arr) {
	int n = arr.size();
	for (int i = 1; i < n; i++) {
	int key = arr[i];
	int j = i - 1;
	while (j >= 0 && arr[j] > key) {
	arr[j + 1] = arr[j];
	j--;
	}
	arr[j + 1] = key;
	}
	}

	int main() {
	vector<int> arr = {5, 2, 8, 3, 1};

	// Bubble Sort
	bubbleSort(arr);
	cout << "Bubble Sort: ";
	for (int num : arr) {
	cout << num << " ";
	}
	cout << endl;

	// Selection Sort
	arr = {5, 2, 8, 3, 1};
	selectionSort(arr);
	cout << "Selection Sort: ";
	for (int num : arr) {
	cout << num << " ";
	}
	cout << endl;

	// Insertion Sort
	arr = {5, 2, 8, 3, 1};
	insertionSort(arr);
	cout << "Insertion Sort: ";
	for (int num : arr) {
	cout << num << " ";
	}
	cout << endl;

	return 0;
	}

# Quick sort

	#include <iostream>
	#include <vector>

	using namespace std;

	// 快速排序 (Quick Sort)
	// 最壞情況時間複雜度：O (n^2)
	// 平均情況時間複雜度：O (nlogn)
	// 最佳情況時間複雜度：O (nlogn)
	int partition(vector<int>& arr, int low, int high) {
	int pivot = arr[high]; // 選擇最後一個元素作為主元
	int i = low - 1;

	for (int j = low; j < high; j++) {
	if (arr[j] < pivot) {
	i++;
	swap(arr[i], arr[j]);
	}
	}

	swap(arr[i + 1], arr[high]);
	return i + 1;
	}

	void quickSort(vector<int>& arr, int low, int high) {
	if (low < high) {
	int pivotIndex = partition(arr, low, high);

	// 遞迴地對分割後的子陣列進行排序
	quickSort(arr, low, pivotIndex - 1);
	quickSort(arr, pivotIndex + 1, high);
	}
	}
	int main() {
	vector<int> arr = {5, 2, 8, 3, 1};

	// 快速排序
	cout << "快速排序結果：" << endl;
	quickSort(arr, 0, arr.size() - 1);
	for (int num : arr) {
	cout << num << " ";
	}
	cout << endl;

	return 0;
	}

在快速排序中，我們使用 partition 函式將陣列分割為比主元小和比主元大的兩個子陣列。
然後，我們遞迴地對這兩個子陣列進行排序，直到排序完成。