2.排序和查找

文章目录

排序

内定义数据排序

对输入的n个数进行排序自定义数据排序

成绩排序整数奇偶排序线性排序--计数排序

[sort(HDU 1425)](http://acm.hdu.edu.cn/showproblem.php?pid=1425) 逆序数对--归并排序

逆序数对[Brainman(POJ 1804)](http://poj.org/problem?id=1804) 第K大数---快速排序

快速排序第k大数查找

线性查找 O(n)

查找二分查找 O(logn)

自定义系统自带散列查找 O(1)

自定义系统自带：unordered_map

排序内定义数据排序对输入的n个数进行排序

#include 
#include
using namespace std;

int arr[100];

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[i]);
		}
		//左闭右开，默认升序
		sort(arr, arr + n);
		//输出
		for (int i = 0; i < n; i++) {
			printf("%d ", arr[i]);
		}
		printf("n");
	}

}

自定义数据排序

设计比较函数定义大小关系成绩排序

使用比较函数

#include 
#include
using namespace std;

struct Student {
	int number;
	int score;
};

Student arr[100];

bool Compare(Student x, Student y) {
	//按照学生的成绩从小到大进行排序
	//如果学生的成绩相同，则按照学号的大小进行从小到大排序。
	if (x.score == y.score) {
		return x.number < y.number;
	} else {
		return x.score < y.score;
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &arr[i].number, &arr[i].score);
	}
	sort(arr,arr+n,Compare);
	for (int i = 0; i < n; i++) {
		printf("%d %dn", arr[i].number, arr[i].score);
	}


	return 0;

}

重新定义大小关系

#include 
#include
using namespace std;

struct Student {
	int number;
	int score;
    //重载运算符
	bool operator<(Student student) const {
		if (score == student.score) {
			return number < student.number;
		} else {
			return score < student.score;
		}
	}
};

Student arr[100];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &arr[i].number, &arr[i].score);
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		printf("%d %dn", arr[i].number, arr[i].score);
	}


	return 0;

}

整数奇偶排序

#include 
#include
using namespace std;

int arr[10];

bool Compare(int x, int y) {
	if (x % 2 == 1 && y % 2 == 1) {
		return x > y; //两个数都为奇数从大到小排列
	} else if (x % 2 == 0 && y % 2 == 0) {
		return x < y; //两个数都为偶数从小到大排列
	} else if (x % 2 == 1 && y % 2 == 0) {
		return true;// 两个数奇偶性不同，奇数在前，偶数在后
	} else {
		return false;
	}

}
int main() {

	while (scanf("%d", &arr[0]) != EOF) {
		for (int i = 1; i < 10; i++) {
			scanf("%d", &arr[i]);
		}
		sort(arr, arr + 10, Compare);
		for (int i = 0; i < 10; i++) {
			printf("%d ", arr[i]);
		}
		printf("n");
	}

	return 0;

}

线性排序–计数排序

5	3	2	4	3	3	2	7	7	1

待排序数	0	1	2	3	4	5	6	7	8	9
出现的次数	0	1	2	3	1	1	0	2	0	0

sort(HDU 1425)

#include 
#include
#include
using namespace std;

const 	int MAXN = 1e6 + 10;
const   int RANGE = 5e5;
//待排序数,处于区间[-500000,500000]的整数
int arr[MAXN];
//记录待排序数 出现的次数，下标为待排序数，值为出现的次数
int number[MAXN];

int main() {
	int n, m;
	while (scanf("%d%d", &n, &m) != EOF) {
		//每轮将辅助数组number清空 
		//给定地址后的连续的内存，逐个字节初始化为参数中指出的值，故第三个参数为总的字节数
		memset(number,0,sizeof(number)) ;
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[i]);
			//用元素值作为number数组的下标，值为元素出现的次数，数组下标不能为负数，进行平移 
			number[arr[i]+RANGE]++;
		}
		//将number里面的值还原到arr ,最终结果即为排好序的元素 （从小到大） 
		int index=0;
		for(int i=0;i=n-m;i--){
			if(i==n-m)
			{
				printf("%dn",arr[i]) ;
			}
			else{
				printf("%d ",arr[i]);
			}
		} 
	}

	return 0;

}

逆序数对–归并排序逆序数对

1 2 5 6 7 3 4 7 8 9

i j

#include 
#include
#include
using namespace std;
int arr[100];
int temp[100];
int number;//逆序对
void Combine(int left, int middle, int right) {
	int i = left;
	int j = middle + 1;
	int k = left;
	while (i <= middle && j <= right) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			//当 arr[i] > arr[j],i后面的元素（包括i)的个数为逆序数个数 
			number+=middle-i+1;
			temp[k++] = arr[j++];
		}
	}
	//j扫描到头，i还没有
	while (i <= middle) {
		temp[k++] = arr[i++];
	}
	//i扫描到头，j还没有
	while (j <= right) {
		temp[k++] = arr[j++];
	}
	//将temp数据还原到arr
	for (k = left; k <= right; k++) {
		arr[k] = temp[k];
	}
	return;
}

void MergeSort(int left, int right) {
	if (left < right) {
//		int middle=(left+right)/2;//如果数据比较大，left+right和会超出int上界溢出
		int middle = left + (right - left) / 2;
		MergeSort(left, middle);
		MergeSort(middle + 1, right);
		Combine(left, middle, right);

	}
	return;
}

int main() {

	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	MergeSort(0, n - 1);
	for (int i = 0; i < n; i++) {
		printf("%d ", arr[i]);
	}
	printf("n");
	printf("%dn",number);
	return 0;

}

Brainman(POJ 1804)

#include
#include
using namespace std;
const int MAXN = 1010;
int arr[MAXN];
int temp[MAXN];
int number; //逆序对
void Combine(int left, int middle, int right) {
	int i = left;
	int j = middle + 1;
	int k = left;
	while (i <= middle && j <= right) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		} else {
			//当 arr[i] > arr[j],i后面的元素（包括i)的个数为逆序数个数
			number += middle - i + 1;
			temp[k++] = arr[j++];
		}
	}
	//j扫描到头，i还没有
	while (i <= middle) {
		temp[k++] = arr[i++];
	}
	//i扫描到头，j还没有
	while (j <= right) {
		temp[k++] = arr[j++];
	}
	//将temp数据还原到arr
	for (k = left; k <= right; k++) {
		arr[k] = temp[k];
	}
	return;
}

void MergeSort(int left, int right) {
	if (left < right) {
		//		int middle=(left+right)/2;//如果数据比较大，left+right和会超出int上界溢出
		int middle = left + (right - left) / 2;
		MergeSort(left, middle);
		MergeSort(middle + 1, right);
		Combine(left, middle, right);
	}
	return;
}

int main() {
	int caseNumber;
	scanf("%d", &caseNumber);
	for (int current = 1; current <= caseNumber; current++) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[i]);
		}
		number=0;
		MergeSort(0, n - 1);
		printf("Scenario #%d:n",current); 
		printf("%dnn", number);
	}

	return 0;
}

第K大数—快速排序快速排序

#include
#include
using namespace std;

int arr[100];

int Partition(int left, int right) {
	//随机选取一个数作为枢纽，并和第一个元素位置互换
	int random = left + rand() % (right - left);
	swap(arr[left], arr[random]); //此时枢纽在left位置
	while (left < right) {
		while (left < right && arr[left] <= arr[right]) {
			right--;
		}
		swap(arr[left], arr[right]);//此时枢纽在right位置
		while (left < right && arr[left] <= arr[right]) {
			left++;
		}
		swap(arr[left], arr[right]);//此时枢纽在right位置

	}
	//最后返回枢纽最终的位置 
	return left;

}
void QuickSort(int left, int right) {
	if (left < right) {
		int position = Partition(left, right);
		QuickSort(left,position-1);
		QuickSort(position+1,right); 

	}
}

int main() {

	int n;
	scanf("%d", &n);
	for(int i=0;i 
第k大数 
#include
#include
using namespace std;

int arr[100];

int Partition(int left, int right) {
	//随机选取一个数作为枢纽，并和第一个元素位置互换
	int random = left + rand() % (right - left);
	swap(arr[left], arr[random]); //此时枢纽在left位置
	while (left < right) {
		while (left < right && arr[left] <= arr[right]) {
			right--;
		}
		swap(arr[left], arr[right]);//此时枢纽在right位置
		while (left < right && arr[left] <= arr[right]) {
			left++;
		}
		swap(arr[left], arr[right]);//此时枢纽在right位置

	}
	//最后返回枢纽最终的位置
	return left;

}
int QuickSort(int left, int right, int k) {

	int position = Partition(left, right);
	if (position == k - 1) {
		return arr[position];
	} else if (position < k - 1) {
		return QuickSort(position + 1, right, k);
	} else {
		return QuickSort(left, position - 1, k);
	}


}

int main() {
	int n;
	while (scanf("%d", &n)) {
		for (int i = 0; i < n; i++) {
			scanf("%d", &arr[i]);
		}
		int k;
		scanf("%d", &k);
		printf("%dn", QuickSort(0, n - 1, k));
	}
	return 0;

}
 
查找 
线性查找 O(n) 
查找 
#include
#include
using namespace std;

int arr[100];

bool LinearSearch(int n, int target) {
	bool flag = false;
	for (int i = 0; i < n; i++) {
		if (arr[i] == target) {
			flag = true;
			break;
		}
	}
	return flag;
}

int main() {
	int n;//元素个数
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int m;//查找次数
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int target;
		scanf("%d", &target);
		if (LinearSearch(n, target)) {
			printf("YESn");

		} else {
			printf("NOn");
		}
	}
	return 0;

}
 
二分查找 O(logn) 
自定义 
#include
#include
#include
using namespace std;

int arr[100];

bool BinarySearch(int n, int target) {
	int left = 0;
	int right = n - 1;
	while(left<=right){
		int middle=left+(right-left)/2;
		if(arr[middle]target){
			right=middle-1;
		}
		else{
			return true;
		}
	}
	return false;
}
int main() {
	int n;//元素个数
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr,arr+n);
	int m;//查找次数
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int target;
		scanf("%d", &target);
		if (BinarySearch(n, target)) {
			printf("YESn");

		} else {
			printf("NOn");
		}
	}
	return 0;

}
 
系统自带 
lower_bound: 返回大于或等于目标值的第一个位置upper_bound: 返回大于目标值的第一个位置 
#include
#include
#include
using namespace std;

int arr[100];


int main() {
	int n;//元素个数
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr,arr+n);
	int m;//查找次数
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int target;
		scanf("%d", &target);
		int position=lower_bound(arr,arr+n,target)-arr;
		if (position!=n&&arr[position]==target) {
			printf("YESn");

		} else {
			printf("NOn");
		}
	}
	return 0;

}
 
散列查找 O(1) 
自定义 
#include
#include
#include
using namespace std;

int arr[100];
bool hashTable[10000000] ;

int main() {
	int n;//元素个数
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		hashTable[arr[i]] = true;
	}
	int m;//查找次数
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int target;
		scanf("%d", &target);
		if (hashTable[target]) {
			printf("YESn");

		} else {
			printf("NOn");
		}
	}
	return 0;

}
 
系统自带：unordered_map 
#include
#include
#include
#include
using namespace std;

int arr[100];
unordered_map hashTable;

int main() {
	int n;//元素个数
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
		hashTable[arr[i]] = true;
	}
	int m;//查找次数
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int target;
		scanf("%d", &target);
		if (hashTable[target]) {
			printf("YESn");

		} else {
			printf("NOn");
		}
	}
	return 0;

}

2.排序和查找

C/C++/C#相关栏目本月热门文章