排序算法总结(超详细)
排序算法总结
直接插入排序
基本思想:将一个值插入到已经排好序中的相应位置。
void InsertSort(std::vector<int>& arr) { for (size_t i = 1; i < arr.size(); i++) { if (arr[i] < arr[i-1]) { size_t k = i; int val = arr[k]; //保存下自己 arr[k] = arr[i-1];//向后移一位 while (val < arr[k-1] && k > 0) { arr[k] = arr[k-1]; k--; } arr[k] = val; printArray(i, arr); } } }
冒泡排序
基本思想:两两比较相邻纪录的关键字,如果是反序的则进行交换。
// 普通排序 void BubbleSort(std::vector<int>& arr) { size_t len = arr.size(); for (size_t i = 0; i < len; i++) { //内层的每一次循环,都会将最大的数推向数组高层,也就是说i代表了高层中已经排好序的个数 for (int j = 1; j < len-i; j++) { if (arr[j-1] > arr[j]) { //两两比较 std::swap(arr[j-1], arr[j]); } } printArray(i, arr); } } // 设置标记位,如果一次循环中没有移位,那么则表明接下来的值的顺序已经排好了 void BubbleSort2(std::vector<int>& arr) { size_t len = arr.size(); bool flag = true; size_t k = len; while (flag) { flag = false; for (int j = 1; j < k; j++) { if (arr[j-1] > arr[j]) { std::swap(arr[j-1], arr[j]); flag = true; } } k --; } } // 设置上次移动的位置,表明上次之前的位置已经拍好了序,接下来只需要排上次位置之前的即可 void BubbleSort3(std::vector<int>& arr) { size_t len = arr.size(); size_t flag = len; while (flag > 0) { size_t k = flag; flag = 0; for (size_t j = 1; j < k; j++) { if (arr[j-1] > arr[j]) { //两两比较 std::swap(arr[j-1], arr[j]); flag = j; } } } } // 双向冒泡排序,在之前的排序中,每次的内层循环只能找出一个最大值或者最小值 // 现在双向排序后同时找出一个最大值和最小值 void BubbleSort4(std::vector<int>& arr) { size_t low = 0, high = arr.size() - 1; while (low < high) { for (size_t i = low; i < high; i++) { if (arr[i] > arr[i + 1]) { std::swap(arr[i], arr[i + 1]); } } high--; for (size_t i = high; i > low; i--) { if (arr[i - 1] > arr[i]) { std::swap(arr[i - 1], arr[i]); } } low++; } }
简单选择排序
基本思想:从一个数组中选择一个最小(或者最大)的值和第一个位置进行交换,接着选择次的值和第二个位置交换,以此类推。
void SelectSort(std::vector<int>& arr) { // 每次从指定的数组间隔中选择一个最小的 auto selectMin = [&](size_t start) { size_t k = start; for (size_t i = start+1; i < arr.size(); i++) { if (arr[i] < arr[k]) { k = i; } } std::cout << "min:" << arr[k] << std::endl; return k; }; size_t len = arr.size(); for (size_t i = 0; i < len; i++) { size_t idx = selectMin(i); if (idx != i) { std::swap(arr[idx], arr[i]); } printArray(i, arr); } }
快速排序
基本思想:
- 选择一个基准元素,通常选择第一个或者最后一个元素;
- 通过一趟排序将待排序的纪录分割成两个部分,其中一个部分比基准元素的值都小,另一个部分比基准元素都要大;
- 此时基准元素在排好序的正确位置;
- 然后分别对这两部分用同样的方法进行排序,直到整个序列都有序;
int partition(std::vector<int>& arr, int low, int high) { int key = arr[low]; while (low < high) { while (low < high && arr[high] >= key) { high--; } std::swap(arr[low], arr[high]); while (low < high && arr[low] <= arr[high]) { low++; } std::swap(arr[low], arr[high]); } printArray(0, arr); return low; } void QuickSort(std::vector<int>& arr, int low, int high) { if (low < high) { int key = partition(arr, low, high); QuickSort(arr, low, key); QuickSort(arr, key+1, high); } } void printArray(size_t idx, const std::vector<int>& arr) { if (arr.empty()) { std::cout << "没有数据" << std::endl; return ; } std::cout << "第" << idx + 1 << "趟:"; for (int i = 0; i < arr.size(); i++) { std::cout << arr[i] << " "; } std::cout << std::endl; }
堆排序
基本思想:首先创建最小堆,在取出堆顶的元素之后进行调整堆,将对堆顶移到数组后面从而实现删除的意思,使其依旧是一个最小堆,直到堆中的元素都取完。
void buidlHeap(std::vector<int>& arr) { int len = arr.size(); // 这里根据父亲结点(最多为数组一半的位置)进行调整 for (int idx = len/2; idx >= 0; idx--) { adjustHeap(arr, idx, len); } } // heapsize是用来控制堆的大小 void adjustHeap(std::vector<int>& arr, int idx, int heapsize) { int left_idx = idx * 2 + 1, right_idx = left_idx+1; int min_idx = idx; // 找结点idx中左子结点和右子结点较小的 if (left_idx < heapsize && arr[idx] > arr[left_idx]) { min_idx = left_idx; } if (right_idx < heapsize && arr[min_idx] > arr[right_idx]) { min_idx = right_idx; } if (min_idx != idx) { std::swap(arr[min_idx], arr[idx]); adjustHeap(arr, min_idx, heapsize); } } void HeapSort(std::vector<int>& arr) { buidlHeap(arr); printArray(0, arr); int len = arr.size(); // 每次取出堆顶后,把堆顶置换到后面,通过heapsize删除该元素 for (int i = len-1; i >= 0; i--) { std::cout << arr[0] << std::endl; std::swap(arr[0], arr[i]); adjustHeap(arr, 0, i); } }
打印数组
void printArray(size_t idx, const std::vector<int>& arr) { if (arr.empty()) { std::cout << "没有数据" << std::endl; return ; } std::cout << "第" << idx + 1 << "趟:"; for (int i = 0; i < arr.size(); i++) { std::cout << arr[i] << " "; } std::cout << std::endl; }
比较
相关推荐
shawsun 2020-07-04
小海 2020-06-25
数据与算法之美 2020-05-27
randy0 2020-11-17
lixiaotao 2020-10-07
美丽的泡沫 2020-09-08
nongfusanquan0 2020-08-18
hang0 2020-08-16
earthhouge 2020-08-15
算法改变人生 2020-07-28
troysps 2020-07-19
Broadview 2020-07-19
chenfei0 2020-07-18
风吹夏天 2020-07-07
yangjingdong00 2020-07-05
数据与算法之美 2020-07-05