做网站手机版,科技类网站怎么做,电商网站开发python,网站淘宝客 难做目录
一. 冒泡排序
基本思想
代码实现
时间和空间复杂度
稳定性
二. 快速排序
基本思想
代码实现
hoare法
挖坑法
前后指针法
时间和空间复杂度
稳定性 一. 冒泡排序 基本思想 冒泡排序是一种交换排序。两两比较数组元素#xff0c;如果是逆序(即排列顺序与排序后… 目录
一. 冒泡排序
基本思想
代码实现
时间和空间复杂度
稳定性
二. 快速排序
基本思想
代码实现
hoare法
挖坑法
前后指针法
时间和空间复杂度
稳定性 一. 冒泡排序 基本思想 冒泡排序是一种交换排序。两两比较数组元素如果是逆序(即排列顺序与排序后的顺序相 反)就交换直到所有元素都有序为止。 方法步骤 ① 比较相邻的元素。如果第一个比第二个大就交换他们两个。 ② 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后 的元素会是最大的数。 ③ 针对所有的元素重复以上的步骤除了最后一个。 ④ 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 图示 代码实现 //冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int flag 0; //作为判断是否交换的标志for (int j 1; j n - i; j){if (a[j-1] a[j]){flag 1;int tmp a[j-1]; //交换a[j-1] a[j];a[j] tmp;}}if (flag 0)break;}
} 时间和空间复杂度 若初始序列为正序序列则只需进行一趟排序在排序过程中进行n-1次比较不移动元素若初始序列为逆序序列则需进行n-1趟排序n(n-1) / 2次比较每次比较都需要移动 3 次移动次数为 3n(n-1) / 2. 时间复杂度O(n^2) 空间复杂度O(1)
稳定性 冒泡排序稳定排序 二. 快速排序 基本思想 任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 方法步骤 从数列中挑出一个元素称为 基准pivot; 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序 图示 代码实现 hoare法 思想方法 定义两个指针 left 和 right分别指向左边和右边左指针从左向右找大( 大于pivotkey)右 指针从右向左找小(小于pivotkey)左大右小就交换相遇时与基准值交换 图解 int PartSort(int* a, int left, int right) //给数组分区返回枢轴元素下标
{int pivotkey left;while (left right){//右边找比pivotkey小的while (left right a[right] a[pivotkey])right--;//左边找比pivotkey大的while (left right a[left] a[pivotkey])left;Swap(a[left], a[right]);}Swap(a[left], a[pivotkey]); //把记录的枢轴元素交换到枢轴位置return left; //返回枢轴所在的位置下标
} 挖坑法 思想方法 定义两个指针 left 和 right分别指向左边和右边先将第一个数据元素放在临时变量 pivotkey 中形成一个坑位让右指针先走当指向的值小于 pivotkey 就停下形成新的坑位让左指针走当指向的值大于 pivotkey 就停下使其形成此次的新坑位直到两指针相遇把pivotkey的值放入坑中。 图解 int PartSort(int* a, int left, int right) //给数组分区返回枢轴元素下标
{int pivotkey a[left]; //保存第一个数据元素的值while (left right){while (left right a[right] pivotkey) //找小{right--;}a[left] a[right]; //右边形成新的坑while (left right a[left] pivotkey) //找大{left;}a[right] a[left]; //左边形成新的坑}a[left] pivotkey;return left;
} 前后指针法 思想方法 定义两个指针 prev 和 cur ,初始时prev指针指向序列开头cur指针指向prev指针的后一个位置cur的值与pivotkey的值比较cur的值小prev先后移一步cur再后移当cur的值大时就prev的值与cur的值交换直到cur为空时prev的值与pivotkey的值交换。 图解 int PartSort(int* a, int left, int right) //给数组分区返回枢轴元素下标
{int prev left;int cur left 1;int pivotkey left;while (cur right){if (a[cur] a[pivotkey] prev ! cur)Swap(a[cur], a[prev]);cur;}Swap(a[pivotkey], a[prev]);return prev;
}时间和空间复杂度 在最优情况下partition每次都划的很均匀此时时间复杂度为O(nlogn);平均情况下其时 间复杂度也为O(nlogn)。在最坏的情况下待排序的序列为正序或逆序时递归树是一棵斜树 此时快速排序会堕落为冒泡排序其时间复杂度为O(n^2),不过可以通过优化使其提升为O(nlogn),总的来说还是O(nlogn)。 空间复杂度主要是递归造成的栈空间的使用最好情况及平均情况下,树的递归深度为logn,空间复杂度均为O(logn);最坏情况空间复杂度为O(n). 时间复杂度O(nlogn) 空间复杂度O(logn) 稳定性 由于元素的比较和交换是跳跃进行的因此 快速排序不稳定排序
