排序算法刷题【两数之和】，C++的sort()排序的使用

一、C++的sort()排序算法

sort()函数整体使用的代码如下所示：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//sort()排序函数的使用
 
//自定义的结构体
typedef struct
{
	int x;
	int y;
}myData;
 
template<typename T>
int* getRandData(int n)
{
	T* ptr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) *(ptr + i) = rand() % 1000;
	return ptr;
}
 
template<typename T>
void getRandData(vector<T>& v, int n)
{
	for (int i = 0; i < n; i++) v.push_back(rand() % 1000);
}
 
template<typename T>
void displayData(T* ptr, int n)
{
	cout << "\r\nArry_data:";
	for (int i = 0; i < n; i++)
	{
		cout << *(ptr + i) << "  ";
	}
}
 
template<typename T>
void displayData(vector<T>& v)
{
	cout << "\r\nVector_data:";
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
}
 
 
template<typename T>
void displayMyData(vector<T>& v)
{
	cout << "\r\nVector_x:";
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i].x << " ";
	}
	cout << "   Vector_y:";
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i].y << " ";
	}
}
 
/* sort()函数对自定义数组的排序使用的规则函数 */
bool cmp(const myData& a, const myData& b)
{
	if (a.x != b.x) return a.x < b.x;
	return a.x > b.x;
}
 
void test()
{
	int* a = NULL;
	int* ind = NULL;
	vector<int> v;
 
	a = getRandData<int>(10);
	ind = getRandData<int>(10);
	displayData<int>(a, 10);
	sort(a, a + 10);      //从小到大排序
	displayData<int>(a, 10);
	sort(a, a + 10, greater<int>());   //从大到小排序
	displayData<int>(a, 10);
	sort(ind, ind + 10, [&](int i, int j) -> bool {
		return a[i] < a[j];
	});               
	displayData<int>(a, 10);
 
	cout << "\r\n";
 
	getRandData<int>(v, 10);
	displayData<int>(v);
	sort(v.begin(), v.end());
	displayData<int>(v);
	sort(v.begin(), v.end(), greater<int>());
	displayData<int>(v);
 
	cout << "\r\n";
	free(a);
	a = NULL;
}
/* sort对自定义数据类型的排序的两种实现方式 */
void test1()
{
	vector<myData> v1, v2;
	for (int i = 0; i < 10; i++)
	{
		myData data;
		data.x = rand() % 10;
		data.y = rand() % 10;
		v1.push_back(data);
		data.x = rand() % 10;
		data.y = rand() % 10;
		v2.push_back(data);
	}
	displayMyData<myData>(v1);
	//自定义的sort()排序，使用自定义的cmp比较函数
	sort(v1.begin(), v1.end(), cmp);
	displayMyData<myData>(v1);
}
 
 
int main()
{
	test();
	return 0;
}

1.1、sort()实现递增排序、递减排序

（1）sort递增排序

    a = getRandData<int>(10);    //创建数组
	ind = getRandData<int>(10);
	displayData<int>(a, 10);
	sort(a, a + 10);             //从小到大排序，数组的首地址、数组最后元素的后一个地址

（2）sort递减排序

    a = getRandData<int>(10);        //创建一个数组
	sort(a, a + 10, greater<int>());   //从大到小排序，传入greater<int>()方法

1.1、sort对自定义数据类型的排序

（1）自定义比较方法函数

#include <iostream>
#include <vector>
#include <algorithm>   //sort()排序函数的头文件
//自定义的结构体
typedef struct
{
	int x;
	int y;
}myData;
 
bool cmp(const myData& a, const myData& b)
{
	if (a.x != b.x) return a.x < b.x;
	return a.x > b.x;
}
 
 
void test1()
{
	vector<myData> v1, v2;
	for (int i = 0; i < 10; i++)
	{
		myData data;
		data.x = rand() % 10;
		data.y = rand() % 10;
		v1.push_back(data);
		data.x = rand() % 10;
		data.y = rand() % 10;
		v2.push_back(data);
	}
	displayMyData<myData>(v1);
	//自定义的sort()排序，使用自定义的cmp比较函数
	sort(v1.begin(), v1.end(), cmp);
	displayMyData<myData>(v1);
}

（2）使用表达式的方式

    int* a = NULL;
	int* ind = NULL;
	vector<int> v;
 
	a = getRandData<int>(10);     //创建数组a
	ind = getRandData<int>(10);   //创建数组ind
    /*
        下面的方法为：对ind数组进行排序，排序的大小按照数组a的大小来。
        最终得到的结果是ind数组的排序数按照a数组值大小的下表排序的
     */
	sort(ind, ind + 10, [&](int i, int j) -> bool {
		return a[i] < a[j];
	});               
	displayData<int>(a, 10);

运行结果：

        a={3，5，4，1，2}

        ind={1，2，3，4，5}

排序之后：

        a={3，5，4，1，2}

        ind={4，5，1，3，2}

二、leetcode的第一题：两数之和

#include <iostream>
#include <vector>
#include <algorithm>   //sort()排序函数的头文件
using namespace std;
 
/* leetcode：两数之和 */
 
class Solution1 {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ind;
        for (int i = 0; i < nums.size(); i++) ind.push_back(i);
        sort(ind.begin(), ind.end(), [&](int i, int j)->bool {
            return nums[i] < nums[j]; });
        int b = 0, e = nums.size() - 1;
        while ((e > b)&&(nums[ind[b]] + nums[ind[e]] != target))
        {
            if (nums[ind[b]] + nums[ind[e]] > target)
                e--;
            else
                b++;
        }
        vector<int> ret;
        if (ind[b] > ind[e])
        {
            ret.push_back(ind[e]);
            ret.push_back(ind[b]);
        }
        else
        {
            ret.push_back(ind[b]);
            ret.push_back(ind[e]);
        }
        return ret;
    }
};
 
 
 
int main()
{
    vector<int> data;
    vector<int> ret;
    data.push_back(2);
    data.push_back(7);
    data.push_back(11);
    data.push_back(15);
    Solution1 s1;
    ret = s1.twoSum(data, 9);
    cout << "ret:" << ret[0] << " " << ret[1];
    return 0;
}