相关链接：
https://blog.csdn.net/weixin_41545534/article/details/115567889?spm=1001.2014.3001.5506
https://blog.csdn.net/weixin_50886514/article/details/119045154?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165301469816781667834550%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165301469816781667834550&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-119045154-null-null.142^v10^pc_search_result_control_group,157^v4^control&utm_term=%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187
一、冒泡排序#include二、选择排序#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void BubbleSort(vector & vec) { int n=vec.size(); if (n == 0) return; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { if (vec[i] > vec[j]) { int tmp = vec[j]; vec[j] = vec[i]; vec[i] = tmp; } } } } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); BubbleSort(vec); PrintVec(vec); std::cout << "Hello World!n"; }
每次外循环选择剩余最小排好。
#include三、插入排序#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void ChooseSort(vector & vec) { int n=vec.size(); if (n == 0) return; for (int i = 0; i < n-1; ++i) { int smallest = i; for (int j = i+1; j < n; ++j) { if (vec[j] < vec[smallest]) { smallest = j; } } int tmp = vec[i]; vec[i] = vec[smallest]; vec[smallest] = tmp; } } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); ChooseSort(vec); PrintVec(vec); std::cout << "Hello World!n"; }
#include四、希尔排序#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void InsertSort(vector & vec) { int n=vec.size(); if (n == 0) return; for (int i = 1; i < n; ++i) { for (int j = i; j >=1; --j) { if (vec[j-1] > vec[j]) { int tmp = vec[j-1]; vec[j-1] = vec[j]; vec[j] = tmp; } } } } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); InsertSort(vec); PrintVec(vec); std::cout << "Hello World!n"; }
#include五、归并排序#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void ShellSort(vector & vec) { int n=vec.size(); if (n == 0) return; int gap = n; while (gap > 1) { gap = gap / 2; //Insert Sort //from gap+1 on for (int i = gap; i < n; ++i) { for (int j = i; j >=gap; j -= gap) { if (vec[j - gap] > vec[j]) { int tmp = vec[j-gap]; vec[j - gap] = vec[j]; vec[j] = tmp; } } } } } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); ShellSort(vec); PrintVec(vec); return 0; }
#include六、快速排序#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void Merge(vector & vec, int l,int m, int r) { if (l >= r) return; int len = r - l + 1; vector tmp(len); int i = l, j = m + 1; int k = 0; while ((i <= m) && (j <= r)) { if (vec[i] <= vec[j]) { tmp[k++] = vec[i++]; } else { tmp[k++] = vec[j++]; } } while (i <= m) { tmp[k++] = vec[i++]; } while (j <= r) { tmp[k++] = vec[j++]; } for (k = l; k <= r; k++) { vec[k] = tmp[k-l]; } } void MergeSort(vector & vec,int l,int r) { if (l >= r) return; int m = (l + r) / 2; MergeSort(vec, l, m); MergeSort(vec, m+1, r); Merge(vec, l, m, r); } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); MergeSort(vec,0,vec.size()-1); PrintVec(vec); return 0; }
https://blog.csdn.net/qq_40941722/article/details/94396010?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165300584216780366582335%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165300584216780366582335&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-94396010-null-null.142^v10^pc_search_result_control_group,157^v4^control&utm_term=快速排序&spm=1018.2226.3001.4187
#include七、堆排序#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void QuickSort(vector & vec, int l,int r) { if (l >= r) return; int pivot = vec[l]; int i = l, j = r; while (i < j) { //move j while (pivot <= vec[j] && j > i) { j--; } while (pivot >= vec[i] && j > i) { i++; } if (i < j) { int tmp = vec[i]; vec[i] = vec[j]; vec[j] = tmp; } } vec[l] = vec[i]; vec[i] = pivot; QuickSort(vec, l, i-1); QuickSort(vec, i+1, r); } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); QuickSort(vec,0,vec.size()-1); PrintVec(vec); return 0; }
https://blog.csdn.net/weixin_41545534/article/details/115567889?spm=1001.2014.3001.5506
#include#include using namespace std; vector vec = { 3,5,8,7,9,4,14,15,82,37,27,45,66,1 }; void Adjust(vector & vec,int end, int idx) { int left_idx = 2 * idx + 1; int right_idx = 2 * idx + 2; int max_idx=idx; if (left_idx < end && vec[left_idx]>vec[max_idx]) max_idx = left_idx; if (right_idx < end && vec[right_idx]>vec[max_idx]) max_idx = right_idx; //if changed if (max_idx != idx) { swap(vec[max_idx],vec[idx]); Adjust(vec,end, max_idx); } } void HeapSort(vector & vec) { //Build Heap int n = vec.size(); if (n == 0) return; for (int i = (n/2-1); i >=0; --i) { Adjust(vec, n,i); } //swap and re-adjust 0-i element for (int i = n - 1; i >= 1; --i) { swap(vec[i],vec[0]); Adjust(vec,i, 0); } } void PrintVec(const vector & vec) { for (auto it : vec) { cout << it << " "; } cout << endl; } int main() { PrintVec(vec); HeapSort(vec); PrintVec(vec); return 0; }
