sort(地址开头,地址结尾+1);默认从小到大排序

int a[10]={9,8,7,6,5,4,3,2,1,0};

//下标：    0 1 2 3 4 5 6 7 8 9

sort(a+3,a+7);//9 8 7 [3 4 5 6] 2 1 0

从大到小排序

bool cmp(int a,int b){

   return a>b;

}

int a[10]={0,1,2,3,4,5,6,7,8,9};

sort(a+3,a+7,cmp);//0 1 2 [6 5 4 3] 7 8 9

sort是在通常情况下，排序最快，也是最方便的解题方案

sort 底层原理：快速排序

快速排序流程：

1、标兵（通常选第一个元素，也叫基准数据）

2、哨兵*2，分别标记排序范围两端

   先从右向左走，直到当前元素小于标兵或哨兵相遇，停止

   再从左向右走，直到当前元素大于标兵或哨兵相遇，停止

   交换两个哨兵对应的数据，再继续相向而行，直到哨兵相遇

3、交换哨兵与标兵对应的元素

int a[9]={6,5,7,3,1,8,9,2,4};//一轮：254316987

   //    0 1 2 3 4 5 6 7 8

int t=0;

int i=0,j=8;

while(i!=j){

   while(a[j]>=a[t]&&i!=j) j--;

   while(a[i]<=a[t]&&i!=j) i++;

   if(i!=j) swap(a[i],a[j]);

}

swap(a[t],a[i]);

//快速排序

void qsort(int left,int right){

   if(right-left<2) return ;

   int t=left;

   int i=left,j=right;

   while(i!=j){

       while(a[j]>=a[t]&&i!=j) j--;

       while(a[i]<=a[t]&&i!=j) i++;

       if(i!=j) swap(a[i],a[j]);

   }

   swap(a[t],a[i]);//left~i i~right

   qsort(left,i-1);

   qsort(i+1,right);

}

时间复杂度

在执行代码前，估算程序执行时间的一个标准

用 T=O(n)     y=f(x)

T代表程序执行的时间，O是函数名，n是题目的数据量

随着n逐渐增大，T也会逐渐增大

具体增大的幅度不同也就是时间不同

通常将循环最内层的代码当作基本代码，基本代码执行的次数就是T（估算）

输入一个n，输入n个数字，将这里面的奇数输出

for(int i=0;i<n;i++){

   if(i%2==1) cout<<i<<" ";

}

T=O(n)

二维数组，输出对角线的数据

for(int i=0;i<n;i++){

   for(int j=0;j<n;j++){

       if(i==j||i+j==n-1) cout<<a[i][j]<<" ";

   }

}

T=O(n^2)

00 01 02 03 04

10 11 12 13 14

20 21 22 23 24

30 31 32 33 34

40 41 42 43 44

斐波那契数列

int fei(int n){

   if(n<2) return 1;

   return fei(n-1)+fei(n-2);

}

T=O(2^n) 由于一分二时间复杂度太高，所以递归形式通常不能处理较大的数据量

冒泡排序时间复杂度：

for(int i=0;i<n;i++){

   for(int j=0;j<n-i;j++){

   }

}

n n-1 n-2 n-3  ... 1

等差数列求和公式   (n+1)*n/2=n^2/2+n/2 当n足够大的时候，接近n^2->T=O(n^2)

二分法时间复杂度：

如果程序的循环范围在不断折半，循环次数就会大幅度降低

1000       1000     10

1000000    1000000  20

T=O(logn)  数学对数函数

桶排序时间复杂度：

O(n) 或 O(1) 如果不计入输入的时间，数据量，与排序时间没关系

这样的时间复杂度为常数级，通常记作O(1)

快速排序时间复杂度：

通常记为 T=O(nlogn)

如果每次选择的基准都恰好是最大的或者最小的，失去了折半功能，时间复杂度为O(n^2)

T=O(n!)

O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(2^n)>O(n!)

如果代码超时，可以根据这个排序进行优化