快速排序及运用

1.快速排序题目要求

给定你一个长度为n的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。

输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整个数列。

输出格式 输出共一行，包含 n 个整数，表示排好序的数列。

数据范围 1 ≤ n ≤ 100000 输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5

算法的基本思想和步骤： 该算法主要运用了分治的思想，通过递归的方法进行大小排序。 第一步：确定分界点x。这里可以选择左右边界数或者是中间数。 第二步：调整区间。通过指针的移动以及对应数的交换,实现x的左边的数都小于等于x, x的右边的数都大于等于x。 第三步：递归处理左右两段。

题目关键点： 本题的关键点在于调整区间。采用从前向后和从后向前的双向遍历的方法进行排序，当遇到不符合条件的数据时停下来，进行指针所指向位置的比较，如果没有相遇，则进行两数交换。然后继续遍历，直至指针相遇。在选择递归的边界点时，也应当注意与分界点相对应。

程序代码：

#include <stdio.h> const int N = 1e6; void quick_sort (int a[], int l, int r) { if(l >= r) return; int x = a[(l + r + 1) / 2]; int i = l - 1, j = r + 1;//后续程序是先移动后比较，这里应选择边界的两边 while(i < j) { while(a[++ i] < x); while(a[-- j] > x); if(i < j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } quick_sort (a, l, i - 1);//这里选取的边界需要与x的取值对应，否则会发生死循环 quick_sort (a, i, r);// 递归处理指针交界的左右两段 } int main() { int a[N], n; scanf("%d", &n); for(int i = 0; i < n; i ++) scanf("%d", &a[i]); quick_sort (a, 0, n-1); for(int i = 0; i < n; i ++) printf("%d ", a[i]); return 0; }

2.第k个数题目要求：

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。

输入格式 第一行包含两个整数 n 和 k。 第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整数数列。

输出格式 输出一个整数，表示数列的第k小数。

数据范围 1 ≤ n ≤ 100000, 1 ≤ k ≤ n 输入样例： 5 3 2 4 1 5 3 输出样例： 3

程序代码：

#include <stdio.h> const int N = 1e6 + 10; void quick_sort (int a[], int l, int r); int main() { int n, k, a[N]; scanf("%d%d", &n, &k); for(int i = 0; i < n; i ++) scanf("%d", &a[i]); quick_sort (a, 0, n - 1); printf("%d", a[k-1]); return 0; } void quick_sort(int a[], int l, int r) { if(l >= r) return; int x = a[(l + r)/ 2], i = l -1, j = r + 1; while(i < j) { while(a[++i] < x); while(a[--j] > x); if(i < j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } quick_sort (a, l, j); quick_sort (a, j + 1, r); }

或者每次递归时只扫目标数所在的区间，降低时间复杂度。

#include <iostream> using namespace std; const int N = 1e6 +10; int n, k, a[N]; int quick_sort(int a[], int l, int r, int k) { if(l == r) return a[l]; int x = a[l]; //或者x = a[r] int i = l - 1, j = r + 1; while(i < j) { while(a[++ i] < x); while(a[-- j] > x); if(i < j) swap(a[i], a[j]); } int sl = j - l + 1; //或者sl = i - l if(k <= sl) return quick_sort(a, l, j, k); //或者(a, l, i - 1, k) return quick_sort(a, j + 1, r, k - sl); //或者(a, i, r, k - sl) } int main() { cin >> n >> k; for(int i = 0 ; i < n; i ++) cin >> a[i]; cout << quick_sort(a, 0, n - 1, k); return 0; }