typora-copy-images-to: upload

前言

此篇文章介紹的排序主要有3個,冒泡排序,選擇排序,插入排序,他們有一個共同的特點,那就是時間復雜度都為O(n2).

冒泡排序

冒牌排序的思想是,先遍歷陣列一次,在遍歷程序中,通過兩兩交換的方式把較大的資料放到后面(保證了每次遍歷時都能把最大的數放在后面),然后又從頭到尾重復此程序,直到有序.如下圖(綠色代表在遍歷程序中兩兩比較,橙色代表已經部分排好序):

知道了思想,怎么寫代碼呢,我們先從最簡單的一步開始,即只遍歷一次,該怎么寫,先看看需求:

• 兩兩交換,說明需要一個交換函式.
• 什么時候需要交換呢?當前者大于后者的時候,也就是說我們需要比較.

所以如果只遍歷一次,代碼如下:

void swap(int* a,int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
//n是陣列長度
for(int j = 0;j<n-1;j++) //小于n-1是因為索引最大為n-1,j代表當前索引,那么j最大只能為n-2
{
    if(num[j] > num[j+1]) //如果前者大于后者就交換,否則繼續遍歷.
    {
        swap(&num[j],&num[j+1]);
    }
}

現在我們結合遍歷一次的代碼和上面的動圖仔細想想,既然遍歷一次就調整好一個最大的數字在最后面,那么我們要遍歷多少次才能把全部的數字排好序呢?沒錯,答案是n-1次,因為有n個數字,但是是通過兩兩比較實作的,**當索引[1,n-1]**都有序后,索引為0的數字一定比索引為1的數字小,就不需要再比較了.

所以冒泡排序的代碼如下:

void BubbleSort(int num[],int n)
{
    for(int i = 0;i<n-1;i++) //需要遍歷n-1次
    {
        //n是陣列長度
        for(int j = 0;j< n-1 - i;j++) //小于n-1-i是因為每一次完整遍歷陣列后,最后一個數字一定是最大的,下一次遍歷就不需要再管它.
        {
            if(num[j] > num[j+1]) //如果前者大于后者就交換,否則繼續遍歷.
            {
                swap(&num[j],&num[j+1]);
            }
        }
    }
}

測驗:

選擇排序

選擇排序的思想是,先假設未排序第一元素是最小的,然后遍歷一遍陣列看是否有比假想的最小數更小的數,如果有就記錄索引,遍歷完成以后把真正的最小數與最初的假想最小數交換.然后繼續重復上面程序.如下圖(綠色代表正在遍歷,紅色代表定位最小數,橙色代表部分排好序):

同樣道理,我們由簡到繁,先寫出只遍歷一次時候的代碼,那么只遍歷一次時候需要的準備是:

• 用于記錄最小元素的索引變數min_index.
• 交換函式.

代碼如下:

//n是陣列長度
int min_index  = 0; //0代表未排序元素的頭的索引.
for(int j = 0 + 1;j<n;j++) //j從頭的下一個位置開始
{
	if(num[j] < num[min_index])  //如果當前元素比最小元素小
    {
        min_index = j;    //就記錄最下元素的索引
    }
}
swap(&num[0],&num[min_index]);  //最小元素與頭進行交換.

這個和冒泡排序是不是幾乎一樣?遍歷一次便能夠確定一個最小的數,然后放到首位,那么需要多少次呢?答案是n-1次

所以完整的代碼如下:

void SelectSort(int num[],int n)
{
    for(int i = 0;i<n-1;i++) //需要遍歷n-1次
    {
        int min_index  = i; //i代表   未排序元素   的頭的索引.
        for(int j = i + 1;j<n;j++) //j從頭的下一個位置開始
        {
            if(num[j] < num[min_index])  //如果當前元素比最小元素小
            {
                min_index = j;    //就記錄最下元素的索引
            }
        }
        swap(&num[i],&num[min_index]);  //最小元素與頭進行交換.
    }
}

測驗:

插入排序

插入排序的思想是,從索引j(范圍為1到n-1)開始,保證[0,i]區間的元素有序,怎么保證呢? 先把索引為i的元素保存下來(變數target),然后依次往前比較,如果前面的元素比target大,就往后放,否則停止.如圖(橙色代表部分有序,綠色代表從i開始往前遍歷,紅色代表原索引i元素):

仍然一樣的思想,先從簡到繁,如若只執行一次,該怎樣操作?

int target = num[i];  //索引為[0,i]區間中索引為i的元素
int aim = i;          //aim是用于記錄target真正應該的位置
for(int j = i;j>0;j--)  
{
    if(num[j-1] > target) num[j] = num[j-1],aim = j-1;//如果前面大于target,前面就覆寫后面,并且aim更新位置.
}
num[aim] = target; //target回到自己應該的位置.

現在我們看向上圖,可以發現,i是從1開始遞增的.所以完整代碼為:

void InsertSort(int num[],int n)
{   
    for(int i =1;i<n;i++)
    {
        int target = num[i];  //索引為[0,i]區間中索引為i的元素
        int aim = i;          //aim是用于記錄target真正應該的位置
        for(int j = i;j>0;j--)  
        {
            if(num[j-1] > target) num[j] = num[j-1],aim = j-1;//如果前面大于target,前面就覆寫后面,并且aim更新位置.
        }
        num[aim] = target; //target回到自己應該的位置.
    }
}

測驗

冒泡排序優化

大家有沒有想過,對于冒泡排序,如果資料本來就是有序的,是沒必要再比下去的,但是冒泡排序卻不得不仍然要比n*(n-1)/2次,所以我們給其加個flag,第一遍遍歷時判斷是否有序,如果有序,就結束.

void BubbleSort(int num[],int n)
{
    for(int i = 0;i<n-1;i++) //需要遍歷n-1次
    {
        int flag =  1; //等于1代表假設是有的
        for(int j = 0;j< n-1 - i;j++)
        {
            if(num[j] > num[j+1]) 
            {
                swap(&num[j],&num[j+1]);
                flag = 0; //如果交換了數字,說明無效,變為0;
            }
        }
        if(flag) break;//如果有序就停止
    }
}

選擇排序優化

受到上面冒泡排序的啟示,大家可能會想,如果有序就怎么樣…但是這種形式的優化對于選擇排序來說是沒有意義的,因為根本無法達到.

那么優化選擇排序是優化的哪些呢?

選擇的思路是把最小的放到最前面,那么我們可不可以在遍歷一次的時候同時找到最大和最小呢?然后最小放前面,最大放后面呢?

void SelectSort(int num[],int n)
{
    for(int i = 0;i<n-1;i++)
    {
        int min_index = i; //假設索引為i元素最小
        int max_index = i; //假設索引為i元素最大
        for(int j = i + 1;j < n-i;j++)  //j小于n-i是因為最后面的元素在逐漸有序,便不需要再管
        {
            if(num[j] < num[min_index]) 
            {
                min_index = j;    //更新最小
            }
            if(num[j] > num[max_index])
            {
                max_index = j;    //更新最大
            }
        }
        
        swap(&num[i],&num[min_index]); //把最小的放前面
        
        if(max_index == i) max_index = min_index; //如果最大值在頭,那么最小值放在前面后,最大值就被換到min_index位置
        
        swap(&num[n-1-i],&num[max_index]);//最大的放后面
        
    }
}

插入排序優化

大家想想,插入排序可以怎么優化呢?其實插入排序由于自身的特性,幾乎優化不了,比如資料有序,插入排序遍歷一遍就知道了,那我們說的插入排序優化是什么呢?這個博主會放到另一篇文章講,因為插入的改進后就是另一個排序,希爾排序