怎么做化妆品网站内容规划,免费做网站的网页,网站空间2000m多少钱,网站符号目录
前言
1.冒泡排序
1.1冒泡排序动图
1.2冒泡排序源代码
1.3冒泡排序的特性总结
2.快速排序#x1f451;
2.1hoare版本实现思想
排序前
排序中
排序后
2.2hoare版本快排源代码
2.3分析先走
情况1#x1f947;
情况2#x1f948; 前言 交换类排序两个常见的排…
目录
前言
1.冒泡排序
1.1冒泡排序动图
1.2冒泡排序源代码
1.3冒泡排序的特性总结
2.快速排序
2.1hoare版本实现思想
排序前
排序中
排序后
2.2hoare版本快排源代码
2.3分析先走
情况1
情况2 前言 交换类排序两个常见的排序算法【冒泡排序】、【快速排序】 交换排序基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 1.冒泡排序
1.1冒泡排序动图 冒泡排序动图 1.2冒泡排序源代码 void BubbleSort(int* a, int n)
{assert(a);for (int j 0; j n - 1; j){int exchange 0;//这里的exchange的值作为是否交换的标志for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)//一趟下来exchange的值还为0证明就没有发生交换也就是已经有序{break;}}
} 1.3冒泡排序的特性总结 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度 O(N^2) 最坏O(N^) 、最好O(N) 3. 空间复杂度 O(1) 4. 稳定性稳定 2.快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 2.1hoare版本实现思想 排序前 排序中 ①先选出一个基准值key一般是最左边或者最右边) ②然后右边【L】先走找比key小的值找到了就停下然后再左边找比key大的值找到了也停下 ③然后交换这两个数 经过上面三步就动图就变成了下面的样子 排序后 由于是一个一个先走一个后走肯定会出现相遇的时候相遇就停下来。相遇后将相遇坐标的值和基准值key交换这时就完成了单趟的hoare排序 【这时的key其实就是在正确的位置上了】 相遇时如下图 2.2hoare版本快排源代码 void QuickSort(int* a, int begin, int end)
{// 区间不存在或者只有一个值则不需要在处理if (begin end){return;}int left begin, right end;int keyi left;while (left right){// 右边先走找小while (left right a[right] a[keyi]){--right;}// 左边再走找大while (left right a[left] a[keyi]){left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);keyi left;// [begin, keyi-1] keyi [keyi1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi1, end);
} 2.3分析先走 为什么左边做key右边先走。 右边做key左边先走。 这样就可以保证相遇位置的值小余或者等于key 我这边拿左边做key右边先走的情况来讲解。 情况1 这个情况比较好理解就是上面最后相遇位置的值也就是3比6要小 情况2 这个情况如下图所示 这边也可以去画一下左边做key左边先走的情况会发现相遇位置的值不能保证比key要小 如果觉得文章不错期待你的一键三连哦你个鼓励是我创作的动力之源让我们一起加油顶峰相见 下期预告快排的其他版本和非递归版本
