快速排序模板整理

Love The Way You Lie 2021-07-24 21:03 426阅读 0赞

**快速排序**

### **1.思想** ###

快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

假设待排序的序列为\{ a\[1\]，a\[1+1\], a\[1+2\],…a\[r\] \},首先任意选取一个记录(通常可选中间一个记作为枢轴或支点)，然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中，所有关键字大于它的记录都放在右子序列中。由此可以将该“支点"记录所在的位置mid作分界线，将序列分割成两个子序列和。这个过程称作一趟快速排序(或一次划分)。

一趟快速排序的具体做法是:附设两个指针i和j，它们的初值分别为i-1和r+1,设枢轴记录取mid,则首先从j所指位置起向前搜索找到第一个关键字小于mid的记录,然后从 i所指位置起向后搜索，找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>=j为止。

### **2.模板** ###

const int maxn = 1e5 + 10;
    int q[maxn];
    void quick_sort(int q[],int l,int r)
    { 
    	if (l >= r)  return;    //递归边界
    	int i = l - 1, j = r + 1, x = q[l + r >> 1];     //这里的初值分别设为l-1，r+1是因为
    	//while中是do，while结构。先使i+1，j-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);  //递归左右子序列
    }

### **3.例题** ###

给定你一个长度为n的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

**输入格式**  
输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整个数列。

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

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

**代码：**

//快速排序模板
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e5 + 10;
    int q[maxn];
    void quick_sort(int q[],int l,int r)
    { 
    	if (l >= r)  return;
    	int i = l - 1, j = r + 1, x = q[l + 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()
    { 
    	int n;
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{ 
    		cin >> q[i];
    	}
    	quick_sort(q, 1, n);
    	for (int i = 1; i <= n; i++)
    	{ 
    		cout << q[i] << " ";
    	}
    	cout << endl;
    	return 0;
    }

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

**输入格式**  
第一行包含两个整数 n 和 k。

第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。

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

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

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e5 + 10;
    int q[maxn];
    int n, k;
    int quick_sort(int q[],int l, int r, int k)
    { 
    	if (l >= r)   return q[l];
    	int i = l - 1, j = r + 1, x = q[(l + r) / 2];
    	while (i < j)
    	{ 
    		do i++; while (q[i] < x);
    		do j--; while (q[j] > x);
    		if (i < j) swap(q[i], q[j]);
    	}
    	int sl = j - l + 1;
    	if (sl >=k )  return quick_sort(q,l, j, k);
    	else return  quick_sort(q,j + 1, r, k - sl);
    }
    int main()
    { 
    	cin>> n >> k;
    	for (int i = 0; i < n; i++)
    	{ 
    		cin >> q[i];
    	}
    	cout << quick_sort(q,0, n - 1, k)<<endl;
    	return 0;
    }