国土网站建设自查报告,网站制作济南,怎么在网上接网站建设,wordpress文章怎么打开空格冒泡排序
冒泡排序#xff08;Bubble Sort#xff09;是一种简单的排序算法#xff0c;它通过重复遍历要排序的数列#xff0c;一次比较两个元素#xff0c;如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换#xff0c;也就是说该数列已…
冒泡排序
冒泡排序Bubble Sort是一种简单的排序算法它通过重复遍历要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
//冒泡排序
void BubbleSort(int* a, int n) {for (int i 0; i n - 1; i) { //冒泡 n-1 次bool flag false;for (int j 0; j n - i - 1; j) {if (a[j] a[j 1]) {Swap(a[j], a[j 1]);}flag true;}if (!flag) {break;}}
}
时间复杂度
O(n^2)
空间复杂度
原地修改O(1)
快速排序
快速排序Quick Sort是一种高效的排序算法由C. A. R. Hoare在1960年提出。它的基本思想是分治法Divide and Conquer通过一个划分操作将数据分为独立的两部分其中一部分的所有数据都比另一部分的所有数据要小然后再递归地对这两部分数据分别进行排序操作。
递归版本
递归版本一hoare 大致思想通过左右下标指针不断的寻找交换每趟分割可以将 1 个 a[keyi] 归位递归地分割、归位子序列即可
右下标指针 right 从右开始寻找小于 a[keyi] 的值左下标指针 left 从左开始寻找大于 a[keyi] 的值然后交换 a[left] 和 a[right]继续寻找直到 left 和 right 相遇将 a[keyi] 归位
//单趟分割区间
int PartSort_1(int* a, int left, int right) {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[left], a[keyi]);return left;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素或区间不存在if (begin end) {return;}//分割区间int midi PartSort_1(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi 1, end);}
递归版本二挖坑法 大致思想hoare法是大小交换而挖坑法是找到小了立即交换到左边找到大了立即交换到右边hole坑的值由 key 保存坑的位置随着值的交换而变化
//单趟分割区间
//挖坑法
int PartSort_2(int* a, int left, int right) {int key a[left]; //保存被挖坑的值int hole left;while (left right) {//右边开始找小while (left right a[right] key) {right--;}a[hole] a[right];hole right;//左边开始找大while (left right a[left] key) {left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素或区间不存在if (begin end) {return;}//分割区间//int midi PartSort_1(a, begin, end);int midi PartSort_2(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi 1, end);
}
递归版本三前后指针法 大致思想通过 prev 和 cur 下标指针将每趟大于等于 a[keyi] 的值往后推最后将基准值 a[keyi] 与 a[prev] 交换归位
//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int prev left;int cur prev 1;int keyi left;while (cur right) {cur 找小//while (cur right a[cur] a[keyi]) {// cur;//}//if (cur right) { //避免所有元素都大于 keyi// prev;// Swap(a[cur], a[prev]);//}if (a[cur] a[keyi]) {prev;Swap(a[cur], a[prev]);}cur;}Swap(a[keyi], a[prev]);return prev;
}//快速排序
void QuickSort(int* a, int begin, int end) {//只有一个元素或区间不存在if (begin end) {return;}//分割区间//int midi PartSort_1(a, begin, end);//int midi PartSort_2(a, begin, end);int midi PartSort_3(a, begin, end);//递归分割子区间// [begin,midi-1] midi [midi1,end]QuickSort(a, begin, midi - 1);QuickSort(a, midi 1, end);
}
时间复杂度三个版本效率相同
每趟区间分割创建函数栈帧的复杂度为二叉结构的高度 O(logn)每趟区间分割确定一个数的位置 O(n)所以是 O(n*logn)
但是如果数组有大量重复元素时每次选择的 keyi 基准值都是同一个数或者每次选择的 keyi 都是数组中最大或最小的元素那么递归深度就会大大增加时间复杂度变成 O(n^2)比如下面的示意图 空间复杂度三个版本效率相同
取决于递归深度即二叉结构高度 O(logn)
稳定性
涉及到元素之间的交换不稳定
递归版本的优化
为了避免取基准值 keyi 时出现取到最小或最大的情况我们使用三数取中的方法
//三数取中
int GetMidIndex(int* a, int left, int right) {int midi (left right) / 2;if (a[left] a[midi]) {Swap(a[left], a[midi]); //此时 a[left] a[midi]}if (a[left] a[right]) {Swap(a[left], a[right]); //此时 a[left] a[right]}if (a[midi] a[right]) {Swap(a[right], a[midi]); //此时 a[midi] a[right]}return midi;
}以版本三为例应用
//单趟分割区间
//前后指针法
int PartSort_3(int* a, int left, int right) {int keyi GetMidIndex(a, left, right);Swap(a[keyi], a[left]);int prev left;int cur prev 1;keyi left;while (cur right) {cur 找小//while (cur right a[cur] a[keyi]) {// cur;//}//if (cur right) { //避免所有元素都大于 keyi// prev;// Swap(a[cur], a[prev]);//}if (a[cur] a[keyi]) {prev;Swap(a[cur], a[prev]);}cur;}Swap(a[keyi], a[prev]);return prev;
}非递归版本
考虑到递归会有栈溢出的风险所以非递归版本使用动态栈进行模拟
对栈有问题请看之前的文章~
大致思想见代码注释~
//非递归快排
void QuickSortNonR(int* a, int begin, int end) {//栈具有后进先出的性质//初始化一个动态栈Stack st;StackInit(st);//将区间入栈StackPush(st, end);StackPush(st, begin);while (StackEmpty(st)) { //只要栈非空子区间未分割完//从栈中取出一对区间int l StackTop(st);StackPop(st);int r StackTop(st);StackPop(st);//对这对区间分割int keyi PartSort_3(a, l, r);//分割完之后接着分割子区间// [l,keyi-1] keyi [keyi1,r]//先让左右子区间入栈//避免区间不存在或者只有一个元素的情况if (keyi 1 r) {StackPush(st, r);StackPush(st, keyi 1);}if (l keyi - 1) {StackPush(st, keyi - 1);StackPush(st, l);}}StackDestroy(st);
}
