首都医科大学网站建设,网站建设佰首选金手指三十,为学校做网站策划怎么写,jsp网站开发的优点文章目录 1.冒泡排序1.1代码实现1.2复杂度 2.快速排序2.1人物及思想介绍【源于百度】2.2hoare【霍尔】版本1.初识代码2.代码分析3.思其因果 3.相关博客 1.冒泡排序 1.1代码实现
//插入排序 O(N)~O(N^2)
//冒泡排序 O(N)~O(N^2)
//当数据有序 二者均为O(N)
//当数据接近有序或… 文章目录 1.冒泡排序1.1代码实现1.2复杂度 2.快速排序2.1人物及思想介绍【源于百度】2.2hoare【霍尔】版本1.初识代码2.代码分析3.思其因果 3.相关博客 1.冒泡排序 1.1代码实现
//插入排序 O(N)~O(N^2)
//冒泡排序 O(N)~O(N^2)
//当数据有序 二者均为O(N)
//当数据接近有序或局部有序 插排更优
void BubbleSort(int* a, int n)
{assert(a);int flag 1;for (int i 0; flag i n - 1; i){flag 0;for (int j 0; j n - 1 - i; j){if (a[j] a[j 1]){Swap(a[j - 1], a[j]);flag 1;}}}
}1.2复杂度
最坏 比较n-1轮 每一轮比较次数n n-1 n-2 n-3 … 1 ≈ N^2最优 比较n-1轮 数据有序–每一轮只判断不比较 – N
2.快速排序
2.1人物及思想介绍【源于百度】 2.2hoare【霍尔】版本
1.初识代码
//快速排序 O(N * logN)
void QuickSort(int* a, int b, int e)
{//b--begin左区间左边界下标 //e--end 右区间右边界下标//be:数据量1 无需排序 直接返回//be :无效区间 无需排序 直接返回if (b e)return;int left b, right e, x left;while (left right){//右找小while (left right a[right] a[x])--right;//左找大while (left right a[left] a[x])left;Swap(a[left], a[right]);}Swap(a[x], a[left]);x left;// [b, x - 1] x [x 1, e]QuickSort(a, b, x - 1);QuickSort(a, x1, e);
}
2.代码分析 3.思其因果 Q为什么a[x]【作为基准值key】置于左侧 – 右边先移动 A目的是为了保证相遇位置的值key 从而把key与相遇值交换 不打乱“左放小右放大”的思想 3.相关博客
点击 qsort与bubble之间不为人知的关系 查看博主之前关于分析这两个排序的博客。
