前言

在很多题目中，我们需要对数据进行排序，升序，降序显而易见，那么结构体又要怎么做到呢！

一、如何实现排序

1.1、折半插入排序

1.1.2、思想

顺序地把待排序的序列中的各个元素按其关键字的大小,通过折半查找插入到已排序的序列的适当位置。

1.1.3、程序代码

//折半插入
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;
void BinaryInsertionSort(vector<int>& a, int left, int right)
{
    int low, middle, high;
    int temp;
    int i, j;
    for (i = left + 1; i <= right; i++) {
        temp = a[i];
        low = left;
        high = i - 1;                  //i-1为已排好序列的右边界
        while (low <= high) {
            middle = (low + high) / 2;
            if (a[i] < a[middle])      //将a[i]插入左半区
                high = middle - 1;
            else                       //将a[i]插入右半区
                low = middle + 1;
        }
        for (j = i - 1; j >= low; j--) a[j + 1] = a[j];
        a[low] = temp;
    }
}

void solve() {
    int k;
    vector<int>a;
    while (cin >> k) {
        a.push_back(k);
    }
    BinaryInsertionSort(a, 0, a.size() - 1);
    for (vector<int>::iterator iter = a.begin(); iter != a.end(); iter++) {
        cout << *iter << " ";
    }
}

int main(int argc, char* argv[])
{
    solve();
    return 0;
}

1.1.4、运行结果

1.2、快速排序

1.2.1、思想

• 首先设定一个分界值，通过该分界值将数组分成左右两部分。
• 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值
• 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
• 重复上述过程，通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

1.2.2、程序代码

#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;
void quickSort(vector<int>& a, int low, int high)
{
    if (low < high) {
        int i = low;
        int j = high;
        int key = a[i];
        while (i < j) {
            while (i < j && a[j] >= key) j--;
            if (i < j)a[i] = a[j];
            while (i < j && a[i] < key) i++;
            if (i < j)a[j] = a[i];
            a[i] = key;
            quickSort(a, low, i - 1);
            quickSort(a, i + 1, high);
        }
    }
}

void solve() {
    int k;
    vector<int>a;
    while (cin >> k) {
        a.push_back(k);
    }
    quickSort(a, 0, a.size() - 1);
    for (vector<int>::iterator iter = a.begin(); iter != a.end(); iter++) {
        cout << *iter << " ";
    }
}

1.2.3、运行结果

1.3、归并排序（2-路归并）

1.3.1、思想

将两个或两个以上的有序表合并成一个有序表的过程。

• 第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 第四步：重复步骤3直到某一指针超出序列尾；
• 第五步：将另一序列剩下的所有元素直接复制到合并序列尾；

1.3.2、程序代码：

#include <iostream>
#include <vector>
using namespace std;

//归并排序采用分治的思想，先分后治
vector<int> mergesort(vector<int> before) {
	if (before.size() == 1)return before;         //这是递归出口，二路分割到最后只剩一个元素
	vector<int>left, right, add_left_right;
	//先分
	for (int i = 0; i < before.size() / 2; i++) {
		left.push_back(before[i]);
	}
	for (int i = before.size() / 2; i < before.size(); i++) {
		right.push_back(before[i]);
	}
	//继续递归分割
	left = mergesort(left);
	right = mergesort(right);

	//后治
	int i = 0, j = 0;
	while (i < left.size() && j < right.size()) { //左右两块，进行比较排序
		if (left[i] < right[j]) {
			add_left_right.push_back(left[i]);
			i++;
		}
		else {
			add_left_right.push_back(right[j]);
			j++;
		}
	}
	if (i == left.size()) {                       //左边排好，接着排右边剩下的数
		for (int k = j; k < right.size(); k++) {
			add_left_right.push_back(right[k]);
		}
	}
	if (j == right.size()) {
		for (int k = i; k < left.size(); k++) {
			add_left_right.push_back(left[k]);
		}
	}
	return add_left_right;
}

void solve() {
	int n;
	vector<int> my_array;
	while (cin >> n) {
		my_array.push_back(n);
	}
	my_array = mergesort(my_array);
	vector<int>::iterator iter;
	for ( iter = my_array.begin(); iter < my_array.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
}

int main() {
	solve();
	return 0;
}

1.3.3、运行结果：

二、排序（sort）函数

2.1、语法:

2.2、定义：

sort()函数为链表排序，默认是升序。如果指定compfunction的话，就采用指定函数来判定两个元素的大小。

2.3、自定义函数升序

2.3.1、程序代码：

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;
bool cmp(int a, int b) {
	if (a > b)return false;
	return true;
}
int main(int argc, char* argv[])
{
	int k;
	vector<int> a;
	while (cin >> k) a.push_back(k);
	sort(a.begin(), a.end(), cmp);
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	return 0;
}

2.3.2、运行结果：

2.4、自定义函数降序

2.4.1、程序代码：

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;
bool cmp(int a, int b) {
	if (a > b)return true;
	return false;
}
int main(int argc, char* argv[])
{
	int k;
	vector<int> a;
	while (cin >> k) a.push_back(k);
	sort(a.begin(), a.end(), cmp);
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	return 0;
}

2.4.2、运行结果：

2.5、使用内置函数排序

2.5.1、程序代码：

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
	int k;
	vector<int> a;
	while (cin >> k) a.push_back(k);
	sort(a.begin(), a.end(), greater<int>()); // 降序
	//sort(a.begin(), a.end(), less<int>());  // 升序
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	return 0;
}

2.5.2、运行结果：

2.6、结构体排序

2.6.1、程序代码：

#include <iostream>
#include <algorithm> 
#include <vector>
using namespace std;

typedef struct node {
	int x;
	int y;
}my_Struct;

bool cmp(const my_Struct &first, const my_Struct &second) {
	if (first.x < second.x) return true;
	else if (first.x <= second.x && first.y <= second.y) return true;
	else return false;
}//编写一个排序比较的自定义函数
int main(int argc, char* argv[])
{
	int k, n;
	vector<my_Struct>a;
	cout << "请问你要输入几个数据：";
	cin >> n;
	cout << "请依次输入数据：\n";
	for (int i = 0; i < n; i++) {
		my_Struct b;
		cin >> b.x >> b.y;
		a.push_back(b);
	}
	sort(a.begin(), a.end(), cmp);
	cout << "排序后的数据为：" << endl; 
	for (int i = 0; i < a.size(); i++) {
		cout << a[i].x << " " << a[i].y << endl;
	}
	return 0;
}

2.6.2、运行结果：

总结

本文讲述了c++中使用API(sort)函数进行排序——降序，升序，以及结构体排序，除了本身自带的greater，less可以进行排序外，其他很多地方还是需要自己编写。

如有疑问，敬请留言！
如有错误，敬请指出！