快速排序！！
快速排序的实现过程包括两个主要部分：分割和递归。
创新互联是专业的王屋网站建设公司，王屋接单;提供成都网站设计、做网站、
成都外贸网站建设公司,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行王屋网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!
首先选取一个基准元素（通常是数组的第一个元素）。
从数组的左端开始，扫描整个数组，如果当前元素小于基准元素，就交换它和基准元素前面的元素，扫描结束后，基准元素左边的元素都比它小，右边的元素都比它大。
然后将基准元素与数组的最后一个元素交换，这样基准元素就位于数组的中间位置，左边的元素都比它小，右边的元素都比它大。
接下来，对基准元素左右两边的子数组分别重复上述过程，直到左右子数组的元素个数小于等于1。
整个排序过程通过递归来实现，递归的终止条件是左右子数组的元素个数小于等于1。
通过这样的分治和递归过程，可以将原始数组排序为有序数组。
需要注意的是，在选择基准元素时需要注意避免最坏情况发生，例如每次都选择大或最小的元素作为基准元素。
快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn) ~ O(n)
代码模板
#includeusing namespace std;
void qsort(int a[], int l, int r) {
int i = l, j = r, flag = a[(l + r) / 2];
do {
while (a[i]< flag) i++;
while (a[j] >flag) j--;
if (i<= j) swap(a[i], a[j]), i++, j--;
} while (i<= j);
if (i< r) qsort(a, i, r);
if (j >l) qsort(a, l, j);
}
int main() {
int n;
cin >>n;
int a[n];
for (int i = 0; i< n; i++)
scanf("%d", &a[i]);
qsort(a, 0, n - 1);
for (int i = 0; i< n; i++)
cout<< a[i]<< ' ';
return 0;
}
//注意模板中有很多小细节
sort函数
sort(a, a+n) //表示从a[0]到a[n-1]升序排列
sort(a+1, a+n+1) //表示从a[1]到a[n]升序排列
sort(a, a+n, cmp) //cmp是自定义函数，返回的是排序规则，比如return x >y,表示前一个大于后一个，也就是降序排列
例题1：奖学金（洛谷P1093）
优化前
#includeusing namespace std;
const int N = 305;
int student[N][4], number[N], sum[N];
bool cmp(int x, int y) {
return ((sum[x] >sum [y]) || (sum[x] == sum[y] && student[x][1] >student[y][1]) ||
(sum[x] == sum[y] && student[x][1] == student[y][1] && x< y));
}
int main() {
int n;
cin >>n;
for (int i = 1; i<= n; i++) {
number[i] = i;
cin >>student[i][1] >>student[i][2] >>student[i][3];
sum[i] = student[i][1] + student[i][2] + student[i][3];
}
sort(number + 1, number + 1 + n, cmp);
for (int i = 1; i<= 5; i++) {
cout<< number[i]<< ' '<< sum[number[i]]<< endl;
}
return 0;
}
优化后
#include#include
using namespace std;
const int N = 305;
int chinese[N], id[N], sum[N]; //改成一维数组，只记录语文成绩
bool cmp(int x, int y) {
return
sum[x] >sum [y] ||
sum[x] == sum[y] && chinese[x] >chinese[y] ||
sum[x] == sum[y] && chinese[x] == chinese[y] && x< y;
}
int main() {
int n;
cin >>n;
for (int i = 1; i<= n; i++) {
int math, english; //英语和数学成绩不重要，不用记录
id[i] = i;
cin >>chinese[i] >>math >>english;
sum[i] = chinese[i] + math + english;
}
sort(id + 1, id + 1 + n, cmp);
//比如原来id[1]=1,id[2]=2...
//现在 id[1]=5,id[2]=6...
//成绩最好的成绩记为编号1，他的学号是id[1],成绩是sum[id[i]]
for (int i = 1; i<= 5; i++) {
cout<< id[i]<< ' '<< sum[id[i]]<< endl;
}
return 0;
}
两种不常用算法
冒泡排序
冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
冒泡排序的实现过程如下：
首先，将第一个元素与第二个元素进行比较，如果第一个元素大于第二个元素，就交换这两个元素的位置。
接着，将第二个元素与第三个元素进行比较，如果第二个元素大于第三个元素，就交换这两个元素的位置。
按照上面的方式，重复地将相邻的元素进行比较和交换，直到比较到数组的最后一个元素。
此时，数组的最后一个元素就是大的元素。
重复上面的过程，但是不再比较最后一个元素，因为它已经是大的元素了。
接着，重复上面的过程，但是不再比较倒数第二个元素，因为它已经是第二大的元素了。
以此类推，直到整个数组都有序。
冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)
代码模板
#includeusing namespace std;
const int N = 100;
int main() {
int a[N];
int n;
cin >>n;
for (int i = 0; i< n; i++)
cin >>a[i];
for(int i = 0; i< n-1; i++)
for(int j = 0; j< n-i-1; j++){
if(a[j] >a[j+1]) swap(a[j], a[j+1]);
}
for (int i = 0; i< n; i++)
cout<< a[i]<< ' ';
return 0;
}
计数排序
计数排序是一种非比较型排序算法，它适用于数据范围较小的情况。
它的基本思想是，对于待排序的数组中的每一个元素，确定其在整个数组中出现的次数，然后根据这个次数将元素放到最终结果的对应位置上。
具体实现过程如下：
创建一个计数数组 counts，用来存储每个元素在数组中出现的次数。
遍历待排序的数组，统计每个元素出现的次数，存入 counts 数组中。
遍历 counts 数组，将 counts[i] 个元素 i 放入结果数组的对应位置。
返回结果数组。
由于计数排序是一种线性排序算法，因此时间复杂度为 O(n)，空间复杂度为 O(k)，其中 n 为数组大小，k 为数据范围。
由于计数排序不需要进行元素之间的比较，因此它是一种稳定排序算法。但是，由于它的空间复杂度随着数据范围的增大而增大，所以它在数据范围较大的情况下不太适用。
计数排序需要预先知道数据的范围
代码模板
#includeusing namespace std;
const int MAX = 100; //数组元素的大值
const int N = 100;
int arr[N], counts[MAX];
int main() {
int n; //数组的长度
cin >>n;
for (int i = 0; i< n; i++) {
cin >>arr[i];
counts[arr[i]]++;
}
int j = 0;
for (int i = 0; i< MAX; i++) { //遍历0到大值，根据之前统计的每个数字的个数，来给数组重新赋值
while (counts[i]--) {
arr[j++] = i;
}
}
for (int i = 0; i< n; i++) {
cout<< arr[i]<< " ";
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文标题：快速排序及自定义函数-创新互联
URL分享：
http://cdkjz.cn/article/hhdpc.html
