排序演算法（C++）

詳細排序原理可以參考：圖文詳解—十大經典排序演算法

1 冒泡排序

//冒泡排序
void bubbleSort(vector<int> & vec) {
	int len = vec.size();
	for (int i = 0; i < len; i++) {
		//此處的i是為了界定遍歷的長度
		for (int j = 0; j < len - i - 1; j++) {
			if (vec[j] > vec[j + 1]) {
				int temp = vec[j];
				vec[j] = vec[j + 1];
				vec[j + 1] = temp;
			}
		}
	}
}

2 選擇排序

//選擇排序
void selectSort(vector<int>& vec) {
	int len = vec.size();
	for (int i = 0; i < len; i++) {
		int maxIndex=0;
		for (int j = 1; j < len - i ; j++) {
			if (vec[maxIndex] < vec[j]) maxIndex = j;
		}
		int temp = vec[maxIndex];
		vec[maxIndex] = vec[len - i - 1];
		vec[len - i - 1] = temp;
	}
}

3 插入排序

//插入排序
void insertSort(vector<int>& vec) {
	int len = vec.size();
	for (int j = 1; j < len; j++) {
		int i, key; 
		key = vec[j];
		for (i = j - 1; i >= 0 && key < vec[i]; i--) {
			//此時第一個i+1等于j
			vec[i + 1] = vec[i];
		}
		vec[i + 1] = key;
	}
}

4 希爾排序

//希爾排序
void shellSort(vector<int>& vec) {
	int len = vec.size();
	for (int gap = 5; gap > 0; gap /= 2) {
		for (int j = gap; j < len; j++) {
			int i, key = vec[j];
			for (i = j - gap; i >= 0 && key < vec[i]; i -= gap) {
				vec[i + gap] = vec[i];
			}
			vec[i + gap] = key;
		}
	}
}

5 歸并排序

//參考鄧俊輝《資料結構》書中歸并排序
void merge(int* arr, int lo, int mi, int hi) {
	int* A = arr + lo;//A[0,hi-lo)=arr[lo,hi)
	//B[0,mi-lo)=arr[lo,mi)
	int lb = mi - lo;
	int* B = new int[lb];//分配lb個單位的連續整型空間
	for (int i = 0; i < lb; i++) {
		B[i] = arr[lo + i];//B[i]=*(arr+lo+i);
	}
	//C[0,hi-mi)=arr[mi,hi)
	int lc = hi - mi;
	int* C = arr + mi;
	for (int i = 0, j = 0, k = 0; i < lb || j < lc;) {
		if ((i < lb) && (!(j < lc) || B[i] < C[j])) A[k++] = B[i++];
		if ((j < lc) && (!(i < lb) || C[j] <= B[i])) A[k++] = C[j++];
	}
}

void mergeSort(int arr[], int lo, int hi) {
	if (hi - lo < 2) return;
	int mi = (lo + hi) / 2;
	mergeSort(arr, lo, mi);
	mergeSort(arr, mi, hi);
	merge(arr, lo, mi, hi);
}

6 快速排序

//快速排序
void quickSort(int* arr,int left,int right) {
	//此處必須要寫為>=;若寫為==則會出錯
	if (left >= right) return;
	int l = left;
	int r = right;
	int pivot = arr[l];
	//標志為false時，表示改指標上的資料已被拿出
	//標志為true時，表示指標上的資料未被拿出
	bool fflag = false;
	bool rflag = true;
	while (l < r) {
		if (rflag) {
			if (!fflag && arr[r] < pivot) {
				arr[l] = arr[r];
				fflag = true;
				rflag = false;
			}
			else r--;
		}
		if (fflag) {
			if (!rflag && arr[l] >= pivot) {
				arr[r] = arr[l];
				fflag = false;
				rflag = true;
			}
			else l++;
		}
	}
	arr[l] = pivot;
	quickSort(arr, left, l - 1);
	quickSort(arr, l + 1, right);
}

7 堆排序

堆排原理詳細可以參考B站視頻：https://www.bilibili.com/video/BV1Eb41147dK

void swap(int tree[], int a, int b) {
	int temp=tree[a];
	tree[a] = tree[b];
	tree[b] = temp;
	
}

//此處的n為傳入的陣列的大小
void heapify(int tree[], int n, int i) {
	if ((2 * i + 1) > n-1) return;
	int pare = (i - 1) / 2;
	int lchild = 2 * i + 1;
	int rchild = 2 * (i + 1);
	int maxIndex = i;
	if (tree[maxIndex] < tree[lchild]) maxIndex = lchild;
	if (tree[maxIndex] < tree[rchild]) maxIndex = rchild;
	if (maxIndex != i)
	{
		swap(tree, maxIndex, i);
		i = maxIndex;
		heapify(tree, n, i);
	}
}

//當數列完全無序時，生成堆序列
void generateHeap(int tree[], int n) {
	int last = ((n - 1) - 1) / 2;
	for (int i = last; i >= 0; i--) {
		heapify(tree, n, i);
	}
}

//堆排序
void heapSort(int tree[],int n) {
	generateHeap(tree, n);
	for (int i = n - 1; i > 0; i-- ) {
		swap(tree, i, 0);
		heapify(tree, i - 1, 0);
	}
}