七大排序算法C++实现
TopK问题（面试重灾区）leecode剑指offer40
- 堆排序思想解决(使用优先队列复杂度最低)
- 快排思想解决
排序算法的稳定性
排序过程中，后面的排序不会更改之前已经排序后的数据的顺序，则称这种排序算法是稳定的；否则称为不稳定的。
冒泡排序（稳定）
冒泡还有一种优化，面试时说出来会加分冒泡排序的优化
相邻元素两两比较，反序则交换；
每一轮完毕，将最大元素排在数组顶端；
时间复杂度：o(n^2)
vector<int> sortSolution::bubbleSort(vector<int>& arr) { int n = arr.size(); for(int i = n - 1; i >= 0; --i) { int cnt = 0; for(int j = 0; j < i; ++j) { if(arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); cnt++; } } if(cnt == 0) break; } return arr; }
选择排序(不稳定)
每一趟选出一个最小值，放到前面
时间复杂度：o(n^2)
vector<int> sortSolution::selectSort(vector<int>& arr) { int n = arr.size(); for(int i = 0; i < n - 1; ++i) { int min = i; for(int j = i; j < n; ++j) { if(arr[j] < arr[min]) { min = j; } } if(min != i) { swap(arr[i], arr[min]); } } return arr; }
插入排序（稳定）
不断地从后面选一个数，然后插入到前面已经有序的序列里；
时间复杂度：o(n^2)
vector<int> sortSolution::insertSort(vector<int>& arr) { int n = arr.size(); for(int i = 1; i < n; ++i) { while(i > 0) { if(arr[i] < arr[i - 1]) { swap(arr[i], arr[i - 1]); i--; } else break; } } return arr; }
希尔排序（不稳定）
是一种分组插入排序算法
时间复杂度：o(nlogn) ~ o(n^2)
class Solution { public: vector<int> sortSolution::shelleSort(vector<int>& arr) { int n = arr.size(); for(int gap = n / 2; gap > 0; gap /= 2) { for(int i = gap; i < n; ++i) { int tmp = arr[i]; int j = i - gap; while(j >= 0 && tmp < arr[j]) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } } return arr; } };
快速排序（不稳定）
指定第一个数为mid_value,排序使得mid_value左边的数比mid_value小，右边的数比mid_value大，然后分别对左边和右边进行递归排序。
class Solution { public: void sortSolution::quickSort(vector<int>& arr, int start, int end) { if(start >= end) { return; } int midVal = arr[start]; int low = start; int high = end; while(low < high) { while(low < high && arr[high] >= midbVal) { high--; } arr[low] = arr[high]; while(low < high && arr[low] <= midVal) { low++; } arr[high] = arr[low]; } arr[low] = midVal; quickSort(arr, start, low - 1); quickSort(arr, low + 1, end); } };
归并排序（稳定）
拆分到单个元素，然后两个两个往上进行递归合并。设置left 和right两个游标,进行合并。
时间复杂度：o(nlogn)
class Solution { public: void sortSolution::merge(vector<int> &arr, int left, int mid, int right) { std::vector<int> tmp(right - left + 1); int i = left, j = mid + 1, k = 0; while(i <= mid && j <= right) { tmp[k++] = arr[i] > arr[j] ? arr[i++] : arr[j++]; } while(i <= mid) { tmp[k++] = arr[i++]; } while (j <= right) { tmp[k++] = arr[j++]; } for(int p = 0; p < tmp.size(); ++p) { arr[left + p] = tmp[p]; } } void sortSolution::mergeSort(vector<int>& arr, int left, int right) { if(left >= right) { return; } int mid = (left + right) >> 1; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } };
堆排序（不稳定）
构造堆：从小堆到大堆，先看最后一个非叶子节点，从下往上
建堆的时间复杂度为：o(n)
时间复杂度 ： o(nlogn)
下标为i的节点的父节点下表：（i-1)/2
下表为i的节点的左孩子下表：i*2+1
下表为i的节点的右孩子下表：i*2+2
void sortSolution::maxHeap(vector<int>& arr, int i, int heapSize) { int l = i * 2 + 1; int r = l + 1; int largest = i; if(l < heapSize && arr[l] > arr[largest]) { largest = l; } if(r < heapSize && arr[r] > arr[largest]) { largest = r; } if(largest != i) { swap(arr[i], arr[largest]); maxHeap(arr, largest, heapSize); } } void sortSolution::buildMaxHeap(vector<int>& arr) { for(int i = arr.size() / 2 - 1; i >= 0; --i) { maxHeap(arr, i, arr.size()); } } void sortSolution::heapSort(vector<int>& arr) { buildMaxHeap(arr); for(int i = arr.size() - 1; i > 0; --i) { swap(arr[0], arr[i]); maxHeap(arr, 0, i); } }
