- 1. 算法基本知识
- 2. 十大排序一图总览
- 2.1 十大排序中的稳定排序
- 2.2 十大排序中的非稳定排序
- 3. 冒泡排序
- 4. 选择排序
- 5. 插入排序
- 6. 快速排序
- 7. 希尔排序
- 8. 归并排序
- 8.1 递归实现
- 8.2 迭代实现
- 9. 堆排序
- 10. 计数排序
- 10.1 自然数的排序（不包含负数）
- 10.2 整数的排序（包含负数）
- 11. 基数排序
1.1 稳定排序
如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
1.2 非稳定排序
如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
1.3 原地排序
原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储
空间进行比较和交换的数据排序。
1.4 非原地排序
需要利用额外的数组来辅助排序。
1.5 时间复杂度
一个算法执行所消耗的时间。
1.6 空间复杂度
运行完一个算法所需的内存大小
冒泡排序（bubble_sort） — O(n2)
插入排序 （insert_sort）— O(n2)
归并排序 （merge_sort）— O(n log n)
计数排序（counting_sort）— O(n + k)(k为整数的范围)
面试考察中一般问快排，选择，希尔，堆这几种非稳定排序
选择排序 （select_sort）— O(n2)
希尔排序 （shell_sort）— O(n log n)
堆排序 （heap_sort）— O(n log n)
快速排序 （quick_sort）— O(n log n)
时间复杂度：O(n²)
空间复杂度：O(1)
稳定排序
冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。
步骤（从小到大）：
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
#include4. 选择排序#include using namespace std; void bubble_sort(vector &vec) { int len = vec.size(); for(int i= 0; i < len-1; i++) //len个数，只需比较len-1对 { for(int j = 0; j < len - i - 1; j++) //后面已经是确定的数，只需比较前面的 { if(vec[j] > vec [j+1]) swap(vec[j],vec[j+1]); } } } int main() { int num; cin >> num; vector vec; //初始化一个size为0的vec数组 //vector vec(num);vec数组里面的num个数全部初始化为0 int temp; while(num--) { cin >> temp; vec.push_back(temp); //在vec数组的末尾添加数字temp } bubble_sort(vec); //for(auto i : vec) //{ // cout << i << " "; //} for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
时间复杂度：O(n²)
空间复杂度：O(1)
非稳定排序
选择排序（从小到大）是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个 元素不用选择了，因为只剩下它一个最大的元素了。
举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和最小的2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
步骤（从小到大）：
- 在未排序序列中找到最小元素（实际是找最小元素的下标，然后进行交换），存放到排序序列的起始位置
- 从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾
- 以此类推，直到所有元素均排序完毕
#include5. 插入排序#include using namespace std; void select_sort(vector &vec) { int len = vec.size(); int minIndex; //定义一个下标 for(int i = 0; i < len; ++i) { minIndex = i; //将第一个数的下标赋给minIndex for(int j = i + 1;j < len; ++j) { if(vec[j] < vec[minIndex]) { minIndex = j; } swap(vec[i],vec[minIndex]); //找到最小数之后再将最小数与第一个数进行交换（在循环完一次之后再交换） } } } int main() { int num; cin >> num; vector vec; int temp; for(int i= 0; i < num; i++) { cin >> temp; vec.push_back(temp); } select_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
时间复杂度：O(n²)
空间复杂度：O(1)
稳定排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。
当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
步骤（从小到大）：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果新元素小于已经排好的元素的最后一个，将该元素移到下一位置
- 重复步骤3，将所有大于新元素的已排序元素向后移动一位，直到找到小于新元素的已排序的元素的位置
- 将新元素插入到该位置的后一位
- 重复步骤2~5
#include6. 快速排序#include using namespace std; void insert_sort(vector &vec) { int len = vec.size(); for(int i = 1; i < len ; ++i) { int temp = vec[i]; //将需要的排列的数放到temp，那需要排列的数的位置就已经空了，然后能够使前面的大于这个数的有序序列进行后移，方便这个数插入 int j; for(j = i - 1; j >= 0 && vec[j] > temp; --j) //从当前元素的前一个元素开始，从后往前扫描已经排序好的序列（--j） { vec[j + 1] = vec[j]; //把大于temp的数全部后移 } vec[j + 1] = temp; //将之前的需要排列的这个数插入到相应的位置。之前已经执行了--j，所以--j这个位置的数是小于需要排序的这个数，将这个数放在--j之后的j+1的位置。 } } int main() { int num; cin >> num; vector vec; int tempNum; for(int i = 0; i < num ; ++i) { cin >> tempNum; vec.push_back(tempNum); } insert_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
平均时间复杂度：O(nlogn)
空间复杂度：O(logn)
最差的情况就是每一次取到的元素就是数组中最小/最大的，退化到冒泡排序，最差的时间复杂度：O(n²)，空间复杂度：O(n)
非稳定排序
- 选取第一个数为基准
- 将比基准小的数交换到前面，比基准大的数交换到后面
- 对左右区间重复第二步，直到各区间只有一个数
#include7. 希尔排序#include using namespace std; void quick_sort(vector &vec,int left,int right) { if(left >= right) return; int low = left; int high = right; int key = vec[low]; while(low < high) { while(low < high && vec[high] >= key) high--; if(low < high) vec[low++] = vec[high]; while(low < high && vec[low] < key) low++; if(low < high) vec[high--] = vec[low]; } vec[high] = key; quick_sort(vec,left,high - 1); quick_sort(vec,high + 1,right); } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; ++i) { cin >> temp; vec.push_back(temp); } quick_sort(vec,0,num - 1); for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
最优时间复杂度：O(n^(1.3)) （元素已经排序好顺序）
最优时间复杂度：O(n²)
空间复杂度：O(1)
非稳定排序
希尔排序可以说是插入排序的一种变种。希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
讲解比较好的视频：https://www.bilibili.com/video/BV1mE411M7SH?share_source=copy_web
#include8. 归并排序#include using namespace std; void shell_sort(vector &vec) { int len = vec.size(); for(int gap = len/2; gap > 0; gap /= 2) { // 对每一躺进行插入排序 for(int i = gap; i < len; ++i) //对于每趟的第一个元素是有序的，从第二个元素开始，所以是i = gap { int tempNum = vec[i]; //将第二个数存到tempNum中，如果第一个数大于第一个数，便于将第一个数后移到第二个数的位置 int j; //对一趟中的数组进行排序，注意数字之间的间隔是gap for(j = i - gap; j >= 0 && vec[j] > tempNum; j -= gap) //如果第一个数大于第二个数,则将第一个数后移到第二个数的位置。j = j - gap，对这趟的数从后往前扫描 { vec[j + gap] = vec[j]; } vec[j + gap] = tempNum;//上面的循环已经执行了j = j - gap不满足条件，所以是将tempNum放到j + gap的位置 } } } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; ++i) { cin >> temp; vec.push_back(temp); } shell_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
时间复杂度：O(nlog(n))
空间复杂度：O(n)
稳定排序
递归的思想实际上是从上往下“递”，再从下往上“归”。
通过递归的方式将一个大的数组一直分割，分割到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 … 直到全部小的数组合并起来。
讲解比较好的视频：https://www.bilibili.com/video/BV1Pt4y197VZ?share_source=copy_web
#include8.2 迭代实现#include using namespace std; void merge_sort(vector &vec, vector &vecTemp, int left, int right) { //1.划分 if(left >= right) //递归终止的条件 return; int mid = left + (right-left)/2; int start1 = left; int end1 = mid; int start2 = mid + 1; int end2 = right; merge_sort(vec,vecTemp,start1,end1); //递归划分左半区 merge_sort(vec,vecTemp,start2,end2); //递归划分右半区 //2.合并 int index = left; //创建临时数组vecTemp的下标 while(start1 <= end1 && start2 <= end2) { if(vec[start1] < vec[start2]) //左半区的第一个元素小于右半区的第一个元素 { vecTemp[index++] = vec[start1++]; //将小的数放到临时数组里面，并将左半区和临时数组的指针右移 } else //左半区的第一个元素小于右半区的第一个元素 { vecTemp[index++] = vec[start2++]; //将小的数放到临时数组里面，并将右半区和临时数组的指针右移 } } while(start1 <= end1) { vecTemp[index++] = vec[start1++]; //合并左半区剩余的元素 } while(start2 <= end2) { vecTemp[index++] = vec[start2++]; //合并右半区剩余的元素 } while(left <= right) { vec[left] = vecTemp[left]; //将临时数组中的元素复制回原来的数组 left++; } //for(index = left; index <= right; ++index) //{ // vec[index] = vecTemp[index]; //} } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; ++i) { cin >> temp; vec.push_back(temp); } vector vecTemp(num); //vector vecTemp; 不能这样写，需要确定数组的个数，否则出现错误：Segmentation fault，内存非法访问 merge_sort(vec,vecTemp,0,num-1); for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
迭代的过程就是化成一个个小的排序问题，再合并到一起
#include9. 堆排序#include using namespace std; void merge_sort(vector &vec) { int len = vec.size(); vector vecTemp(len); //创建临时数组 for(int seg = 1; seg < len; seg += seg) //指定步长，从开始的1，到2,4,6...到len-1; //对不同步长的数开始比较排序，最开始是对步长为1的两个数排序，下来是步长为2的4个数，步长为4的8个数... { //对同一步长的不同数组开始排序 for(int start = 0; start < len; start += seg + seg) { int index = start; //定义临时数组的下标 int start1 = start; int end1 = min(start + seg,len); //下标不能超过len int start2 = min(start + seg,len); //下标不能超过len int end2 = min(start + seg + seg,len);//在合并的过程中其end2可能会大于len，比如序列的个数是奇数，在第一次合并end2就会大于len,再比如序列的个数是偶数为10，在第二次合并end2就会大于10。也就是说当待排序的数组的个数不为2的幂次方时，在合并的过程当中就会出现end2大于len的情况。 while(start1 < end1 && start2 < end2) { if(vec[start1] < vec[start2]) vecTemp[index++] = vec[start1++]; else vecTemp[index++] = vec[start2++]; } //while(start1 < end1 && start2 < end2) //{ // vecTemp[index++] = vec[start1] < vec[start2] ? vec[start1++] : vec[start2++]; //} while(start1 < end1) vecTemp[index++] = vec[start1++]; while(start2 < end2) vecTemp[index++] = vec[start2++]; } swap(vec,vecTemp); } } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; i++) { cin >> temp; vec.push_back(temp); } merge_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); ++it) { cout << *it << " "; } cout << endl; return 0; }
时间复杂度：O(nlog(n))
空间复杂度：O(1)
非稳定排序
基本思想：先把数组构造成一个大顶堆，构造大顶堆就是维护堆的性质，使得父节点大于左右孩子节点，从最后一个父节点（n/2 - 1）开始，递归实现，然后把堆顶和数组的最后一个数进行交换，这样就把最大的值放到数组的最后面。把长度为n - 1的数组再进行构造大顶堆，把最大数放到堆顶，与倒数第二个数进行交换，这样就把第二大值放到了倒数第二的位置。以此类推，完成数组的排序。
大顶堆适用于升序排列
小顶堆适用于降序排列
讲解比较好的视频：https://www.bilibili.com/video/BV1fp4y1D7cj?share_source=copy_web
#include10. 计数排序#include using namespace std; void heapify(vector &vec, int n, int i) { int largest = i; //假设i下标的元素是最大的，相对于左孩子和右孩子 int lson = 2 * i + 1; //左孩子下标 int rson = 2 * i + 2; //右孩子下标 //从节点和它的左右孩子中找出最大的数 if(lson < n && vec[largest] < vec[lson]) largest = lson; if(rson < n && vec[largest] < vec[rson]) largest = rson; if(largest != i) //i下标的数相对于左右孩子不是最大的，需要交换 { swap(vec[largest], vec[i]); heapify(vec, n, largest); //递归调用，维护其他节点堆的性质 //当前largest在lson或rson的位置，交换完最大数之后，较小数的位置为largest } } void heapify_build(vector &vec, int n) { //建堆 int i; for(i = n / 2 - 1; i >= 0; i--) { heapify(vec, n, i); } //排序 for(i = n - 1; i > 0; i--) { swap(vec[i], vec[0]); heapify(vec, i, 0); } } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; i++) { cin >> temp; vec.push_back(temp); } heapify_build(vec, num); for(vector ::iterator it = vec.begin(); it != vec.end(); it++) { cout << *it << " "; } cout << endl; return 0; }
时间复杂度为Ο(n+k)（其中k是整数的范围）
空间复杂度为Ο(n+k)
稳定排序
计数排序是一种线性排序算法，不需要进行比较。
对一定范围内的整数排序时，计数排序快于任何比较排序算法
基本思想就是：需要创建一个临时数组来进行对待排序数组中的元素进行计数，这个临时数组的下标就是待排序数组中的所有元素减去数组中的最小值，这样就不会出现数组的下标出现负数的情况。然后将计数完之后的数组进行累积统计，累积统计就是每一项和前一项相加，目的是为了以怎样的方式反向填充数组，再建立一个数组，将待排序数组的元素放入到数组中，每放一个数，临时数组的下标为该数的数就减1。
10.1 自然数的排序（不包含负数）如果代码不理解可以看一下这个视频：https://www.bilibili.com/video/BV1KU4y1M7VY?share_source=copy_web
#include10.2 整数的排序（包含负数）#include using namespace std; void counting_sort(vector &vec) { int len = vec.size(); //寻找最大元素 int maxNum = vec[0]; for(int i = 1; i < len; i++) //上面定义了下标0，从下标1开始寻找。 { if(vec[i] > maxNum) maxNum = vec[i]; } //建立一个(最大元素+1)的数组 int lenCount = maxNum + 1; vector vecCount(lenCount); //计数 for(int i = 0; i < len; i++) { vecCount[vec[i]]++; } //统计计数的累计值 for(int i = 1; i < lenCount; i++) //从第二个数开始，所以是i=1 { vecCount[i] += vecCount[i - 1]; } //创建数组保存排序的结果,注意数组长度 vector vecOutput(len); //将元素放到正确的位置上 for(int i = 0; i < len; i++) { vecOutput[vecCount[vec[i]] - 1] = vec[i]; //注意不是vecCount[i] - 1，i是从0到len vecCount[vec[i]]--; } //将结果复制回原数组 swap(vec, vecOutput); //第二种将结果复制回原数组方法 //while(len--) //{ // vec[len] = vecOutput[len]; //} //第三种将结果复制回原数组方法 //for(int i = 0; i < len; i++) //{ // vec[i] = vecOutput[i]; //} } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; i++) { cin >> temp; vec.push_back(temp); } counting_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); it++) { cout << *it << " "; } cout << endl; return 0; }
#include11. 基数排序#include using namespace std; void counting_sort(vector &vec) { int len = vec.size(); //寻找最大元素和最小元素 int maxNum = vec[0]; int minNum = vec[0]; for(int i = 1; i < len; i++) //上面定义了下标0，从下标1开始寻找。 { if(vec[i] > maxNum) maxNum = vec[i]; if(vec[i] < minNum) minNum = vec[i]; } //建立一个(最大元素 - 最小元素 + 1)的数组 int lenCount = maxNum - minNum + 1; vector vecCount(lenCount); //计数 for(int i = 0; i < len; i++) { vecCount[vec[i] - minNum]++; //数组的下标不能是负数，所以原数组的数字映射现数组的下标可以这样表示 } //统计计数的累计值 for(int i = 1; i < lenCount; i++) //从第二个数开始，所以是i=1 { vecCount[i] += vecCount[i - 1]; } //创建数组保存排序的结果,注意数组长度 vector vecOutput(len); //将元素放到正确的位置上 for(int i = 0; i < len; i++) { vecOutput[vecCount[vec[i] - minNum] - 1] = vec[i]; vecCount[vec[i] - minNum]--; } //将结果复制回原数组 swap(vec, vecOutput); //第二种将结果复制回原数组方法 //while(len--) //{ // vec[len] = vecOutput[len]; //} //第三种将结果复制回原数组方法 //for(int i = 0; i < len; i++) //{ // vec[i] = vecOutput[i]; //} } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; i++) { cin >> temp; vec.push_back(temp); } counting_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); it++) { cout << *it << " "; } cout << endl; return 0; }
时间复杂度：O(n * k) (k为最大数的位数的个数)
空间复杂度：O(n * k)
算法思想：关键字排序，对于数组中的每一个元素，先比较每一个元素的个位数，按个位数的大小将数组中的每一个元素从小到大排列，再比较十位数，按十位数的大小将每一个元素从小到大排列，以此类推，百位、千位…
若不理解可以看一下这个视频：https://www.bilibili.com/video/BV1xz411i7Eb?share_source=copy_web
#include#include using namespace std; void radix_sort(vector &vec) { int len = vec.size(); //寻找数组中的最大数 int maxNum = vec[0]; for(int i = 1; i < len; i++) { if(vec[i] > maxNum) maxNum = vec[i]; } //统计位数 int base = 1; while(maxNum / base > 0) { //计数 vector buckets(10); //定义10个桶i:0~9 for(int i = 0; i < len; i++) { buckets[vec[i] / base % 10]++; //计数每个桶装入的元素数。注意：vec[i] / base % 10 是桶的下标 } //统计 for(int i = 1; i < 10; i++) { buckets[i] += buckets[i - 1]; } //存放 vector vecTemp(len); //计数、统计和存放和之前的计数排序有点类似，方法是一样的 for(int i = len - 1; i >= 0; i--) //i = len - 1,不是i = len;一定要从后往前存放，比如原数组有3,12,3，如果从桶中前往后存放会影响两个3的前后顺序，在收集的时候出现不稳定排序 { vecTemp[buckets[vec[i] / base % 10 ] - 1] = vec[i]; buckets[vec[i] / base % 10]--; } //将临时数组中的数放回原数组 swap(vec, vecTemp); base *= 10; } } int main() { int num; cin >> num; vector vec; int temp; for(int i = 0; i < num; i++) { cin >> temp; vec.push_back(temp); } radix_sort(vec); for(vector ::iterator it = vec.begin(); it != vec.end(); it++) { cout << *it << " "; } cout << endl; return 0; }
