個人博客地址

基礎(chǔ)篇

基礎(chǔ)概念

復(fù)雜性評估

• 時間復(fù)雜度：評估執(zhí)行程序所需要的時間。可以估算出程序?qū)τ嬎銠C處理器的使用程序
• 空間復(fù)雜度：評估執(zhí)行程序 所需的存儲空間?？梢怨浪愠龀绦?對計算機內(nèi)存的使用程度

“復(fù)雜度”大多數(shù)情況下是指的時間復(fù)雜度

大O表示法：大O表示法是一種評估算法效率的“標尺”，以諸如、的形式表示算法的效率，其中n為問題的數(shù)據(jù)大小。

常用的復(fù)雜度比較

5	2	2	10	25	32	120
10	3	3	30	100	1024	3628800
20	4	4	80	400	1048576	約
50	5	7	250	2500	約	約
100	6	10	600	10000	約	約
1000	9	31	9000		約	約
	13	100			約	約
	16	316			約	約
	19	100			約	約

穩(wěn)定排序

是指在出現(xiàn)多次相同數(shù)據(jù)時，能保證穩(wěn)定輸出的排序算法

初等排序

排序	最好	最壞	穩(wěn)定情況
插入排序	N（有序）		穩(wěn)定
冒泡排序			穩(wěn)定
選擇排序			不穩(wěn)定
希爾排序			不穩(wěn)定

插入排序

** 步驟：**

1. 從第一個元素開始，該元素可以認為已經(jīng)被排序
2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到該位置中
6. 重復(fù)步驟2

img

void InsertSort(int a[],int n)
{
    for(int i=0;i<n;i++)
    {
        int j=i-1;
        if(a[i]<a[i-1]){ //若第i個元素小于第i-1個元素,移動有序序列插入------大于的話則直接插入 
        int swap=a[i];  //存儲將要排序的元素 
        a[i]=a[i-1];   //向后移動一個元素 
        while(swap<a[j])//查詢將要插入的位置 
        {
            a[j+1]=a[j];
            j--;       //元素后移 
        }
        a[j+1]=swap;//循環(huán)結(jié)束 插入到指定位置 
    }    
    }
}

冒泡排序

** 步驟：**

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

image

#include<stdio.h>
void BuddleSort(int a[],int n){
     
    for(int i=0;i<n-1;i++){
        for( int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1]){
                int swap=a[j];
                a[j]=a[j+1];
                a[j+1]=swap;
            }
        }
    }
} 

選擇排序

步驟：

1. 未排序序列中找到最小元素，存放到排序序列的起始位置。
2. 再從剩余未排序元素中繼續(xù)尋找最小元素，然后放到排序序列末尾。
3. 以此類推，直到所有元素均排序完畢。

image

void SelectSort(int a[],int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min=i;  //存放數(shù)組最小值的位置 
        
        for(int j=i+1;j<n;j++)
        {
            if(a[j]<a[min]){
                min=j;   //找出最小值，并記錄位置 
            }
         } 
         if(min!=i) //最小元素與第i個元素互換位置 
         {
            int swap=a[min];
             a[min]=a[i];
             a[i]=swap;
         }
    }
}

希爾排序

步驟：

1. 選取間隔為g的元素進行插入排序
2. 縮小g的范圍，新的g與原g互質(zhì)
3. 重復(fù)執(zhí)行步驟1，2
4. 最后選取g=1執(zhí)行一次插入排序

image

insertionSort(A,n,g){
    for i = g to n-1
        v=A[i]
        j=i-g
        while j>=0 && A[j]>v
            A[j+g]=a[j]
            j=j-g
            cnt++
         A[j+g]=v
}
shellSort(A,n){
    cnt=0;
    m=?;
    g[]={……,1};
    for i=0 to m-1
        insertionSort(A,n,g[i])
}

注： 最后一定要執(zhí)行一次g=1的普通 插入排序 ，確保正確

參考教材：《挑戰(zhàn)程序設(shè)計競賽2 算法數(shù)據(jù)結(jié)構(gòu)》

參考資料：https://www.cnblogs.com/xaimicom/p/9189471.html