做舞美的好素材网站j,舆情信息报送,东营市城乡建设局网站,网站空间费用1.快速排序
主要思想#xff1a;基于分治思想。通过选择一个基准元素#xff0c;将数组分为两部分#xff0c;左边部分元素都小于等于基准#xff0c;右边部分元素都大于等于基准。然后对这两部分分别递归地进行排序。
分区逻辑#xff1a;双指针算法
左指针i从左往右找…1.快速排序
主要思想基于分治思想。通过选择一个基准元素将数组分为两部分左边部分元素都小于等于基准右边部分元素都大于等于基准。然后对这两部分分别递归地进行排序。
分区逻辑双指针算法
左指针i从左往右找到第一个大于等于基准的元素右指针从右往左找到第一个小于等于基准的元素交换两个元素使得左侧部分小于等于基准右侧部分大于等于基准
设l是待排序区间的左边界r是右边界
确定分界点x基准可以取左边界的值q[l]或右边界的值q[r]或者中间位置的值q[(l r)/2]根据基准值调整区间使得左半边区间的值全都≤ x右半边区间的值全都≥ x . 采用双指针左指针i从左边界l-1开始往右扫描右指针j从右边界r1开始往左扫描 为什么初始是l-1r1 因为后续的不管执行交换与否首先都先将ij向内移动一位所以一开始的两个指针都设置为超出边界一个位置 当满足条件q[i] x时i右移直到不满足条件时即q[i] xi停下;
然后移动右指针jj 当满足条件q[j] x时j左移直到不满足条件时即q[j] xj停下
交换q[i]和q[j] 将i右移一位j左移一位重复上面的操作直到i和j相遇(最终i和j的位置为ij或ij1)。 此时左半区间的数都满足≤x且左半区间的最后一个数的下标为j右半区间的数都满足≥ x,且右半区间的第一个数的下标为i
递归处理左右两段 若用j来作为区间的分界则[l, j] 都是≤x[j 1, r]都是≥x若用i来作为区间的分界则[l, i - 1]都是≤x[i, r]都是≥x 注意 递归取[l, j][j 1, r]区间时基准值不能取右边界xq[r]不然会出现死循环问题此时常取左边界xq[l]或中间值 eg:1,2 会出现死循环 同理当递归取[l, i - 1][i,r]区间时基准值不能取左边界xq[l]不然会出现死循环问题此时常取左边界xq[r] 或中间值 eg:1,2 会出现死循环 快排不稳定平均时间复杂度nlogn。最坏情况例如数组已经有序的情况下时间复杂度为 ( 2 ) (^2) O(n2)但通过选择中间值作为基准可以减少最坏情况的发生。 这里给出一个快排的板子
// 快速排序函数q[] 是待排序的数组l 是左边界r 是右边界
void quick_sort(int q[], int l, int r) {if (l r) return; // 递归终止条件当左边界大于或等于右边界时停止递归// 选择中间元素作为基准数并初始化左右指针 i 和 jint x q[(l r) / 2], i l - 1, j r 1;// 使用双指针法进行分区while (i j) {// 从左边开始找到第一个大于等于基准数的元素do i; while (q[i] x);// 从右边开始找到第一个小于等于基准数的元素do j--; while (q[j] x);// 如果 i 和 j 没有相遇交换 q[i] 和 q[j]确保左边都比基准数小右边都比基准数大if (i j) swap(q[i], q[j]);}// 递归处理左半部分quick_sort(q, l, j);// 递归处理右半部分quick_sort(q, j 1, r);
}Acwing 785.快速排序 具体实现代码详解版
#include iostream
#include algorithmusing namespace std;const int N 1e6 10; int n;
int q[N]; // 存储待排序的数组// 快速排序函数q[] 是待排序的数组l 是左边界r 是右边界
void quick_sort(int q[], int l, int r) {if (l r) return; // 递归终止条件当左边界大于或等于右边界时停止递归// 选择中间元素作为基准数并初始化左右指针 i 和 jint x q[(l r) / 2], i l - 1, j r 1;// 使用双指针法进行分区while (i j) {// 从左边开始找到第一个大于等于基准数的元素do i; while (q[i] x);// 从右边开始找到第一个小于等于基准数的元素do j--; while (q[j] x);// 如果 i 和 j 没有相遇交换 q[i] 和 q[j]确保左边都比基准数小右边都比基准数大if (i j) swap(q[i], q[j]);}// 递归处理左半部分quick_sort(q, l, j);// 递归处理右半部分quick_sort(q, j 1, r);
}int main() {cin n; for (int i 0; i n; i) cin q[i];quick_sort(q, 0, n - 1);for (int i 0; i n; i) cout q[i] ;cout endl; return 0;
}
Acwing 786.第k个数 实现思路直接进行快排然后注意第k个数的数组下标是k-1,即答案就是q[ k - 1].
#include iostream
#include algorithmusing namespace std;const int N 1e6 10;
int n , k;
int q[N];//快速排序
void quick_sort(int q[],int l , int r){if(l r) return ;int x q[(l r) / 2], i l - 1, j r 1;while(i j){do i ; while(q[i] x);do j -- ; while(q[j] x);if(i j) swap(q[i] , q[j]);}quick_sort(q, l ,j);quick_sort(q, j 1 ,r);
}int main(){cin n k ;for(int i 0 ; i n ; i ) cin q[i];quick_sort(q, 0 , n - 1);//第k个数cout q[k - 1] endl;return 0;
}
2.归并排序
主要思想也是基于分治思想
先确认分界点下标一般取中间点l r) /2;对左右两个子数组分别进行递归排序将两个排好序的子数组合二为一
实现思路设置左右指针和一个临时数组temp左指针指向左区间的的第一个元素右指针指向右区间的第一个元素循环比较左右指针所指元素两者较小的元素放入temp数组中指针后移继续比较。直至某一指针到达末尾将其中一个未放置完的区间的数再都放入temp数组。 归并排序的时间复杂度为 ( l o g ) (log) O(nlogn)即使在最坏的情况下也是如此。它的性能较为稳定适用于大规模数据的排序任务 归并排序的板子
const int N 1e6 10; // 定义数组容量为 10^6 10int n;
int q[N], temp[N]; // q[] 存储待排序的数组temp[] 是归并时的临时数组// 归并排序函数q[] 是待排序的数组l 是左边界r 是右边界
void merge_sort(int q[], int l, int r) {if (l r) return; // 递归终止条件如果只有一个元素直接返回int mid (l r) / 2; // 取中间点将数组分成两部分// 递归处理左半部分merge_sort(q, l, mid);// 递归处理右半部分merge_sort(q, mid 1, r);// 合并两个有序的部分int i l, j mid 1, k 0; // i 追踪左半部分j 追踪右半部分k 追踪临时数组while (i mid j r) {if (q[i] q[j]) temp[k] q[i]; // 左边小或相等时将左边的元素放入临时数组else temp[k] q[j]; // 否则将右边的元素放入临时数组}// 如果左半部分还有剩余元素放入临时数组while (i mid) temp[k] q[i];// 如果右半部分还有剩余元素放入临时数组while (j r) temp[k] q[j];// 将临时数组中的元素拷贝回原数组的对应位置for (i l, k 0; i r; i, k) q[i] temp[k];
}Acwing 787.归并排序 具体实现代码详解版
#include iostream
using namespace std;const int N 1e6 10; // 定义数组容量为 10^6 10int n;
int q[N], temp[N]; // q[] 存储待排序的数组temp[] 是归并时的临时数组// 归并排序函数q[] 是待排序的数组l 是左边界r 是右边界
void merge_sort(int q[], int l, int r) {if (l r) return; // 递归终止条件如果只有一个元素直接返回int mid (l r) / 2; // 取中间点将数组分成两部分// 递归处理左半部分merge_sort(q, l, mid);// 递归处理右半部分merge_sort(q, mid 1, r);// 合并两个有序的部分int i l, j mid 1, k 0; // i 追踪左半部分j 追踪右半部分k 追踪临时数组while (i mid j r) {if (q[i] q[j]) temp[k] q[i]; // 左边小或相等时将左边的元素放入临时数组else temp[k] q[j]; // 否则将右边的元素放入临时数组}// 如果左半部分还有剩余元素放入临时数组while (i mid) temp[k] q[i];// 如果右半部分还有剩余元素放入临时数组while (j r) temp[k] q[j];// 将临时数组中的元素拷贝回原数组的对应位置for (i l, k 0; i r; i, k) q[i] temp[k];
}int main() {cin n; // 输入数组长度// 读取 n 个元素存入数组 q 中for (int i 0; i n; i) cin q[i];// 调用归并排序算法排序整个数组merge_sort(q, 0, n - 1);// 输出排序后的数组for (int i 0; i n; i) cout q[i] ;cout endl; // 换行return 0; // 程序结束
}
Acwing.788求逆序对的数量 实现思路
根据归并排序的思想将数组分为各自有序的左右两个区间[l,mid],[mid1,r]采用双指针开始分别指向两个区间的第一个元素相互比较选出较小的那个元素然后后移不断循环直到一个区间遍历完。在比较过程中设i指向左区间j指向右区间由于两个区间各自有序逆序对只会出现一种情况即左区间存在大于右区间元素的元素。若a[i]a[j]则左区间中从i开始到mid的元素都大于a[j]与a[j]组成逆序对数量为mid-i1 注意对于给定n个数最坏的情况为逆序则逆序对数为n(n-1)/2个题中数据个数范围为100000则最大结果会超出int的存储范围(-231~231-1)所以虽好使用long long来存储最终结果 具体实现代码详解版
#include iostream
#include algorithmusing namespace std;typedef long long LL;
const int N 1e6 10;
int n;
int q[N], temp[N]; // q[] 用于存储输入数组temp[] 用于合并时的临时数组// 归并排序函数返回区间 [l, r] 的逆序对数量
LL merge_sort(int l, int r) {if (l r) return 0; // 如果区间内只有一个元素返回 0表示没有逆序对int mid (l r) / 2; // 找到中间位置// 递归处理左半部分和右半部分并计算各自的逆序对数量LL res merge_sort(l, mid) merge_sort(mid 1, r);// 合并两个有序区间同时统计逆序对int i l, j mid 1, k 0; // i 指向左区间j 指向右区间k 是 temp 的索引while (i mid j r) {if (q[i] q[j]) {temp[k] q[i]; // 如果左区间的元素小于等于右区间取左区间的元素} else {temp[k] q[j]; // 否则取右区间的元素res mid - i 1; // 统计逆序对的数量mid - i 1 表示当前左区间剩余的元素个数}}// 如果左区间还有剩余元素直接加入 temp[]while (i mid) temp[k] q[i];// 如果右区间还有剩余元素直接加入 temp[]while (j r) temp[k] q[j];// 将 temp[] 中的元素复制回原数组 q[]for (int i l, k 0; i r; i, k) q[i] temp[k];return res; // 返回逆序对的数量
}int main() {cin n;for (int i 0; i n; i) cin q[i];// 输出逆序对的数量cout merge_sort(0, n - 1) endl;return 0;
}
以上就是两种经典常考的排序算法快排的思想是选择基准点然后进行分区而归并排序是选择一个位置将原序列划分为两个序列再分别进行排序最后合并为一个有序数组。可以看到各有优缺点下面进行一个简答的总结
