經典算法

算法

算法（Algorithm）是指解題方案的準確而完整的描述，是一系列解決問題的清晰指令。簡單來說，算法就是解決一個問題的具體方法和步驟。在計算機科學中，算法是程序設計的核心，它決定了程序如何執行特定的任務。

算法的性能評價通常包括時間復雜度和空間復雜度兩個方面。時間復雜度衡量了算法執行所需的時間資源，而空間復雜度則衡量了算法執行所需的存儲資源。

1.時間復雜度

它衡量了一個算法執行所需時間的相對量度。

時間復雜度描述了算法運行時間與輸入規模之間的增長關系。

間復雜度并不是算法執行所需的實際時間，因為實際時間會受到很多因素的影響，如處理器速度、編譯器優化、系統負載等。因此，時間復雜度是算法執行時間隨輸入規模增長而增長的“趨勢”或“速率”的度量。

計算方式：
- 時間(空間)復雜度計算公式：T(n)=O(f(n));
- n ：數據規模大小
- T(n) ：代碼的執行時間
- f(n) ：每一行代碼的執行的次數的總和（平常只關心量級最大的代碼次數，忽略低階、常數、系數)
常見的時間復雜度有：
- 常數時間復雜度 O(1)：算法的執行時間不隨輸入規模的增長而增長，即無論輸入數據有多大，算法的執
  
  行時間都是固定的。（數組訪問）
- 線性時間復雜度 O(n)：算法的執行時間與輸入規模呈線性關系，即算法的執行時間隨著輸入數據量的增
  
  加而線性增長。（單層循環）
- 對數時間復雜度 O(log n)：算法的執行時間與輸入規模的對數成正比。（二分查找）
- 線性對數時間復雜度 O(n log n)：算法的執行時間隨輸入規模的增長而線性對數增長。（快速排序、歸
  
  并排序）。
- 平方時間復雜度 O(n^2)：算法的執行時間與輸入規模的平方成正比。（雙重循環）。

2.空間復雜度

空間復雜度（Space Complexity）是對一個算法在運行過程中臨時占用存儲空間大小的量度。具體來
說，它表示算法在計算機內存中執行時所需額外空間的度量，記作S(n)，其中n是問題的規模（即輸入數
據的大小）。這個空間包括算法在執行時所使用的所有額外存儲空間，如變量（包括靜態變量和動態變量）、遞歸調用棧、以及輸入輸出數據所占據的存儲空間等。

計算方式類似于時間復雜度.

1 排序

排序算法是計算機程序設計中的一種重要操作，旨在將一組數據元素（或記錄）按照某種關鍵字的大小順序，遞增或遞減地排列起來。排序算法在數據處理、數據庫管理、搜索引擎優化等多個領域都有廣泛應用

注意：下文中的排序默認是升序！

1.1冒泡排序

通過重復遍歷待排序的序列，從數組一端開始不斷比較相鄰元素的大小，并在必要時交換它們的位置，
直到沒有元素需要交換為止。

在這里插入圖片描述

示例時間復雜度O(n^2)

#include <iostream>
using namespace std;//冒泡排序 時間復雜度O(n^2)
void bubble_sort(int *arr, int size)
{//每進行一輪排序，最大的元素都會被安排再最右邊 size - 1是因為比較左右兩個元素，最后一個元
// 素不用比較int tmp = 0;for(int i = 0; i < size - 1; i++){// / 對最大元素左邊的所有數據重新排序，再找到其中最大的for(int j = 0; j < size - 1 - i;  j++){if(arr[j] > arr[j+1]){// 交換 arr[j] 和 arr[j+1]tmp = arr[j+1];arr[j+1] =  arr[j];arr[j] = tmp;}   }}
}int main()
{int arr[5] = {5, 2, 1, 3, 4 };bubble_sort(arr, 5);for(int i = 0; i < 5; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

1.2 選擇排序

首先在序列中找到最小元素，放到序列的起始位置作為已排序序列；
然后，再從剩余未排序元素中繼續尋找最小元素，放到已排序序列的末尾；
重復上述步驟，直到所有元素均排序完成。

在這里插入圖片描述

示例時間復雜度O(n^2)

// 選擇排序
void select_sort(int *arr, int size)
{int temp = 0;// 記錄最小索引for(int i = 0; i < size - 1; i++){//假設當前索引就是iint MinNum = i;for(int j = MinNum + 1; j < size; j++){if(arr[j] < arr[MinNum]){MinNum = j;}}if(MinNum != i){temp = arr[MinNum];arr[MinNum] = arr[i];arr[i] = temp;}}
}
int main()
{int arr1[5] = { 2, 0, 1,3, 4 };select_sort(arr1, 5);for(int i = 0; i < 5; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

1.3 插入排序

插入排序的基本思想是將數組分為已排序和未排序兩部分，初始時，已排序部分只包含第一個元素，未
排序部分包含其余元素。

然后，依次將未排序部分的元素插入到已排序部分的適當位置，直到未排序部
分為空。

在這里插入圖片描述

示例時間復雜度O(n^2)

// 插入排序
void insertionSort(int *arr, int size)
{//默認第一個元素已經是有序的了for(int i = 1; i < size ;i++){// 有序位置int key =  arr[i];// 從后往前// j = i - 1 是用來從后往前比較的，這里的“后”是相對于當前要插入的元素 arr[i] 的位置而言的int j =  i - 1;while (j > 0 &&  arr[j] > key){arr[j + 1] = arr[j];j--; }arr[j + 1] = key;}
}
int main()
{ int arr2[5] = { 2, 6, 5, 3, 4 };insertionSort(arr2, 5);for(int i = 0; i < 5; i++){cout << arr2[i] << " ";}cout << endl;return 0;
}

***1.4 快速排序（面試會問）

首先從序列中任意選擇一個元素，把該元素作為基準（一般是第一個或者最后一個元素）。

然后將小于等于基準的所有元素都移到基準的左側，把大于樞軸的元素都移到樞軸的右側，。基準元素不屬于任一子序列，并且基準元素當前所在位置就是該元素在整個排序完成后的最終位置。

這樣一個劃分左右子序列的過程就叫做快速排序的一趟排序，或稱為一次劃分。遞歸此劃分過程，直到整個序列有序。

算法圖解

首先給出一個無序序列[3, 5, 4, 1, 2]，選取一個元素為基準元素，一般選擇序列第一個元素（或最后一個元素），以3作為基準，然后設置兩個指針，一個left指針指向左側第一個位置，一個right指針指向右側最后一個位置。

在這里插入圖片描述

首先取出基準元素3，此時left指向的位置留出一個空位。為了好理解說是空位，其實是指向基準值

我們規定，指向**空(基準值)**的指針不移動。

此時應該操作right指針

如果right指針指向的元素大于基準元素3，那么right指針左移；
如果right指針指向的元素小于基準元素3，那么將right指針指向的元素放到left指針指向的空

位處（保證左邊的元素都比基準小，右邊元素都基準大），同時left指針右移。

顯然，當前right指向的2小于3，所以把2放到left指向的位置，此時right指向為空。

在這里插入圖片描述

right指針指向空，操作left指針，對left指針：如果left指針指向元素小于基準元素3，那么left指針右移

對left指針：

如果left指針指向元素小于基準元素3，那么left指針右移；
如果left指針指向元素大于基準元素3，那么把left指針指向的元素放到right指向的空位處。

在這里插入圖片描述

此時，5大于3，元素放到right，同時right指針左移 )

在這里插入圖片描述

left指針指向空，操作right指針，此時，1小于3，元素放到left，同時left指針右移

!
%BA%8F%5C5.png&pos_id=img-QZQXfVx8-1747289875468)

right指針指向空，操作left指針，此時，4大于3，元素放到right，同時right指針左移

在這里插入圖片描述

left指針和right指針指向同一個位置，此時將基準元素插入。

在這里插入圖片描述

最后得到的序列，3左側全部是小于3的元素，3右側全部是大于3的元素

然后重復上述步驟，對基準左右兩邊同時進行快速排序

`示例

時間復雜度O(n logn）`

#include <iostream>
using namespace std;//冒泡排序 時間復雜度O(n^2)
void bubble_sort(int *arr, int size)
{//每進行一輪排序，最大的元素都會被安排再最右邊 size - 1是因為比較左右兩個元素，最后一個元
// 素不用比較int tmp = 0;for(int i = 0; i < size - 1; i++){// / 對最大元素左邊的所有數據重新排序，再找到其中最大的for(int j = 0; j < size - 1 - i;  j++){if(arr[j] > arr[j+1]){// 交換 arr[j] 和 arr[j+1]tmp = arr[j+1];arr[j+1] =  arr[j];arr[j] = tmp;}   }}
}// 選擇排序
void select_sort(int *arr, int size)
{int temp = 0;// 記錄最小索引for(int i = 0; i < size - 1; i++){//假設當前索引就是iint MinNum = i;for(int j = MinNum + 1; j < size; j++){if(arr[j] < arr[MinNum]){MinNum = j;}}if(MinNum != i){temp = arr[MinNum];arr[MinNum] = arr[i];arr[i] = temp;}}
}// 插入排序
void insertionSort(int *arr, int size)
{//默認第一個元素已經是有序的了for(int i = 1; i < size ;i++){// 有序位置int key =  arr[i];// 從后往前// j = i - 1 是用來從后往前比較的，這里的“后”是相對于當前要插入的元素 arr[i] 的位置而言的int j =  i - 1;while (j > 0 &&  arr[j] > key){arr[j + 1] = arr[j];j--; }arr[j + 1] = key;}
}// 快速排序
void quick_sort(int *p_num, int size)
{int base =  *p_num; //基準，選在開頭int *left = p_num;      //左指針int *right = p_num + size - 1;      //右指針int temp = 0;// int *temp  == nullptr error// temp是一個指針，它用于存儲內存地址。在你的代碼中，你試圖用 *temp 來存儲交換的值，// 但 temp 沒有指向一個有效的內存地址，所以這種操作是非法的。這就像你有一個指向空房間的門（指針），但你卻試圖把東西放進這個不存在的房間里if(size <= 1){return; //遞歸出口}while( left < right)//指針比較{if( *left > *right)//指針指向的值比較{temp = *left;*left  = *right;*right =  temp;}// 等于基準值的指針不移動// 左指針等于基準右指針前移if( *left == base){right--;}// 右指針等于基準左指針后移else{left++;}}// 遞歸調用基準值左邊quick_sort(p_num, left - p_num);quick_sort(right + 1,size - 1 - (left - p_num));}int main()
{int arr[5] = {5, 2, 1, 3, 4 };bubble_sort(arr, 5);for(int i = 0; i < 5; i++){cout << arr[i] << " ";}cout << endl;int arr1[5] = { 2, 0, 1,3, 4 };select_sort(arr1, 5);for(int i = 0; i < 5; i++){cout << arr1[i] << " ";}cout << endl;int arr2[5] = { 2, 6, 5, 3, 4 };insertionSort(arr2, 5);for(int i = 0; i < 5; i++){cout << arr2[i] << " ";}cout << endl;int arr3[5] = { 7, 6, 10, 8, 9 };quick_sort(arr3, 5);for(int i = 0; i < 5; i++){cout << arr3[i] << " ";}cout << endl;return 0;
}

問題 int *temp == nullptr不能存儲元素

temp是一個指針，它用于存儲內存地址。在你的代碼中，你試圖用 *temp 來存儲交換的值，
但 temp 沒有指向一個有效的內存地址，所以這種操作是非法的。這就像你有一個指向空房間的門（指針），但你卻試圖把東西放進這個不存在的房間里2 查找

2 查找

查找算法是計算機科學中用于在數據結構中查找特定元素的算法。

二分查找

在有序數組中，通過不斷將數組分成兩半，比較中間元素與目標值的大小，從而確定下一步的查找范圍。

示例時間復雜度O(log n) 在這里插入圖片描述

在這里插入圖片描述

int* half_search(const int *p_num, int size, int num)
{// 開始位置const int *p_start = p_num;// 結束位置const int* p_end = p_num + size - 1;// 中間位置const int* p_mid = nullptr;while (p_start <= p_end){// 中間位置就是開始位置加(結束位置 -開始位置) /2p_mid  = p_start + (p_end - p_start ) / 2 ;          if ( *p_mid ==  num){    return (int*)p_mid;}//中間值比要找的值小else if( *p_mid < num  ){      //在后半部分找p_start = p_mid + 1;}//中間值比要找的值大else {//在前半部分找p_end = p_mid - 1;}}
// 遍歷完了沒有return nullptr;
}
int main()
{int arr[5] = {1, 2, 3, 4, 5 };int *p = half_search(arr3, 5 , 4);cout << *p << " ";return 0;
}