网站的开发建设要做什么,后端需要学什么,私人ftp服务器,宁夏百度seo排序算法汇总
这篇文章说明下排序算法#xff0c;直接开始。
1.冒泡排序
最简单直观的排序算法了#xff0c;新手入门的第一个排序算法#xff0c;也非常直观#xff0c;最大的数字像泡泡一样一个个的“冒”到数组的最后面。
算法思想#xff1a;反复遍历要排序的序列…排序算法汇总
这篇文章说明下排序算法直接开始。
1.冒泡排序
最简单直观的排序算法了新手入门的第一个排序算法也非常直观最大的数字像泡泡一样一个个的“冒”到数组的最后面。
算法思想反复遍历要排序的序列每次比较相邻的两个元素如果顺序不正确就交换它们。这样每次遍历都会将最大的元素放到末尾。
排序的时间复杂度O(n²)如果设置标志为如果发生数据交换flag1默认为0复杂度为O(n)因为是原地排序基本不用。
void bubble_sort(vectorint nums) {int n nums.size();for (int i 0; i n-1; i) {for (int j 0; j n-i-1; j) {if (nums[j] nums[j1]) {swap(nums[j], nums[j1]);}}}
}2.选择排序
算法思想每次从未排序的部分选择最小的元素放到已排序部分的末尾重复这个过程。时间复杂度O(n²)无论怎样都是O(n²)空间复杂度O(1)基本不用。
void selectionSort(std::vectorint arr) {int n arr.size();for (int i 0; i n - 1; i) {int minIndex i; // 假设当前元素为最小值的索引for (int j i 1; j n; j) { // 在未排序部分查找最小值if (arr[j] arr[minIndex]) {minIndex j; // 更新最小值索引}}// 将找到的最小值与当前元素交换if (minIndex ! i) {std::swap(arr[i], arr[minIndex]);}}
}3.插入排序
算法思想将数组分为已排序和未排序部分从未排序部分取元素在已排序部分找到合适的位置插入。时间复杂度O(n²)空间复杂度O(1)。
void insertionSort(std::vectorint arr) {int n arr.size(); // 获取数组的大小for (int i 1; i n; i) { // 从第二个元素开始int key arr[i]; // 当前待插入的元素int j i - 1;// 在已排序部分中找到合适的位置插入 keywhile (j 0 arr[j] key) {arr[j 1] arr[j]; // 向后移动元素j--; // 移动到前一个元素}arr[j 1] key; // 插入 key}
}4.快速排序
算法思想选择一个基准元素将数组划分为比基准小的部分和比基准大的部分递归地对这两个部分排序。时间复杂度O(n log n)空间复杂度O(log n) 。
void fastSort(vectorint nums, int low, int high) {if (low high)return;int pivot nums[high], i low;for (int j low; j high; j) {if (nums[j] pivot) {if (i ! j)swap(nums[i], nums[j]);i;}}swap(nums[i], nums[high]);fastSort(nums, low, i - 1);fastSort(nums, i 1, high);
}5.归并排序
算法思想采用分治法将数组分成两个子数组分别排序再将它们合并成一个有序数组。时间复杂度O(n log n)空间复杂度O(n) 。
//递归版本
void mergeSort(vectorint nums, int left, int right) {if (left right)return;int mid left (right - left)/2;mergeSort(nums, left, mid);mergeSort(nums, mid 1, right);vectorint tmp(right - left 1);int count 0;int i left, j mid 1;while (i mid j right) {if (nums[i] nums[j]) {tmp[count] nums[i];} else {tmp[count] nums[j];}}while (i mid) {tmp[count] nums[i];}while (j right) {tmp[count] nums[j];}for (int p 0; p tmp.size(); p) {nums[left p] tmp[p];}
}//迭代版本
void mergeSortIterative(std::vectorint nums) {int n nums.size();for (int currentsize 1; currentsize n - 1; currentsize * 2)for (int left 0; left n - 1; left 2 * currentsize) {int mid min(left currentsize - 1, n - 1);int right min(left 2 * currentsize - 1, n - 1);int n1 mid - left 1;int n2 right - mid;vectorint leftArr(n1), rightArr(n2);for (int i 0; i n1; i)leftArr[i] nums[left i];for (int i 0; i n2; i)rightArr[i] nums[mid i 1];int i 0, j 0, k left;while (i n1 j n2) {if (leftArr[i] rightArr[j]) {nums[k] leftArr[i];} else {nums[k] rightArr[j];}k;}while (i n1) {nums[k] leftArr[i];}while (j n2) {nums[k] rightArr[j];}}
}6.堆排序
算法思想使用二叉堆这种数据结构先构建最大堆或最小堆然后依次将堆顶元素移除重新调整堆。时间复杂度O(n log n)空间复杂度O(1)不用递归的话
void heapify(vectorint nums, int n, int i) {if(in)return;int largest i;int left 2 * i 1, right 2 * i 2;if (left n nums[left] nums[largest])largest left;if (right n nums[right] nums[largest])largest right;if (largest ! i) {swap(nums[i], nums[largest]);heapify(nums, n, largest);}}void heapSort(vectorint nums) {int n nums.size();for(int in/2-1;i0;i--) {heapify(nums,n,i);}for(int in-1;i0;i--) {swap(nums[0],nums[i]);heapify(nums,i,0);}
}排序算法的总结表格
排序算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性冒泡排序O(n)O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n)O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定
7.文末解释一下算法时间复杂中的log n有些人不理解
快速排序的平均时间复杂度为 O(n log n)是因为它在理想情况下可以将问题规模递归减半而每次递归的划分过程需要 O(n) 的操作。通过递归树的结构我们可以直观理解为什么时间复杂度为 O(n log n)。
1. 每一层的操作需要 O(n) 的时间
在快速排序的每一层递归中主要的开销来自于划分partition操作。这个操作的过程是选取一个基准元素pivot然后从两边扫描数组交换元素使得基准元素的左边都比它小右边都比它大。
无论基准元素选得如何每次划分需要遍历整个数组。因此在每一层递归中划分操作的时间复杂度是 O(n)其中 n 是当前数组的长度。
2. 递归的层数为 log n
在理想情况下快速排序的每次递归都能将数组大致划分为相等的两部分即每次递归之后数组的规模缩小为原来的 1/2。这个过程相当于将问题规模递归地减半直到数组大小缩减到 1。
因此总共需要递归 log n 层递归树的高度这里的 log n 表示递归树的层数也就是快速排序的递归深度。
3. 总时间复杂度为 O(n log n)
每层的时间复杂度在递归树的每一层需要 O(n) 的时间来对数组进行划分。递归树的层数递归树的高度为 log n表示总共要递归 log n 层。
因此整个快速排序的总时间复杂度就是 总时间每层所需的时间×递归的层数O(n)×O(logn)O(nlogn)
递归树示意
可以将快速排序的递归过程看作是一个递归树每一层是对整个数组的遍历每一层都需要 O(n) 的时间来进行划分。递归树的层数是 log n总共 log n 层。
举例说明递归树结构 O(n)----------------| |O(n/2) O(n/2)------- -------| | | |O(n/4) O(n/4) O(n/4) O(n/4)----------------------------... (共 log n 层)4. 平均时间复杂度为 O(n log n) 的解释
在理想情况下每次划分都能把数组平分成两半快速排序的递归树的高度为 log n。每一层递归处理的元素总数为 n即整个数组的长度由于有 log n 层所以整个快速排序的总时间复杂度为 O(n log n)。
5. 总结
每一层快速排序的递归操作需要 O(n) 的时间来进行划分。总共有 log n 层递归即递归树的高度为 log n。因此快速排序的平均时间复杂度是 O(n log n)。
不过需要注意在最坏情况下当每次划分都极不平衡如数组是完全有序的递归树的高度会退化为 n此时时间复杂度为 O(n^2)。通过随机化选择基准元素可以有效避免这种最坏情况的发生从而保证平均时间复杂度为 O(n log n)。
