绵阳梓潼网站制作公司

快速排序及自定义函数-创新互联

快速排序！！

快速排序的实现过程包括两个主要部分：分割和递归。

创新互联是专业的王屋网站建设公司，王屋接单;提供成都网站设计、做网站、成都外贸网站建设公司,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行王屋网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

  1. 首先选取一个基准元素（通常是数组的第一个元素）。

  1. 从数组的左端开始，扫描整个数组，如果当前元素小于基准元素，就交换它和基准元素前面的元素，扫描结束后，基准元素左边的元素都比它小，右边的元素都比它大。

  1. 然后将基准元素与数组的最后一个元素交换，这样基准元素就位于数组的中间位置，左边的元素都比它小，右边的元素都比它大。

  1. 接下来，对基准元素左右两边的子数组分别重复上述过程，直到左右子数组的元素个数小于等于1。

  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;
}

两种不常用算法 冒泡排序

冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

冒泡排序的实现过程如下：

  1. 首先，将第一个元素与第二个元素进行比较，如果第一个元素大于第二个元素，就交换这两个元素的位置。

  1. 接着，将第二个元素与第三个元素进行比较，如果第二个元素大于第三个元素，就交换这两个元素的位置。

  1. 按照上面的方式，重复地将相邻的元素进行比较和交换，直到比较到数组的最后一个元素。

  1. 此时，数组的最后一个元素就是大的元素。

  1. 重复上面的过程，但是不再比较最后一个元素，因为它已经是大的元素了。

  1. 接着，重复上面的过程，但是不再比较倒数第二个元素，因为它已经是第二大的元素了。

  1. 以此类推，直到整个数组都有序。

冒泡排序的时间复杂度为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;
}
计数排序

计数排序是一种非比较型排序算法，它适用于数据范围较小的情况。

它的基本思想是，对于待排序的数组中的每一个元素，确定其在整个数组中出现的次数，然后根据这个次数将元素放到最终结果的对应位置上。

具体实现过程如下：

  1. 创建一个计数数组 counts，用来存储每个元素在数组中出现的次数。

  1. 遍历待排序的数组，统计每个元素出现的次数，存入 counts 数组中。

  1. 遍历 counts 数组，将 counts[i] 个元素 i 放入结果数组的对应位置。

  1. 返回结果数组。

由于计数排序是一种线性排序算法，因此时间复杂度为 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元起，快前往官网查看详情吧


本文标题：快速排序及自定义函数-创新互联
链接地址：http://myzitong.com/article/hhdpc.html

其他资讯