一、排序

void swap(vector<int>& a, int x, int y) {if (x == y)return;a[x] = a[x] ^ a[y];a[y] = a[x] ^ a[y];a[x] = a[x] ^ a[y];
}

1.1 冒泡排序BubbleSort

核心思想：相鄰的兩個元素進行大小比較，若前者比后者大，則進行交換

每一輪操作都讓大元素盡可能往后，小元素盡可能往前

void BubbleSort(vector<int>& a) {int len = a.size();int mark = len - 1;	//優化方案：標記已經排序好的后半部分，使得每次遍歷的個數和遍歷輪數減少for (int i = len - 1; i >= 0; i--) {for (int j = 0; j < i; j++) {if (a[j] > a[j + 1]) {	//交換swap(a, j, j + 1);mark = j;}}if (mark == i)	//若沒有發生交換，說明已經有序break;else i = mark + 1;}	
}

1.2 簡單選擇排序SelectSort

核心思想：每一次找最值放到響應的位置

void SelectSort(vector<int>& a) {int minIndex;int len = a.size();for (int i = 0; i <= len - 1; i++) {minIndex = i;for (int j = i+1; j < len; j++) {if (a[j] < a[minIndex]) {minIndex = j;}}swap(a, i, minIndex);}
}

1.3 插入排序InsertSort

核心思想：數據分成兩部分，一部分有序一部分無序，將無序的元素依次插入到有序的序列中

void InsertSort(vector<int>& a) {int len = a.size();for (int i = 1; i < len; i++) {if (a[i - 1] > a[i]) {int temp = a[i];int j;for (j = i - 1; j >= 0 && a[j] > temp; j--)a[j + 1] = a[j];a[j + 1] = temp;}}
}