建立网站的连接结构有哪几种形式,wordpress首页幻灯片尺寸,运营托管公司,怎么把平台推广出去目录 1.交换排序
#xff08;1#xff09;冒泡排序
#xff08;2#xff09;快速排序 1.交换排序 基本思想#xff1a;所谓交换#xff0c;就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置#xff0c;交换排序的特点是#xff1a;将键值较大的…目录 1.交换排序
1冒泡排序
2快速排序 1.交换排序 基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。 1冒泡排序 冒泡排序的特性总结 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性稳定 冒泡的主要思想是 一趟一趟将最大、次大等等数据排放到最后的位置 如单趟 for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);}} 放完最大的数据到达数组最后一个位置后就可以屏蔽最后一个位置end下标。 即n--; 完整冒泡 // 冒泡排序
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int flag 1;for (int i 1; i n - j; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);flag 0;}}if (flag)break;}
} 加flag标注的原因仅是防止有序时遍历n^2 2快速排序 快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右 子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止 。 与二叉树的思想大致类似熟悉二叉树的遍历递归后这块部分理解起来就会相对容易本人感觉还是有点难度。 核心思想 while (l r){while (l r a[r] a[keyi]){r--;}while (l r a[l] a[keyi]){l;}Swap(a[l], a[r]);} 之后可以将keyi移到中间位置这时左边全是比他小的数可相等右边全是比他大的数可相等因此就可以开始递归左边和右边然后左边的左边和右边等等当begin end时就可以return了。 完整代码 //快速排序
void QuickSort(int* a, int begin,int end)
{if (begin end)return;int keyi begin;int l begin;int r end;while (l r){while (l r a[r] a[keyi]){r--;}while (l r a[l] a[keyi]){l;}Swap(a[l], a[r]);}Swap(a[l], a[keyi]);keyi l; QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
} 对代码进行优化可以取最左、中、最右三个值取中间大小的值最为基准值keyi可以提高排序的效率。 即 int GetMidi(int* a, int begin, int end)
{int midi (begin end) / 2;// begin end midi三个数选中位数if (a[begin] a[midi]){if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}else// a[begin] a[midi]{if (a[midi] a[end])return midi;else if (a[begin] a[end])return begin;elsereturn end;}
}
//快速排序
void QuickSort(int* a, int begin,int end)
{if (begin end)return;int midi GetMidi(a, begin, end);Swap(a[midi], a[begin]);int keyi begin;int l begin;int r end;while (l r){while (l r a[r] a[keyi]){r--;}while (l r a[l] a[keyi]){l;}Swap(a[l], a[r]);}Swap(a[l], a[keyi]);keyi l; QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);
}