<2>操作

• 創(chuàng)建棧
• 入棧
• 出棧
• 獲取棧頂元素
• 判空

6.隊(duì)列

（1）隊(duì)列是什么

<1>概念

隊(duì)列是一種只能從表的一端存數(shù)據(jù)另一端取數(shù)據(jù)且遵循FIFO(先進(jìn)先出)原則的線性存儲(chǔ)結(jié)構(gòu)。

• 隊(duì)尾：在隊(duì)列的一端只能插入元素，
• 隊(duì)首：在隊(duì)列的另一端只能刪除元素。

<2>操作

• 入隊(duì)：數(shù)據(jù)元素進(jìn)隊(duì)列的過程稱為 "入隊(duì)"
• 出隊(duì)：出隊(duì)列的過程稱為 "出隊(duì)"。

（2）使用

隊(duì)列一般用來處理與等待相關(guān)的處理。

（3）實(shí)現(xiàn)

考慮到每次出隊(duì)和入隊(duì)都要移動(dòng)隊(duì)首和隊(duì)尾指針。若采用順序存儲(chǔ)，將會(huì)有可能造成順序表前段部分存儲(chǔ)單元的浪費(fèi)。雖說可以采用循環(huán)隊(duì)列的方式復(fù)用存儲(chǔ)單元，若遇到隊(duì)列滿的情況，將隊(duì)列擴(kuò)容比較麻煩。因此建議用鏈表的方式實(shí)現(xiàn)隊(duì)列。

• 順序隊(duì)列：在index=0，入隊(duì)，在index=size-1，為出隊(duì)元素
• 鏈?zhǔn)疥?duì)列：尾部入隊(duì)，頭部出隊(duì)，尾插法。

<1>結(jié)構(gòu)

鏈?zhǔn)疥?duì)列 (技巧：使用啞元)
鏈?zhǔn)降膆ead指向dummy，tail指向尾部，從尾部入隊(duì)，從頭部出隊(duì)。（尾插法）

<2>函數(shù)

• 創(chuàng)建隊(duì)列
• 入隊(duì)
• 出隊(duì)
• 獲取隊(duì)首元素
• 判空

（4）兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

思想：（兩個(gè)棧各司其職）

• stack1作為隊(duì)列的入口，stack2作為隊(duì)列的出口；
• 入隊(duì)列的操作就是入stack1；出隊(duì)列操作：若stack2為空，則將stack1里面的數(shù)據(jù)入棧到stack2中，再出棧，如果stack2不為空則直接出棧。

（5）兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

思想：（空隊(duì)列和非空隊(duì)列的互搗）

• 兩個(gè)隊(duì)列que1和que2不管是插入還是彈出或者查看棧頂元素，總是要保證有一個(gè)隊(duì)列為空。
• 入棧操作：總是往有數(shù)據(jù)的列隊(duì)插入，默認(rèn)兩個(gè)列隊(duì)空時(shí)，往que1插入
• 出棧操作：從非空隊(duì)列中刪除元素并插入到空隊(duì)列中，直到非空隊(duì)列剩下一個(gè)元素，改元素就是出棧的元素。

7.簡單排序算法

（1）qsort

qsort包含在<stdlib.h>頭文件中.

<1>函數(shù)原型

void qsort(s,n,sizeof(s[0]),cmp);

• 參數(shù)
  s：參與排序的數(shù)組名或者也可以理解成開始排序的地址；
  n：參與排序的元素個(gè)數(shù)；
  sizeof：單個(gè)元素的大?。?br> cmp：比較函數(shù)（回調(diào)函數(shù)）

<2>cmp函數(shù)

返回1：左邊放在右邊的后面；-1：左邊的放在右邊的前面。

 int cmp(const void* a,const void* b){
      int l=*(int*)a;
      int r=*(int*)b;
      if(l==r) return 0;
      return l>r?1:-1;
 }

<3>缺點(diǎn)

• 1、快排是不穩(wěn)定的，這個(gè)不穩(wěn)定一個(gè)表現(xiàn)在其使用的時(shí)間是不確定的，最好情況(O(n))和最壞情況(O(n^2))差距太大，我們一般說的O(nlog(n))都是指的是其平均時(shí)間。

• 2、部分排序：如果要對數(shù)組進(jìn)行部分排序，比如對一個(gè)s[n]的數(shù)組排列其從s[i]開始的m個(gè)元素，只需要在第一個(gè)和第二個(gè)參數(shù)上進(jìn)行一些修改:

  void qsort(&s[i],m,sizeof(s[i]),cmp);
  

（2）冒泡排序

<1>原理

從第一個(gè)元素開始比較相鄰的兩個(gè)元素，如果左邊的大于右邊的，就交換這兩個(gè)元素，大的往后移動(dòng)，當(dāng)右邊大于左邊就保持不變。所以每經(jīng)過一次冒泡，就會(huì)找出最大的一個(gè)元素。當(dāng)有n個(gè)元素時(shí)，第一次參與冒泡的元素是n個(gè)，比較n-1次；第二次參與冒泡的元素是n-1個(gè)（最大的元素不再需要排序），比較n-2次，總共需要n-1次冒泡。

<2>代碼

void bubble_sort(int* arr,int n){
    for(int i=0;i<n-1;++i){//總共需要多少趟（n個(gè)元素需要n-1趟）
        for(int j=1;j<n-i;++j){//第i趟需要比較的次數(shù)
            if(arr[j]<arr[j-1]){
                int t=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=t;
            }
        }
    }
}

<3>復(fù)雜度分析

時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定的，排序過程中不改變相同元素的相對位置。

（3）選擇排序

<1>原理

設(shè)定索引為0的元素是最大值max，其索引為maxindex，然后讓max與index等于1...n-1的元素進(jìn)行比較，找到max和maxindex，最后讓max和最后一個(gè)元素進(jìn)行交換，這樣每次選擇，就會(huì)找到當(dāng)前元素的最大值。

<2>代碼

void select_sort(int* arr,int n){
    for(int i=0;i<n-1;++i){//總共需要多少輪
        int max=arr[0];
        int maxindex=0;
        for(int j=1;j<n-i;++j){//找到最大的元素和index
            if(arr[j]>max){
                max=arr[j];
                maxindex=j;
            }
        }
        arr[maxindex]=arr[n-i-1];//交換最大元素和最后一個(gè)元素
        arr[n-i-1]=max;
    }
}

<3>復(fù)雜度

時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)
不穩(wěn)定。

（4）插入排序

打撲克。

<1>原理

• 只含有1個(gè)元素的序列必定是有序的；
• 第1輪：將第2個(gè)元素插入到由第1個(gè)元素組成的序列中，將其與第1個(gè)元素進(jìn)行比較，如果第2個(gè)元素小于第1個(gè)元素，進(jìn)行交換，此時(shí)前兩個(gè)元素組成的序列完成排序。
• 第2輪：將第3個(gè)元素插入到由前兩個(gè)元素組成的有序序列中，將第3個(gè)元素與有序序列的最后一個(gè)元素進(jìn)行比較，如果需要發(fā)生交換，則將第三個(gè)元素替換成有序序列的最后一個(gè)元素，并保存之前的第三個(gè)元素，再將改元素與有序序列的倒數(shù)第二個(gè)進(jìn)行比較，如果不需要交換，則停止，把保存的第三個(gè)元素填到有序序列的倒數(shù)第二個(gè)元素的位置。
• 第 i 輪，將第 i+1 個(gè)元素插入由前 i 個(gè)元素組成的子序列中，依次與第 i、i-1、……、1 個(gè)元素做比較，如果小于則交換位置。由于前 i 個(gè)元素都是有序的，因此一旦出現(xiàn)不大于第 i+1 個(gè)元素的數(shù)即可停止比較，比較次數(shù) ≤ i，此時(shí)前 i+1 個(gè)元素組成的子序列完成排序。

<2>代碼

void insert_sort(int* arr,int n){
    for(int i=1;i<n;++i){//從index=1的元素開始與前面的元素比較，index=0的元素是有序的
        if(arr[i]<arr[i-1]){ //待排元素小于有序序列的最后一個(gè)元素時(shí)，向前插入
            int tmp=arr[i];
            for(int j=i;j>=0;--j){
                if(j>0 && arr[j-1]>tmp){
                    arr[j]=arr[j-1];
                }else{
                    arr[j]=tmp;
                    break;//否則后面的元素都會(huì)變成tmp
                }
            }
        }
    }
}

<3>復(fù)雜度

時(shí)間復(fù)雜度：O(n^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定的，排序過程中不改變相同元素的相對位置。

8.遞歸(Recursion)

（1）概念

<1>定義

遞歸是一種直接或者間接調(diào)用自身函數(shù)。

<2>本質(zhì)

把問題分解成規(guī)?？s小的同類問題的子問題。（遞歸就是函數(shù)的“套娃”）

<3>套路

關(guān)系+出口

• 確定遞歸公式
• 確定邊界條件

<4>示例

• 打印1到10

法1：
void printN(int n){
    if(n<0) return;
    printN(n-1);
    printf("&n=%p:n=%d\n",&n,n);//
}
法2：
int f(int n){
    if(n==1) return 1;
    else return f(n-1)+1;
}
int main(){
    //printN(10);
    for(int i=1;i<11;++i){
        printf("%d ",f(i));
    }
    printf("\n");
}

• 1-n求和

關(guān)系：f(n)=f(n-1)+n
出口：f(1)=1
代碼：
int sum(int n){
      if(n==0) return 0;
      else  return sum(n-1)+n;
}

• 打印數(shù)組

void printN(int* arr,int n,int i){
    if(i==n) return;
    cout<< arr[i]<<endl;
    printN(arr,n,i+1);
}
void printN(int* arr,int n){
    printN(arr,n,0);
}

• 數(shù)組求和

int sumN(int* arr,int n,int i){//i是下標(biāo)，表示從i開始求和
    if(i==n-1) return arr[i];
    else return arr[i]+sumN(arr,n,i+1);
}
int sumN(int* arr,int n){
    return sumN(arr,n,0);
}

• 求數(shù)組的最大值

int maxarr(int* arr,int n,int i){
    if(i==n-1) return arr[i];
    else{
        if(maxarr(arr,n,i+1)>arr[i]){
            return maxarr(arr,n,i+1);
        }else{
            return arr[i];
        }
    }
}

• 斐波那契數(shù)列（*）
  （1）兔子問題

//f(n)=f(n-1)+f(n-2)
//f(1)=1;f(2)=1
int Fibonacci(int n){
    if(n==1 || n==2) return 1;
    //遞歸
    //return Fibonacci(n-1)+Fibonacci(n-2);
    //迭代
    int prev = 1;
    int curr = 1;
    for(int i=3;i<=n;++i){
        int res = prev + curr;
        prev = curr;
        curr = res;
    }
    return curr;
}

（2）爬樓梯
直接使用遞歸可能會(huì)超時(shí)?。⌒枰玫絼?dòng)態(tài)規(guī)劃。?。。?/strong>

（2）遞歸的缺點(diǎn)

<1>空間

遞歸可能耗內(nèi)存。（因?yàn)椋汉瘮?shù)參數(shù)中的每個(gè)變量都會(huì)重新申請內(nèi)存）
可能導(dǎo)致吐核。

<2>時(shí)間

會(huì)很耗時(shí)（尤其對于兩個(gè)或者三個(gè)函數(shù)相加的運(yùn)算），主要原因是會(huì)重復(fù)計(jì)算某些值，會(huì)導(dǎo)致運(yùn)行超時(shí)，解決：使用動(dòng)態(tài)規(guī)劃，申請動(dòng)態(tài)數(shù)組來記錄已經(jīng)計(jì)算過的函數(shù)值。
動(dòng)態(tài)規(guī)劃：解決遞歸性能問題的一種方法。

動(dòng)態(tài)規(guī)劃講解：https://leetcode-cn.com/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/

可以使用time來統(tǒng)計(jì)執(zhí)行時(shí)間。
time ./a.out

9.高級排序算法

（1）歸并排序

<1>原理

分到一定細(xì)度的時(shí)候，每一個(gè)部分就只有一個(gè)元素了，那么我們此時(shí)不用排序，對他們進(jìn)行一次簡單的歸并就好了

<2>步驟

• 1.實(shí)現(xiàn)兩個(gè)有序數(shù)組的合并（*）

  void merge(int* arr,int n,int mid);
  

• 2.拆分并合并數(shù)組（遞歸）

  void merge_sort(int* arr,int n);
  

<3>代碼

//歸并排序
void merge(int*arr,int n,int mid) {
    int temp[n];
    int p=0;//前半部分下標(biāo)
    int q=mid;//后半部分下標(biāo)
    int k=0;//結(jié)果下標(biāo)
    while(p<mid && q<n) {
        if(arr[p] < arr[q]) {
            temp[k]=arr[p];
            p++;
        } else {
            temp[k]=arr[q];
            q++;
        }
        k++;
    }
//上面循環(huán)的優(yōu)化：
    //while(p<mid && q<n) temp[k++]=arr[p]<arr[q]?arr[p++]:arr[q++];
    while(p<mid) temp[k++]=arr[p++];
    while(q<n)  temp[k++]=arr[q++];
    memcpy(arr,temp,n*sizeof(int));
}
//[0,mid) [mid,n)
//分到一定細(xì)度的時(shí)候，每個(gè)部分就只有一個(gè)元素了，那么我們此時(shí)不用排序，只是歸并即可。
void merge_sort(int* arr,int n) {
    if(n<=1) return;//如果是1項(xiàng)的話，就不用再排序了
    int mid = n/2;
    merge_sort(arr,mid);//不包括mid,mid表示個(gè)數(shù)
    merge_sort(arr+mid,n-mid);
    merge(arr,n,mid);
}

<4>復(fù)雜度

• 時(shí)間復(fù)雜度：一共拆分log2(n)次，每次比較n個(gè)元素，一共比較nlog2(n)次。
• 空間復(fù)雜度：需要增加額外空間n+log2(n)(臨時(shí)數(shù)組n和遞歸調(diào)用函數(shù)棧log2(n)),空間復(fù)雜度為O(n)
• 穩(wěn)定

（4）快速排序

<1>理解

以第一個(gè)個(gè)元素為基準(zhǔn)，并且設(shè)置左右兩個(gè)哨兵，右哨兵先走，當(dāng)遇到比基準(zhǔn)小的后，停止，然后左邊的哨兵再走，當(dāng)遇到比基準(zhǔn)大的數(shù)停止，交換左右兩個(gè)哨兵，然后再從右哨兵開始，重復(fù)，直到左右哨兵相遇為止。

<2>代碼

• 遞歸

int partition(int* arr,int n){
    int priot=arr[0];//以第一個(gè)元素為基準(zhǔn)
    int low=0;//從左往右
    int height=n-1;//從右往左
    while(low<height){
        //當(dāng)隊(duì)尾的元素大于等于基準(zhǔn)數(shù)據(jù)時(shí),向前挪動(dòng)high指針
        while(low<height && arr[height]>=priot) height--;
        // 如果隊(duì)尾元素小于tmp了,需要將其賦值給low
        //arr[low]=arr[height];
        // 當(dāng)隊(duì)首元素小于等于tmp時(shí),向前挪動(dòng)low指針
        while(low<height && arr[low]<=priot) low++;
        // 當(dāng)隊(duì)首元素小于等于tmp時(shí),向前挪動(dòng)low指針
        //arr[height]=arr[low];
        if(low<height){
            swap(arr[low],arr[height]);
        }
    }
    // 跳出循環(huán)時(shí)low和high相等,此時(shí)的low或high就是tmp的正確索引位置
    //arr[low]=priot;
    swap(arr[0],arr[low]);
    return low;
}
void quick_sort(int* arr,int n){
    if(n<=1) return;
    int pos=partition(arr,n);
    quick_sort(arr,pos);
    quick_sort(arr+pos+1,n-(pos+1));
}

• 非遞歸
  遞歸的算法主要是在劃分子區(qū)間，如果要非遞歸實(shí)現(xiàn)快排，只要使用一個(gè)棧來保存區(qū)間就可以了。
  一般將遞歸程序改成非遞歸首先想到的就是使用棧，因?yàn)檫f歸本身就是一個(gè)壓棧的過程。

void quicksortnonrecursive(int* arr,int n){
    stack<int> s;
    int low=0;
    int height=n-1;
    if(low<height){
        int pos=partition(arr,n);
        if(pos-1>low){
            s.push(low);
            s.push(pos-1);
        }
        if(pos+1<height){
            s.push(pos+1);
            s.push(height);
        }

        while(!s.empty()){
            int end=s.top();
            s.pop();
            int start=s.top();
            s.pop();
            int mid=partition(arr+start,end-start+1)+start;//因?yàn)檎一鶞?zhǔn)的函數(shù)每次返回的是以0開始的，所以要加上本來的最小索引
            if(mid-1>start){
                s.push(start);
                s.push(mid-1);
            }
            if(mid+1<end){
                s.push(mid+1);
                s.push(end);
            }
        }
    }
}

非遞歸的算法比遞歸實(shí)現(xiàn)還要慢。 因?yàn)檫f歸算法使用的棧由程序自動(dòng)產(chǎn)生，棧中包含：函數(shù)調(diào)用時(shí)的參數(shù)和函數(shù)中的局部變量。如果局部變量很多或者函數(shù)內(nèi)部又調(diào)用了其他函數(shù)，則棧會(huì)很大。每次遞歸調(diào)用都要操作很大的棧，效率自然會(huì)下降。而對于非遞歸算法，每次循環(huán)使用自己預(yù)先創(chuàng)建的棧，因此不管程序復(fù)雜度如何，都不會(huì)影響程序效率。但是對于上面的快速排序，由于局部變量只有一個(gè)mid，棧很小，所以效率并不比非遞歸實(shí)現(xiàn)的低。

<3>復(fù)雜度

• 時(shí)間復(fù)雜度：一共拆分log2(n)次，每次比較n個(gè)元素，一共比較nlog2(n)次。
• 空間復(fù)雜度：需要增加額外空間log2(n)(遞歸調(diào)用函數(shù)棧log2(n)),空間復(fù)雜度為O(log2(n))
• 不穩(wěn)定

（5）希爾排序（Shell排序）

希爾排序比插入排序的優(yōu)勢：
通過分組排序使元素逐漸靠近最終位置，從而減少了插入排序 時(shí)的移動(dòng)次數(shù)。（先粗調(diào)再微調(diào)）

<1>理解

https://blog.csdn.net/qq_39207948/article/details/80006224

<2>代碼

void ShellSort(int* arr,int len){
    int temp,j;
    for(int r=len/2;r>=1;r/=2){//間隔
        //內(nèi)層循環(huán)間距為r,分別比較對應(yīng)元素，當(dāng)r=1時(shí)，就是插入排序。
        for(int i=r;i<len;++i){//多少組（每個(gè)組是相互交替來排的）
            temp=arr[i];
            j=i-r;
            while(j>=0 && arr[j]>temp){
                arr[j+r]=arr[j];
                j -=r;
            }
            arr[j+r]=temp;
        }
    }
}

<3>復(fù)雜度

<4>算法選擇標(biāo)準(zhǔn)