目錄
個人觀點(diǎn)：
排序的概念：
排序的穩(wěn)定性：
內(nèi)排序與外排序：
概念：
排序用到的結(jié)構(gòu)與函數(shù)：
代碼：
最簡單排序的實現(xiàn)：
舉例：
代碼：
時間復(fù)雜度:
冒泡排序：
舉例：
代碼：
時間復(fù)雜度：
在優(yōu)化：
舉例：
代碼：
簡單選擇排序：
思想:
代碼:
時間復(fù)雜度：
直接插入排序：
舉例：
代碼：
時間復(fù)雜度：
希爾排序：
分析：
舉例：
推薦視頻：
代碼：
注意：
堆排序：
堆定義;
舉例：
基本思想：
舉例：
代碼：
歸并排序：
算法思想：
理解圖解：
舉例：
分析一下它的合并操作是如何進(jìn)行的：
代碼實現(xiàn)：
快速排序：
算法思想：
舉例：
代碼：
（僅代表個人）
對于我初學(xué)者來講，排序這個章節(jié)我們注重的思想而不是用法（個人看法而言，因為我刷題量很少，對我來說sort現(xiàn)在夠用），那么我們就先注重這些算法的內(nèi)容思想。
排序的概念：排序的穩(wěn)定性：通俗來講就是相同的關(guān)鍵字，在排序之后，它們的前后關(guān)系不會變
舉例
內(nèi)排序是在整個排序過程中，待排序的所有記錄全部被放置在內(nèi)存中。
外排序是由于排序記錄個數(shù)過多，不能同時防止在內(nèi)存中，整個排序過程需要在內(nèi)外存之間多次數(shù)據(jù)交換才能進(jìn)行
對于內(nèi)排序性能而言：
（1）時間性能
（2）輔助空間
（3）算法復(fù)雜性
內(nèi)排序分為插入排序、交換排序、選擇排序和歸并排序
排序用到的結(jié)構(gòu)與函數(shù)： 代碼：
重慶分公司
重慶分公司
#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len=0;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
cout< 它的基本思想就是相鄰兩兩比較，有冒泡思想但不是冒泡排序
舉例：
下標(biāo)從1開始
代碼：#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void BubbleSort0(Sqlist*L){
for(int i=1;i<=L->len;i++){
for(int j=1;j<=L->len;j++){
if(L->res[i]>L->res[j])
swaq(L,i,j);
}
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
for(int i=1;i<=L.len;i++)cout< 時間復(fù)雜度高，O(n^2)
從后往前交換，則必定會把相對小的數(shù)向前移動，時間復(fù)雜度提高了
代碼：#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Bubblesort(Sqlist*L){
for(int i=1;ilen;i++){
for(int j=L->len-1;j>=i;j--){
if(L->res[j]>L->res[j+1])
swaq(L,j,j+1);
}
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Bubblesort(&L);
for(int i=1;i<=L.len;i++){
cout< O(n^2)，但是相對來說總歸有優(yōu)化
#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Bubblesort(Sqlist*L){
for(int i=1;ilen;i++){
bool flag=1;
for(int j=L->len-1;j>=i;j--){
if(L->res[j]>L->res[j+1])
swaq(L,j,j+1);
flag=0;
}
if(flag)
break;
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Bubblesort(&L);
for(int i=1;i<=L.len;i++){
cout< 與冒泡排序差不多，只不過不是遇見小的就交換，而是每次循環(huán)遇到最小的才交換
代碼:#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Selectsort(Sqlist*L){
int j,mn;
for(int i=1;ilen;i++){
mn=i;
bool flag=0;
for(j=i+1;j<=L->len;j++){
if(L->res[mn]>L->res[j]){
mn=j;
flag=1;
}
}
if(flag)
swaq(L,i,mn);
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Selectsort(&L);
for(int i=1;i<=L.len;i++){
cout< O(n^2)，但是相對于冒泡排序，總歸有一定的優(yōu)化
直接插入排序： 舉例：此時哨兵（L.res[0]）就起到了作用
#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void swaq(Sqlist*L,int i,int j){
int temp=L->res[i];
L->res[i]=L->res[j];
L->res[j]=temp;
}
void Insertsort(Sqlist*L){
int j;
for(int i=2;i<=L->len;i++){
if(L->res[i]res[i-1]){
L->res[0]=L->res[i];
for(j=i-1;L->res[j]>L->res[0];j--)
L->res[j+1]=L->res[j];
L->res[j+1]=L->res[0];
}
}
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
Insertsort(&L);
for(int i=1;i<=L.len;i++){
cout< O(n^2)，但是時間效率更好點(diǎn)
希爾排序： 分析：希爾排序是在直接插入排序上的優(yōu)化
直接插入排序的最好情況：{2,3,4,5,6}，時間復(fù)雜度為O（n）
最壞情況：{6,5,4,3,2}，時間復(fù)雜度為O（n^2）
希爾排序是將一個數(shù)組分為若干個子序列，然后各自排序然后合并，實現(xiàn)基本有序
基本有序，就是小的關(guān)鍵字基本在前面，大的關(guān)鍵字基本在后面
采用跳躍式分割策略。。。
舉例：
排序算法：希爾排序【圖解+代碼】_嗶哩嗶哩_bilibili
代碼：#includeusing namespace std;
const int N=1e3+10;
int n;
typedef struct{
int res[N];
int len;
}Sqlist;
void shellsort(Sqlist*L){
int i,j,k=0;
int lon=L->len;
do{
lon=lon/3+1;
for(i=lon+1;i<=L->len;i++){
if(L->res[i]res[i-lon]){
L->res[0]=L->res[i];
for(j=i-lon;j>0&&L->res[0]res[j];j-=lon){
L->res[j+lon]=L->res[j];
}
L->res[j+lon]=L->res[0];
}
}
}while(lon>1);
}
int main(){
Sqlist L;
cin>>n;
for(int i=1;i>L.res[i];
L.len++;
}
shellsort(&L);
for(int i=1;i<=L.len;i++){
cout< 增量序列的最后一個增量必須等于1才行
堆排序： 堆定義;其實就是特殊的完全二叉樹
舉例：
大頂堆，所有結(jié)點(diǎn)大于其左右孩子結(jié)點(diǎn)，小頂堆反之
基本思想：將待排序的序列構(gòu)造成一個大頂堆。此時整個序列的大值就是堆頂?shù)母Y(jié)點(diǎn)
將它移走（其實就是將其與堆數(shù)組末尾元素交換，此時末尾元素就是大值），然后將剩余的n-1
個序列重新構(gòu)造一個堆，這樣就會得到n個元素中的次大值，反復(fù)執(zhí)行，便能得到一個有序序列
舉例：（建樹）
是利用歸并的思想實現(xiàn)的排序方法，通俗理解起來就是
對于一個無序的數(shù)組，先讓子序列為1的序列兩兩歸并，然后讓子序列為2的序列兩兩歸并，以此類推
理解圖解：
舉例：
通過一趟排序?qū)⒋庞涗浄指畛蓛刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，然后對這兩部分繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序的目的
舉例：
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
