排序

把各类排序做一遍梳理。

冒泡排序

//bubble sort
void sort(int num[]){
    int length = sizeof(num)/sizeof(num[0]);//获取数组长度
    int temp;
    for(int i  = 0;i < length-1; i++){
        for(int j = 0; j< length-1-i; j++){//注意这里，每一轮j比前一轮到达的位置递减
            if(num[j] > num[j+1]){
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }
}

双层循环，时间复杂度是 O(n2)。

优化

比如说给你一个有序的数组，或者是部分有序的数组，你怎么把它的运行时间降下来
我们可以设置一个标记位，如果在某一轮中从来没有交换过前后两个数，我们认为此时就已经有序了，没必要再进行之后的循环了。

int length = sizeof(num)/sizeof(num[0]);//注意，计算数组长度必须要在main函数里面，而不能将num做参数传递之后再计算。

void OptimizeSort(int num[],int length){
    int temp;
    for(int i = 0; i < length - 1 ; i++){
        bool flag = true;
        for(int j = 0; j < length - 1 -i; j++){
            if(num[j] > num[j+1]){
                temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
                flag = false;
            }
        }
          if(flag){//经过一轮后，flag标志没有改变，说明有序，可以退出循环
              break;
          }
    }
}

当将数组作为实参传递到另一个函数中时, 另一个函数的形参相当于一个指针变量, 因为将数组的名作为实参时, 就是将数字的首地址作为实参, 所以在 test 函数中输出的sizeof(arr)其实得到的是一个整型数组指针的长度(所占的字节数), 所以结果是 8, 再用其除以 int 所占的字节数(4), 结果就是 2。ps：这里 sizeof(&arr)=8，sizeof(arr)=实际长度*4
要想用函数计算数组的长度，可以使用函数模板。

#include<iostream>
using namespace std;

template<typename T>
int count(T& x)
{
    int s1 = sizeof(x);
    int s2 = sizeof(x[0]);
    int result = s1 / s2;
    return result;
}
int main()
{
    int a[] = { 1,2,3 };
    cout << count(a);
    return 0;
}

为什么可以呢？首先我们需要知道函数模板是什么。

函数模板

函数模板不是一个实在的函数，编译器不能为其生成可执行代码。定义函数模板后只是一个对函数功能框架的描述，当它具体执行时，将根据传递的实际参数决定其功能。
C++ 语言支持模板。有了模板，可以只写一个 Swap 模板，编译器会根据 Swap 模板自动生成多个 Sawp 函数，用以交换不同类型变量的值。
函数模板的写法如下：

template <class 类型参数1, class类型参数2, ...>
返回值类型  模板名(形参表)
{
    函数体
}

具体示例：

template <class T>
void Swap(T & x, T & y)
{
    T tmp = x;
    x = y;
    y = tmp;
}

就像这样，它用 T 代替了普通函数定义中的数据类型，代表一种泛化类型。
T 是类型参数，代表类型。
编译器由模板自动生成函数时，会用具体的类型名对模板中所有的类型参数进行替换，其他部分则原封不动地保留。同一个类型参数只能替换为同一种类型。编译器在编译到调用函数模板的语句时，会根据实参的类型判断该如何替换模板中的类型参数。

选择排序

首先，找到数组中最小的元素，拎出来，将它和数组的第一个元素交换位置，第二步，在剩下的元素中继续寻找最小的元素，拎出来，和数组的第二个元素交换位置，如此循环，直到整个数组排序完成。

 int length = sizeof(num)/sizeof(num[0]);
void SelectSort(int num[],int length){

    for(int i = 0;i < length;i++){
        int min = i;//只需要记录最小值的位置即可！
        for(int j = i+1; j < length;j++){
            if (num[min] > num[j]){
                min = j;//更新最小位置
            }
        }
        if(i!=min){
            int temp = num[min];
            num[min] = num[i];
            num[i] = temp;
        }
    }
}

双层循环，时间复杂度和冒泡一模一样，都是 O(n2)。

#

STL 库函数 sort

编写 C++经常需要使用 sort 进行排序，有可能是简单的数组、数字 vector 或者是复杂一点的存放对象的 vector。
C++为了满足用户的需求，在 algorithm 里面封装了 sort 泛型算法。所以使用时，必须#include < algorithm>

template <class RandomAccessIterator>
	void sort (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
	void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

可以看见，sort 原型分为两个，区别在于第一个函数有两个参数，第一个函数有三个参数。
其中两个函数都有的是 RandomAccessIterator 是随机访问迭代器，first 是初始位置，last 是末尾位置，默认使用迭代器引用的 operator < 进行排序。
第二个函数，前两个参数一样，也是用来说明从哪儿到哪儿排序。第三个参数是Compare，意思是使用 comp 这个“方法”对对象进行排序。comp可以是函数对象或者是函数指针。

默认情况

• 两个参数

使用两个参数这应该是最普遍也是最简单的情景，如果只有两个参数，默认使用 operator < 对数组排序，结果为升序。

对数组排序

int arr[] = { 9,8,7,6,5,4,3,2,1 };
sort(arr, arr + 9);

需要注意的是，这里传入的是迭代器，所以要传入头指针和末尾指针（最后一个待排元素的后一个位置）,数组的话，变量名就是起始地址。

对 vector 排序

vector<int> arr;
for(int i = 9;i >0;i--){
    arr.push_back(i);
}
sort(arr.begin(),arr.end());

这里直接传入 vector 的 begin 和 end 两个迭代器就对整个 vector 完成了排序。

对对象排序

如果只使用两个参数的话，要对对象排序，那么只能依靠重载运算符来实现。而且必须重载的是 < 关系运算符。

class Test {
public:
    int value;
    Test() : value(0) {};
    Test(int x) : value(x) {};

    // 重载运算符
    bool operator < (const Test& t) {
        if (value < t.value)
            return true;
        return false;
    }
};

int main(){

	vector<Test> arr;
	for (int i = 9; i > 0; i--) {
  	  arr.push_back(Test(i));
	}
	sort(arr.begin(), arr.end());
    for(int i =0;i<arr.size();i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

这样，就根据 Test 类中 value 的值来升序排对象的顺序了。

三个参数排序

先不写了

参考文章

1. https://mp.weixin.qq.com/s?__biz=MzI5MzYzMDAwNw==∣=2247486587&idx=1&sn=7becbafba2658a4c6bf901ee65dd5277&chksm=ec6e7523db19fc358cdaac6686d4d4c5c36309b69352c33f71ece38b90fef50394a5c004cb84&mpshare=1&scene=1&srcid=
2. 视频 | 手撕九大经典排序算法，看我就够了！ - 力扣（LeetCode）的文章 - 知乎 https://zhuanlan.zhihu.com/p/52884590
3. https://blog.csdn.net/qq_46018418/article/details/106341404
4. https://www.cnblogs.com/scyq/p/13053177.html