数据排序 第1课时

[引入]

​ 信息获取后通常需要进行处理，处理后的信息其目的便于人们的应用。信息处理方法有多种，通常有数据的排序、查找、插入、删除、归并等操作。

[STD库的排序方法]

​ STD库中存在一个排序函数，叫sort，这个函数在库algorithm(通过代码#include<algorithm>导入)

​ sort函数的使用方法

1
sort(头指针,尾指针);

​ 举例:将a数组的下表为1~n项排序

1
sort(a+1,a+n+1);//下表从0开始
[选择排序]
<基本思想>

​ 每一趟从待排序的数据元素中选出最小(或最大)的一个元素，顺序放在待排序的数列的最前面，直到全部待排序的数据元素都排序完。

<代码实现>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[20005];
void psort(int l, int r) {					//此函数的意义:排序a数组的l~r的位置的元素
	for(int i = l; i < r; i++) {			//j=i+1，当i=r时j(i+1)>r所以,i的枚举是从l~(r-1)
		minn = i;
		for(int j = i + 1; j <= r; j++) {
			if(a[j] < a[minn]) {			//如过找到比a[minn]小的元素,就标记给minn,如果是逆序排序就将小于号改为大于号
				minn = j;
			}
		}
		if(minn != i) {						//如果i~r中最小的数不是i本身,那么i这个位置的数就与最小的数进行替换
            int k = a[minn];				//进行替换
            a[minn] = a[i];
            a[i] = k;
        }
	}
    return;
}
[冒泡排序]
<基本思想>

​ 冒泡排序的基本思想 冒泡排序是交换排序中一种简单的排序方法。 它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，使最大(或最小)的元素冒到最后的那个位置，最终达到有序化。

<代码实现>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[20005];
void msort(int l, int r) {
    for(int i = r; i > l; i--) {
        bool flag = true;							//判断序列是否有序
        for (int j = l; j < i; j++) {
            if(a[j] > a[j + 1]) {					//逆序排序将大于号改为小于号
                int k = a[i];						//交换
                a[i] = a[j];
                a[j] = k;
                flag = false;						//进行交换说明不是有序的
            }
        }
        if(flag) {									//如果使有序的就结束排序
            break;
        }
    }
    return;
}
[今日作业]

​ 完成下列题目的代码,禁止照抄上面代码(三种方法都使用一遍),写完请发给我。

​ 谁考了第k名

【题目描述】

在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第k名学生的学号和成绩。

【输入】

第一行有两个整数，分别是学生的人数n（1≤n≤100），和求第k名学生的k（1≤k≤n）。

其后有n行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。

【输出】

输出第k名学生的学号和成绩，中间用空格分隔。（注：请用%g输出成绩）

【输入样例】
1
2
3
4
5
6
5 3 
90788001 67.8 
90788002 90.3 
90788003 61 
90788004 68.4 
90788005 73.9
【输出样例】
1
90788004 68.4
关于

本篇文章作者是serverDream。