做团购网站需要多少钱,绍兴seo包年排行榜,wordpress ajax json,汽车商城网站模板一、常用排序说明 当涉及排序算法时#xff0c;理解每个算法的工作原理、时间复杂度和空间复杂度是至关重要的。下面对常用排序算法进行详细说明#xff1a; 1、冒泡排序#xff08;Bubble Sort#xff09;#xff1a; 工作原理#xff1a;比较相邻的元素并交换理解每个算法的工作原理、时间复杂度和空间复杂度是至关重要的。下面对常用排序算法进行详细说明 1、冒泡排序Bubble Sort 工作原理比较相邻的元素并交换每一轮将最大或最小的元素移动到数组末尾或开头。 时间复杂度平均情况和最坏情况均为 O(n^2)。 空间复杂度O(1)原地排序不需要额外空间。 适用场景适用于小规模数据集对稳定性要求高的场景或者作为教学和理解排序算法的基础。 2、选择排序Selection Sort 工作原理每一轮选择最小或最大的元素放在已排序序列的末尾或开头。 时间复杂度平均情况和最坏情况均为 O(n^2)。 空间复杂度O(1)原地排序不需要额外空间。 适用场景适用于小规模数据集简单易实现但性能较差。对稳定性要求不高的场景。 3、插入排序Insertion Sort 工作原理将未排序序列中的元素逐个插入到已排序序列中的适当位置。 时间复杂度平均情况和最坏情况均为 O(n^2)。 空间复杂度O(1)原地排序不需要额外空间。 适用场景适用于小规模或基本有序的数据集对稳定性要求高的场景用于改进其他排序算法的一部分。 4、希尔排序Shell Sort 工作原理是插入排序的改进版通过比较距离较远的元素进行交换最终使数据基本有序然后再使用插入排序。 时间复杂度取决于增量序列的选择在实践中介于 O(n log^2 n) 和 O(n^2) 之间。 空间复杂度O(1)原地排序不需要额外空间。 适用场景适用于小规模或基本有序的数据集对稳定性要求高的场景用于改进其他排序算法的一部分。 5、归并排序Merge Sort 工作原理采用分治法将数组分成两半分别排序然后合并两个有序数组。 时间复杂度平均情况和最坏情况均为 O(n log n)。 空间复杂度O(n)需要额外的内存来存储临时数组。 适用场景适用于小规模或基本有序的数据集对稳定性要求高的场景用于改进其他排序算法的一部分。 6、快速排序Quick Sort 工作原理采用分治法选取一个基准值将小于基准值的放在左边大于基准值的放在右边然后递归地对左右两部分进行排序。 时间复杂度平均情况为 O(n log n)最坏情况为 O(n^2)。 空间复杂度取决于实现方式通常为 O(log n)。 适用场景适用于大规模数据集性能优秀且易于实现。常用于实际生产环境中的排序需求。 7、堆排序Heap Sort 工作原理利用堆的性质最大堆或最小堆将待排序数组构建成堆然后每次取出堆顶元素重新调整堆直至完成排序。 时间复杂度平均情况和最坏情况均为 O(n log n)。 空间复杂度O(1)原地排序不需要额外空间。 适用场景适用于大规模数据集性能稳定且不受输入数据分布情况影响。适合内存受限的情况下进行排序。 8、计数排序Counting Sort 工作原理统计待排序数组中每个元素出现的次数然后根据元素的值将其放到正确的位置。 时间复杂度平均情况和最坏情况均为 O(n k)其中 k 是非负整数的最大值。 空间复杂度O(n k)需要额外空间来存储计数数组和输出数组。 适用场景适用于输入数据的范围相对较小但数量较大的情况下可以快速排序。对数字的频率进行统计。 9、桶排序Bucket Sort 工作原理将待排序数据分到有限数量的桶里每个桶再分别进行排序最后合并所有桶的结果。 时间复杂度平均情况为 O(n k)最坏情况为 O(n^2)。 空间复杂度O(n k)需要额外空间来存储计数数组和输出数组。 适用场景适用于数据均匀分布在一个范围内的情况下将数据分到多个桶中然后对每个桶单独进行排序。 10、基数排序Radix Sort 工作原理根据数字位进行排序先按个位排序再按十位排序依次类推直到最高位排序完成。 时间复杂度平均情况和最坏情况均为 O(d * (n k))其中 d 是数字位数k 是基数如 10 进制中的 10。 空间复杂度O(n k)需要额外空间来存储计数数组和输出数组。 适用场景适用于对数字进行排序的场景通过按位进行排序每次排序根据数字位数来确定效率高且稳定。 二、时间复杂度说明 O(1)常数时间复杂度。无论输入规模的大小如何算法的执行时间都是固定的。例如访问数组中的一个元素计算数组的长度等。无论数组中有多少个元素时间都是恒定的。 O(log n)对数时间复杂度。算法的执行时间与输入规模的对数成正比。典型的例子是二分查找算法。在一个有序数组中查找一个元素时每次都将搜索空间减半因此时间复杂度为对数级别。 O(n)线性时间复杂度。算法的执行时间与输入规模成正比呈线性增长。例如遍历数组或链表中的所有元素。如果一个数组有 n 个元素那么对每个元素的访问将花费 O(n) 的时间。 O(n log n)线性对数时间复杂度。典型的例子是快速排序和归并排序等基于比较的排序算法。这些算法的执行时间与输入规模的对数乘以线性成正比。 O(n^2)平方时间复杂度。算法的执行时间与输入规模的平方成正比。例如嵌套循环的排序算法如冒泡排序、选择排序每个元素都需要与其他元素比较。 O(2^n)指数时间复杂度。通常出现在递归算法中每次递归都会产生指数级别的子问题。例如求解所有可能的子集或排列问题。 O(n!)阶乘时间复杂度。通常出现在全排列等组合问题中需要计算所有可能的排列。例如求解 n 个元素的所有排列可能性的问题。
三、空间复杂度说明 O(1)常数空间复杂度。算法的额外空间使用是一个固定的常数与输入规模无关。例如原地排序算法如冒泡排序、选择排序不需要额外的空间。 O(log n)对数空间复杂度。算法的额外空间使用与输入规模的对数成正比。例如递归算法每次调用都会消耗对数级别的栈空间。二分搜索的递归版本就是一个典型的例子。 O(n)线性空间复杂度。算法的额外空间使用与输入规模成正比呈线性增长。例如需要一个与输入规模相同大小的数组来存储数据或者使用一个辅助数组来进行排序。 O(n^2)平方空间复杂度。算法的额外空间使用与输入规模的平方成正比。例如使用一个二维数组来存储所有可能的组合情况。 O(2^n)指数空间复杂度。算法的额外空间使用与输入规模的指数成正比。通常出现在递归的指数增长情况下例如子集生成问题。 O(n!)阶乘空间复杂度。算法的额外空间使用与输入规模的阶乘成正比。通常出现在全排列等组合问题中需要存储所有可能的排列。 四、代码样例
(一) 冒泡排序Bubble Sort
#include iostream
using namespace std;void bubbleSort(int arr[], int n) {for (int i 0; i n-1; i) {for (int j 0; j n-i-1; j) {if (arr[j] arr[j1]) {swap(arr[j], arr[j1]);}}}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);cout Sorted array: ;for (int i 0; i n; i) {cout arr[i] ;}cout endl;return 0;
}(二) 选择排序Selection Sort
#include iostream
using namespace std;void selectionSort(int arr[], int n) {for (int i 0; i n-1; i) {int min_idx i;for (int j i1; j n; j) {if (arr[j] arr[min_idx]) {min_idx j;}}swap(arr[i], arr[min_idx]);}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);selectionSort(arr, n);cout Sorted array: ;for (int i 0; i n; i) {cout arr[i] ;}cout endl;return 0;
}(三) 插入排序Insertion Sort
#include iostream
using namespace std;void insertionSort(int arr[], int n) {for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j1] arr[j];j--;}arr[j1] key;}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);insertionSort(arr, n);cout Sorted array: ;for (int i 0; i n; i) {cout arr[i] ;}cout endl;return 0;
}(四) 希尔排序Shell Sort
#include iostream
using namespace std;void shellSort(int arr[], int n) {for (int gap n/2; gap 0; gap / 2) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}int main() {int arr[] {64, 34, 25, 12, 22, 11, 90};int n sizeof(arr) / sizeof(arr[0]);shellSort(arr, n);cout Sorted array: ;for (int i 0; i n; i) {cout arr[i] ;}cout endl;return 0;
}(五) 归并排序Merge Sort
#include iostream
#include vector
using namespace std;void merge(vectorint arr, int l, int m, int r) {int n1 m - l 1;int n2 r - m;vectorint L(n1), R(n2);for (int i 0; i n1; i)L[i] arr[l i];for (int j 0; j n2; j)R[j] arr[m 1 j];int i 0, j 0, k l;while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}while (i n1) {arr[k] L[i];i;k;}while (j n2) {arr[k] R[j];j;k;}
}void mergeSort(vectorint arr, int l, int r) {if (l r) {int m l (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m 1, r);merge(arr, l, m, r);}
}int main() {vectorint arr {64, 34, 25, 12, 22, 11, 90};int n arr.size();mergeSort(arr, 0, n - 1);cout Sorted array: ;for (int i 0; i n; i)cout arr[i] ;cout endl;return 0;
}(六) 快速排序Quick Sort
#include iostream
#include vector
using namespace std;int partition(vectorint arr, int low, int high) {int pivot arr[high];int i low - 1;for (int j low; j high; j) {if (arr[j] pivot) {i;swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return i 1;
}void quickSort(vectorint arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}int main() {vectorint arr {64, 34, 25, 12, 22, 11, 90};int n arr.size();quickSort(arr, 0, n - 1);cout Sorted array: ;for (int i 0; i n; i)cout arr[i] ;cout endl;return 0;
}(七) 堆排序Heap Sort
#include iostream
#include vector
using namespace std;void heapify(vectorint arr, int n, int i) {int largest i;int l 2 * i 1;int r 2 * i 2;if (l n arr[l] arr[largest])largest l;if (r n arr[r] arr[largest])largest r;if (largest ! i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(vectorint arr) {int n arr.size();for (int i n / 2 - 1; i 0; i--)heapify(arr, n, i);for (int i n - 1; i 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}int main() {vectorint arr {64, 34, 25, 12, 22, 11, 90};int n arr.size();heapSort(arr);cout Sorted array: ;for (int i 0; i n; i)cout arr[i] ;cout endl;return 0;
}(八) 计数排序Counting Sort
#include iostream
#include vector
using namespace std;void countingSort(vectorint arr) {int n arr.size();int maxVal *max_element(arr.begin(), arr.end());int minVal *min_element(arr.begin(), arr.end());int range maxVal - minVal 1;vectorint count(range), output(n);for (int i 0; i n; i)count[arr[i] - minVal];for (int i 1; i range; i)count[i] count[i - 1];for (int i n - 1; i 0; i--) {output[count[arr[i] - minVal] - 1] arr[i];count[arr[i] - minVal]--;}for (int i 0; i n; i)arr[i] output[i];
}int main() {vectorint arr {64, 34, 25, 12, 22, 11, 90};countingSort(arr);cout Sorted array: ;for (int i 0; i arr.size(); i)cout arr[i] ;cout endl;return 0;
}(九) 桶排序Bucket Sort
#include iostream
#include vector
#include algorithm
using namespace std;void bucketSort(vectorfloat arr) {int n arr.size();vectorvectorfloat buckets(n);for (int i 0; i n; i) {int bucketIndex n * arr[i];buckets[bucketIndex].push_back(arr[i]);}for (int i 0; i n; i)sort(buckets[i].begin(), buckets[i].end());int index 0;for (int i 0; i n; i) {for (float num : buckets[i]) {arr[index] num;}}
}int main() {vectorfloat arr {0.64, 0.34, 0.25, 0.12, 0.22, 0.11, 0.90};bucketSort(arr);cout Sorted array: ;for (int i 0; i arr.size(); i)cout arr[i] ;cout endl;return 0;
}(十) 基数排序Radix Sort
#include iostream
#include vector
#include algorithm
using namespace std;int getMax(vectorint arr) {int maxVal arr[0];for (int i 1; i arr.size(); i) {if (arr[i] maxVal)maxVal arr[i];}return maxVal;
}void countingSort(vectorint arr, int exp) {int n arr.size();vectorint output(n), count(10);for (int i 0; i n; i)count[(arr[i] / exp) % 10];for (int i 1; i 10; i)count[i] count[i - 1];for (int i n - 1; i 0; i--) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}for (int i 0; i n; i)arr[i] output[i];
}void radixSort(vectorint arr) {int maxVal getMax(arr);for (int exp 1; maxVal / exp 0; exp * 10)countingSort(arr, exp);
}int main() {vectorint arr {64, 34, 25, 12, 22, 11, 90};radixSort(arr);cout Sorted array: ;for (int i 0; i arr.size(); i)cout arr[i] ;cout endl;return 0;
}
