数据结构_排序⑧快速排序

快速排序 hoare版本 挖坑法 前后指针版本 空间: 空间可以复用 最大的递归调用链–> logN 时间: N * logN 序列有序 时间效率最差–> N^2 快速排序 void QuickSort(int* a, int left, int right){ if(left >…

数据结构_排序⑦冒泡排序

⑦# 冒泡排序 时间复杂度:O(N^2) 空间复杂度:O(1) 稳定性:稳定 void Swap(int* x, int* y){ int tmp = *x; *x = *y; *y = tmp; } void BubbleSort(int* a, int n){ int cur, bound; f…

数据结构_排序⑥归并排序

归并排序 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。 时间: N * logN 空间: N + logN ~ N 稳定性: 稳定 void _MergeSort(int*a, int left, int right, int* tmp){ //区间只剩一…

数据结构_排序⑤计数排序

计数排序 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。 时间复杂度:O(MAX(N,范围)) 空间复杂度:O(范围) 稳定性:稳定 void CountSort(int* a, int n){ //范围: min ~ max int min = a[0], max = a[0]; i…

数据结构_排序④堆排序

堆排序 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是 通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。 时间复杂度:O( N*logN) 空间复杂度: O(1) 稳定性: 不稳定 void Swap(int* x, int*…

数据结构_排序③选择排序

三.选择排序 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 可以稳定 void Swap(int* x, int* y){ int tmp = *x; *x = *y; *y …

数据结构_排序②希尔排序

希尔排序 先选定一个整数,把待排序文件中所有元素分成多个组,所有距离为gap的元素及两者间的元素分在同一组内,并对每一组内的元素进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有元素在统一组内排好序 //时间复杂度: O(N^1.3 ~ N^2) //空间复杂度: O(1); 稳定性:…

数据结构_排序①插入排序

插入排序: 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。 时间复杂度: O(N^2) 空间复杂度: O(1) 稳定性: 稳定 适合场景: 接近有序的序列, 时间复杂度趋近于O(N)对于有序的序列, 时间复杂度O(N) void Ins…