网站建设首页模板下载,手机关联网站,网站广告设计怎么做,个人营业执照网上注册入口快速排序
题目1
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式 输入共两行#xff0c;第一行包含整数 n。
第二行包含 n 个整数#xff08;所有整数均在 1∼109 范围内#xff09;#…快速排序
题目1
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式 输入共两行第一行包含整数 n。
第二行包含 n 个整数所有整数均在 1∼109 范围内表示整个数列。
输出格式 输出共一行包含 n 个整数表示排好序的数列。
数据范围 1≤n≤100000 输入样例 5 3 1 2 4 5 输出样例 1 2 3 4 5
#includeiostreamusing namespace std;const int N 1e510;int q[N];void quick_sort(int q[], int l, int r){if(lr) return;int x q[(lr)/2];int i l-1, j r1;while(ij){do i; while(q[i]x);do j--; while(q[j]x);if(ij) swap(q[i],q[j]);}quick_sort(q,l,j);quick_sort(q,j1,r);}int main(){int n;cinn;for(int i0; in; i) scanf(%d, q[i]);quick_sort(q,0,n-1);for(int i0;in;i) printf(%d ,q[i]);return 0;
}算法思想快速排序是基于分治的思想其基本思路是首先选取一个基准点根据这个基准点将数组划分出两个部分分别对左右两边递归的进行排序。在理想的情况下基准点的划分是能将数据进行中间等长切分的这样只需要切分logn次因为每次都变为以前的一半log的底数为2, 2的n次方次。最坏的情况需要求切分n次。 复杂度分析快速排序是一种基于分治思想的排序算法其时间复杂度为 O(nlogn)。这是因为在每一次递归中快速排序都会选择一个基准元素pivot element并将数组分成两部分小于基准元素的元素和大于基准元素的元素。然后递归地对这两部分进行排序。在平均情况下快速排序每次递归都会将数组分成大小大致相等的两部分因此每次递归的时间复杂度为 O(n)因为是在进行线性的一个交换所以复杂度是O(n)。由于递归的深度为 logn最坏情况下为 n所以整个排序过程的时间复杂度为 O(nlogn)。然而最坏情况下快速排序的时间复杂度为 O(n^2)。这发生在每次递归所选的基准元素都是当前数组中的最小值或最大值时。在这种情况下快速排序退化为冒泡排序每次递归只能将数组分成大小为 1 和 n-1 的两部分导致时间复杂度为 O(n^2)。为了避免最坏情况的发生可以使用随机化快速排序Randomized Quicksort它在选择基准元素时加入随机性使得平均情况下时间复杂度保持为 O(nlogn)。
题目2 快速排序的一个应用-第k个数
给定一个长度为 n 的整数数列以及一个整数 k请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式 第一行包含两个整数 n 和 k。
第二行包含 n 个整数所有整数均在 1∼109 范围内表示整数数列。
输出格式 输出一个整数表示数列的第 k 小数。
数据范围 1≤n≤100000, 1≤k≤n 输入样例 5 3 2 4 1 5 3 输出样例 3
#includeiostreamusing namespace std;const int N 100010;int q[N];void quick_sort(int q[], int l, int r){if(lr) return;int mid l r 1;int x q[mid];int i l-1, j r1;while(ij){do i; while(q[i]x);do j--; while(q[j]x);if(ij) swap(q[i],q[j]);}quick_sort(q,l,j);quick_sort(q,j1,r);}int main(){int n;int k;scanf(%d %d, n,k);for(int i0;in;i) scanf(%d,q[i]);quick_sort(q,0,n-1);printf(%d,q[k-1]);return 0;
}
