记录了冒泡排序，选择排序，直接插入排序，希尔排序，快速排序，堆排序和归并排序的实现。
#include<iostream> #include<vector> using namespace std; void bubbleSort(vector<int> &s) { for (int i = s.size(); i > 0; i--) { for (int j = 1; j < i; j++) if (s[j - 1] > s[j]) swap(s[j - 1], s[j]); } } void bubbleSortUp(vector<int> &s) { bool sign = false; for (int i = s.size(); !sign&&i > 0; i--) { sign = true; for (int j = 1; j < i; j++) if (s[j - 1] > s[j]) { swap(s[j - 1], s[j]); sign = false; } } } void insertSort(vector<int> &s) { for (int i = 1; i < s.size(); i++) { int temp = s[i],j; for (j = i - 1; j >= 0 && s[j] > temp; j--) s[j + 1] = s[j]; s[j + 1] = temp; } } void selectSort(vector<int> &s) { for (int i = 0; i < s.size(); i++) { int min = i; for (int j = i + 1; j < s.size(); j++) min = s[min] > s[j] ? j : min; swap(s[i], s[min]); } } void shellSort(vector<int>& s) { int increament = s.size(); while (increament > 1) { increament = increament / 3 + 1; for (int i = increament; i < s.size(); i++) { int temp = s[i], j; for (j = i - increament; j >= 0 && s[j] > temp; j = j - increament) s[j + increament] = s[j]; s[j + increament] = temp; } } } int quick(vector<int> &s, int left, int right) { int temp = s[left]; while (left < right) { while (left<right&&s[right] >= temp) right--; swap(s[left], s[right]); while (left < right&&s[left] < temp) left++; swap(s[left], s[right]); } return left; } void quickSort(vector<int> &s, int left, int right) { if (left >= right) return; int temp = quick(s, left, right); quickSort(s, left, temp - 1); quickSort(s, temp + 1, right); return; } void heap(vector<int>& s, int index, int len) { int left = 2 * index + 1; int right = 2 * index + 2; int max = index; if(left <= len) max = s[max] < s[left] ? left : max; if(right <= len) max = s[max] < s[right] ? right : max; if (max != index) { swap(s[max], s[index]); heap(s, max, len); } return; } void creatHeap(vector<int>& s) { int num = s.size() >> 1 - 1; for (int i = num; i >= 0; i--) heap(s, i, s.size() - 1); } void heapSort(vector<int>& s) { creatHeap(s); for (int i = s.size()-1; i >= 0; i--) { swap(s[0], s[i]); heap(s, 0, i-1); } } void merage(vector<int> &s, int left, int mid, int right) { int i = left, j = mid + 1; vector<int> data; while (i <= mid && j <= right) { if (s[i] < s[j]) { data.push_back(s[i]); i++; } else { data.push_back(s[j]); j++; } } while (i <= mid) { data.push_back(s[i]); i++; } while (j <= right) { data.push_back(s[j]); j++; } for (int i = left; i <= right; i++) s[i] = data[i - left]; return; } void merageSort(vector<int> &s, int left, int right) { if (left == right) return; int mid = (left + right) >> 1; merageSort(s, left, mid); merageSort(s, mid + 1, right); merage(s, left, mid, right); } void Show(const vector<int>& s) { for (int temp : s) cout << temp << " "; cout << endl; } int main() { vector<int> test = { 1,4,2,5,3,5,8,7,5,0 }; Show(test); merageSort(test,0,test.size()-1); Show(test); return 0; }