你關(guān)注 我送禮：感謝各位的觀看，別忘了點個贊，同時我在這里還給各位準(zhǔn)備了你們專屬資料，關(guān)注我，獲得私信進裙了解，不要忘記看私信消息啊?；蛘咧苯舆M群有管理員主動找你，回復(fù)[7]之后，你就能拿到各自想要的資料。別忘了去領(lǐng)取啊

定義

假設(shè)含有n個記錄的序列列為(r1,r2,.....,rn). 其相應(yīng)的關(guān)鍵字分別為{k1,k2,......,kn}. 需確定 1,2,......,n 的?一種排序p1,p2,......pn. 使其相應(yīng)的關(guān)鍵字滿?足kp1 <= kp2 <= ...... <= kpn ?非遞減(或 ?非遞增)關(guān)系. 即使得到序列列成為?一個按關(guān)鍵字有序的序列列(rp1,rp2,...,rpn).這樣得出操作稱為排 序

排序分類

• 內(nèi)排序:是在排序整個過程中,待排序的所有記錄全部被放置在內(nèi)存中;
• 外排序:由于排序的記錄個數(shù)太多,不不能同時放置在內(nèi)存,整個排序過程需要在內(nèi)外存 之間多次交換數(shù)據(jù)才能進?行行

準(zhǔn)備工作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

//1.排序算法數(shù)據(jù)結(jié)構(gòu)設(shè)計
//用于要排序數(shù)組個數(shù)最大值，可根據(jù)需要修改
#define MAXSIZE 10000
typedef struct
{
    //用于存儲要排序數(shù)組，r[0]用作哨兵或臨時變量
    int r[MAXSIZE+1];
    //用于記錄順序表的長度
    int length;
}SqList;


//2.排序常用交換函數(shù)實現(xiàn)
//交換L中數(shù)組r的下標(biāo)為i和j的值
void swap(SqList *L,int i,int j)
{
    int temp=L->r[i];
    L->r[i]=L->r[j];
    L->r[j]=temp;
}

//3.數(shù)組打印
void print(SqList L)
{
    int i;
    for(i=1;i<L.length;i++)
        printf("%d,",L.r[i]);
    printf("%d",L.r[i]);
    printf("\n");
}

有資料需求的可以了解下，有關(guān)于包括 數(shù)據(jù)結(jié)構(gòu)、底層進階、圖形視覺、音視頻、架構(gòu)設(shè)計、逆向安防、RxSwift、flutter，算法等方面的資料，面試資料就在群文件里面可自行下載，891點擊 488進入 181
有什么問題也可以直接在里面提出來，互相交流，同時內(nèi)有好友發(fā)內(nèi)推機會，一起共同進步！

冒泡排序

冒泡排序(Bubble Sort) ?一種交換排序,它的基本思想就是：兩兩?比較相鄰的記錄的關(guān)鍵字,如果反序則交換,直到?jīng)]有反序的記錄為?

初級版本

初級版本冒泡排序就是利用兩個循環(huán)，依次進行遍歷交換

//4. 冒泡排序-對順序表L進行交換排序(冒泡排序初級版本)
void BubbleSort0(SqList *L){
   
    int i,j;
    for (i = 1; i < L->length; i++) {
        for (j = i+1; j <= L->length; j++) {
            if(L->r[i] > L->r[j])
                swap(L, i, j);
        }
    }
}

正宗冒泡排序

初級版本冒泡排序，每次循環(huán)后原順序表的順序沒有根本性的變化，而正宗冒泡排序是每次遍歷都會對順序表進行一次簡單排序，并且找到一個相應(yīng)位置的值

//5.冒泡排序-對順序表L作冒泡排序(正宗冒泡排序算法)
void BubbleSort(SqList *L){
    int i,j;
    for (i = 1; i < L->length; i++) {
        //注意:j是從后面往前循環(huán)
        for (j = L->length-1; j>=i; j--) {
            
            //若前者大于后者(注意與上一個算法區(qū)別所在)
            if(L->r[j]>L->r[j+1])
                //交換L->r[j]與L->r[j+1]的值;
                swap(L, j, j+1);
        }
    }
}

冒泡排序的優(yōu)化

冒泡排序有個缺陷就是，假如原來的順序表本來就是有序的，本質(zhì)上不應(yīng)該再次一個個遍歷，應(yīng)該在知道順序表是有序時候直接終止遍歷，優(yōu)化點就是創(chuàng)建一個flag來標(biāo)示一下剩下的順序表是否是有序的，如果是有序的直接可以break

//6.冒泡排序-對順序表L冒泡排序進行優(yōu)化
void BubbleSort2(SqList *L){
    int i,j;
    //flag用作標(biāo)記
    Status flag = TRUE;
    
    //i從[1,L->length) 遍歷;
    //如果flag為False退出循環(huán). 表示已經(jīng)出現(xiàn)過一次j從L->Length-1 到 i的過程,都沒有交換的狀態(tài);
    for (i = 1; i < L->length && flag; i++) {
        
        //flag 每次都初始化為FALSE
        flag = FALSE;
        
        for (j = L->length-1; j>=i; j--) {
            
            if(L->r[j] > L->r[j+1]){
            //交換L->r[j]和L->r[j+1]值;
            swap(L, j, j+1);
            //如果有任何數(shù)據(jù)的交換動作,則將flag改為true;
            flag=TRUE;
            }
        }
    }
}

##選擇排序

選擇排序也是兩個循環(huán)，每次內(nèi)循環(huán)都找到一個最小值，然后，讓最小值和待排序數(shù)據(jù)的第一個值進行交換

//7.選擇排序--對順序表L進行簡單選擇排序
void SelectSort(SqList *L){
    
    int i,j,min;

    for (i = 1; i < L->length; i++) {
        //① 將當(dāng)前下標(biāo)假設(shè)為最小值的下標(biāo)
        min = i;
        //② 循環(huán)比較i之后的所有數(shù)據(jù)
        for (j = i+1; j <= L->length; j++) {
            //③ 如果有小于當(dāng)前最小值的關(guān)鍵字,將此關(guān)鍵字的下標(biāo)賦值給min
            if (L->r[min] > L->r[j]) {
                min = j;
            }
        }
        
        //④ 如果min不等于i,說明找到了最小值,則交換2個位置下的關(guān)鍵字
        if(i!=min)
            swap(L, i, min);
    }
}

插入排序

直接插入排序算法(Stright Insertion Sort)的基本操作是將一個記錄插入到已經(jīng)排好序的有序表中,從而得到一個新的,記錄數(shù)增1的有序表;
步驟：

用哨兵temp，記錄已排序好的有序表的后面的第一個值
再跟已排序后的有序表倒序比較，如果有序表的值大于待排序的值，那么就將已排序的有序表的值往后移一位，因為后面值已經(jīng)被temp記錄了
依次往前移，直到找到已排好的有序表中的值小于temp，那么temp就應(yīng)該排在該值前面
如果待排序的值最小，那么就插在第一個位置

//8.直接插入排序算法--對順序表L進行直接插入排序
void InsertSort(SqList *L){
    int i,j;
    //L->r[0] 哨兵 可以把temp改為L->r[0]
    int temp=0;
    
    //假設(shè)排序的序列集是{0,5,4,3,6,2};
    //i從2開始的意思是我們假設(shè)5已經(jīng)放好了. 后面的牌(4,3,6,2)是插入到它的左側(cè)或者右側(cè)
    for(i=2;i<=L->length;i++)
    {
        //需將L->r[i]插入有序子表
        if (L->r[i]<L->r[i-1])
        {
            //設(shè)置哨兵 可以把temp改為L->r[0]
            //倒序遍歷已排序好的部分，找到temp應(yīng)該插入的位置
            temp = L->r[i];
            for(j=i-1;L->r[j]>temp;j--)
                    //記錄后移
                    L->r[j+1]=L->r[j];
            
            //插入到正確位置 可以把temp改為L->r[0]
            L->r[j+1]=temp;
        }
    }
}

希爾排序

上面插入排序，我們根據(jù)實現(xiàn)知道對數(shù)據(jù)量小，基本有序的數(shù)據(jù)進行排序比較高效，但是對數(shù)據(jù)量大，無序的數(shù)據(jù)，就需要對插入排序進行改進了
希爾排序聽名字就能想到是Shell提出來的，只是對直接插入排序做了一個基本的改進。什么改進呢？
希爾排序思想:

希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序;
對增量數(shù)組每次排序后，就會將每組值小的排到前面，值大的排到后面，這樣就使數(shù)組變成了基本有序了，再整體插入排序的效率就比較高了
隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減?至1時，整個序列列恰被分成 一組，算法便便終?

//9.希爾排序-對順序表L希爾排序
void shellSort(SqList *L){
    int i,j;
    int increment = L->length;
    //0,9,1,5,8,3,7,4,6,2
    //① 當(dāng)increment 為1時,表示希爾排序結(jié)束
    do{
        //② 增量序列
        increment = increment/3+1;
        //③ i的待插入序列數(shù)據(jù) [increment+1 , length]
        for (i = increment+1; i <= L->length; i++) {
            //④ 如果r[i] 小于它的序列組元素則進行插入排序,例如3和9. 3比9小,所以需要將3與9的位置交換
            if (L->r[i] < L->r[i-increment]) {
                //⑤ 將需要插入的L->r[i]暫時存儲在L->r[0].和插入排序的temp 是一個概念;
                L->r[0] = L->r[i];         
                //⑥ 記錄后移
                for (j = i-increment; j > 0 && L->r[0]<L->r[j]; j-=increment) {
                    L->r[j+increment] = L->r[j];
                }             
                //⑦ 將L->r[0]插入到L->r[j+increment]的位置上;
                L->r[j+increment] = L->r[0];
            }
        }
    }while (increment > 1);
}

文章到這里就結(jié)束了，你也可以私信我及時獲取最新資料以及面試相關(guān)資料。如果你有什么意見和建議歡迎給我留言。