<menuitem id="r3jhr"></menuitem><noscript id="r3jhr"><progress id="r3jhr"><code id="r3jhr"></code></progress></noscript>

      各種排序方法復(fù)雜度總結(jié)

      時(shí)間:2021-03-29 17:20:22 總結(jié) 我要投稿

      各種排序方法復(fù)雜度總結(jié)

        在C中,排序算法是最基本最常用的算法,不同的排序算法在不同的場景或應(yīng)用中會(huì)有不同的表現(xiàn),接下來小編搜集了各種排序方法復(fù)雜度總結(jié),歡迎查看。

      各種排序方法復(fù)雜度總結(jié)

        一、冒泡排序

        主要思路是:

        通過交換相鄰的兩個(gè)數(shù)變成小數(shù)在前大數(shù)在后,這樣每次遍歷后,最大的數(shù)就“沉”到最后面了。重復(fù)N次即可以使數(shù)組有序。

        代碼實(shí)現(xiàn)

        void bubble_sort(int arr[], int len)

        {

        for (int i = 0; i < len — 1; i++)

        {

        for (int j = len — 1; j >= i; j——)

        {

        if (arr[j] < arr[j — 1])

        {

        int temp = arr[j];

        arr[j] = arr[j — 1];

        arr[j — 1] = temp;

        }

        }

        }

        }

        冒泡排序改進(jìn)1:

        在某次遍歷中,如果沒有數(shù)據(jù)交換,說明整個(gè)數(shù)組已經(jīng)有序,因此通過設(shè)置標(biāo)志位來記錄此次遍歷有無數(shù)據(jù)交換就可以判斷是否要繼續(xù)循環(huán)。

        冒泡排序改進(jìn)2:

        記錄某次遍歷時(shí)最后發(fā)生數(shù)據(jù)交換的位置,這個(gè)位置之后的數(shù)據(jù)顯然已經(jīng)有序。因此設(shè)置標(biāo)志位記錄每次遍歷中最后發(fā)生數(shù)據(jù)交換的位置可以確定下次循環(huán)的范圍。

        二、直接插入排序

        主要思路是:

        每次將一個(gè)待排序的'數(shù)組元素,插入到前面已排序的序列中這個(gè)元素應(yīng)該在的位置,直到全部數(shù)據(jù)插入完成。類似撲克牌洗牌過程。

        代碼實(shí)現(xiàn)

        void _sort(int arr[], int len)

        {

        for (int i = 1; i < len; i ++)

        {

        int j = i — 1;

        int k = arr[i];

        while (j > —1 && k < arr[j] )

        {

        arr[j + 1] = arr[j];

        j ——;

        }

        arr[j + 1] = k;

        }

        }

        三、直接選擇排序

        主要思路是:

        數(shù)組分成有序區(qū)和無序區(qū),初始時(shí)整個(gè)數(shù)組都是無序區(qū),每次遍歷都從無序區(qū)選擇一個(gè)最小的元素直接放在有序區(qū)最后,直到排序完成。

        代碼實(shí)現(xiàn)

        void select_sort(int arr[], int len)

        {

        for (int i = 0; i < len; i++)

        {

        int index = i;

        for (int j = i + 1; j < len; j++)

        {

        if (arr[j] < arr[index])

        index = j;

        }

        if (index != i)

        {

        int temp = arr[i];

        arr[i] = arr[index];

        arr[index] = temp;

        }

        }

        }

        四、快速排序

        主要思路是:

        “挖坑填數(shù) + 分治法”,首先令i = L;j = R;將a[i]挖出形成打一個(gè)坑,稱a[i]為基準(zhǔn)數(shù)。然后j——從后向前找到一個(gè)比基準(zhǔn)數(shù)小的數(shù),挖出來填到a[i]的坑中,這樣a[j]就形成了一個(gè)新的坑,再i++從前向后找到一個(gè)比基準(zhǔn)數(shù)大的數(shù)填到a[j]坑中。重復(fù)進(jìn)行這種挖坑填數(shù),直到i = j。這時(shí)a[i]形成了一個(gè)新的坑,將基數(shù)填到a[i]坑中,這樣i之前的數(shù)都比基準(zhǔn)數(shù)小,i之后的數(shù)都比基準(zhǔn)數(shù)大。因此將數(shù)組分成兩部分再分別重復(fù)上述步驟就完成了排序。

        代碼實(shí)現(xiàn)

        void quick_sort(int arr[], int left, int right)

        {

        if (left < right)

        {

        int i = left, j = right, target = arr[left];

        while (i < j)

        {

        while (i < j && arr[j] > target)

        j——;

        if (i < j)

        arr[i++] = arr[j];

        while (i < j && arr[i] < target)

        i++;

        if (i < j)

        arr[j] = arr[i];

        }

        arr[i] = target;

        quick_sort(arr, left, i — 1);

        quick_sort(arr, i + 1, right);

        }

        }

        五、希爾排序

        主要思路是:

        先將整個(gè)待排元素序列分割成若干個(gè)子序列(由相隔某個(gè)“增量”的元素組成的)分別進(jìn)行直接插入排序,然后依次縮減增量再進(jìn)行排序,待整個(gè)序列中的元素基本有序(增量足夠小)時(shí),再對(duì)全體元素進(jìn)行一次直接插入排序。由于希爾排序是對(duì)相隔若干距離的數(shù)據(jù)進(jìn)行直接插入排序,因此可以形象的稱希爾排序?yàn)椤疤濉薄?/p>

        六、歸并排序

        主要思路是:

        當(dāng)一個(gè)數(shù)組左邊有序,右邊也有序,那合并這兩個(gè)有序數(shù)組就完成了排序。如何讓左右兩邊有序了?用遞歸!這樣遞歸下去,合并上來就是歸并排序。

        代碼實(shí)現(xiàn)

        void merge(int arr[], int temp_arr[], int start_index, int mid_index, int end_index)

        {

        int i = start_index, j = mid_index + 1;

        int k = 0;

        while (i < mid_index + 1 && j < end_index + 1)

        {

        if (arr[i] > arr[j])

        temp_arr[k++] = arr[j++];

        else

        temp_arr[k++] = arr[i++];

        }

        while (i < mid_index + 1)

        {

        temp_arr[k++] = arr[i++];

        }

        while (j < end_index + 1)

        temp_arr[k++] = arr[j++];

        for (i = 0, j = start_index; j < end_index + 1; i ++, j ++)

        arr[j] = temp_arr[i];

        }

        void merge_sort(int arr[], int temp_arr[], int start_index, int end_index)

        {

        if (start_index < end_index)

        {

        int mid_index = (start_index + end_index) / 2;

        merge_sort(arr, temp_arr, start_index, mid_index);

        merge_sort(arr, temp_arr, mid_index + 1, end_index);

        merge(arr, temp_arr, start_index, mid_index, end_index);

        }

        }

        七、堆排序

        堆排序的難點(diǎn)就在于堆的的插入和刪除。

        堆的插入就是——每次插入都是將新數(shù)據(jù)放在數(shù)組最后,而從這個(gè)新數(shù)據(jù)的父結(jié)點(diǎn)到根結(jié)點(diǎn)必定是一個(gè)有序的數(shù)列,因此只要將這個(gè)新數(shù)據(jù)插入到這個(gè)有序數(shù)列中即可。

        堆的刪除就是——堆的刪除就是將最后一個(gè)數(shù)據(jù)的值賦給根結(jié)點(diǎn),然后再從根結(jié)點(diǎn)開始進(jìn)行一次從上向下的調(diào)整。調(diào)整時(shí)先在左右兒子結(jié)點(diǎn)中找最小的,如果父結(jié)點(diǎn)比這個(gè)最小的子結(jié)點(diǎn)還小說明不需要調(diào)整了,反之將父結(jié)點(diǎn)和它交換后再考慮后面的結(jié)點(diǎn)。相當(dāng)于從根結(jié)點(diǎn)開始將一個(gè)數(shù)據(jù)在有序數(shù)列中進(jìn)行“下沉”。

        因此,堆的插入和刪除非常類似直接插入排序,只不是在二叉樹上進(jìn)行插入過程。所以可以將堆排序形容為“樹上插”。

      【各種排序方法復(fù)雜度總結(jié)】相關(guān)文章:

      《排序》優(yōu)秀教案課件05-16

      排序和篩選說課稿11-04

      《有趣的排序》教學(xué)設(shè)計(jì)02-09

      大班數(shù)學(xué)模式排序說課稿04-07

      高中英語各種文體的寫作練習(xí)方法和要素分析08-23

      用各種方法巧妙抒發(fā)感情的小學(xué)寫作技巧06-10

      各種圖形剪紙貼畫03-21

      各種分類佳句摘抄05-28

      元旦各種飲食習(xí)俗01-04

      各種道歉信01-05

      久久亚洲中文字幕精品一区四_久久亚洲精品无码av大香_天天爽夜夜爽性能视频_国产精品福利自产拍在线观看
      <menuitem id="r3jhr"></menuitem><noscript id="r3jhr"><progress id="r3jhr"><code id="r3jhr"></code></progress></noscript>
        午夜福利成年电影在线观看 | 午夜国产理论片中文飘花 | 久久少妇一级视频 | 伊人久久大香线蕉成人 | 亚洲人在线观看视频 | 永久免费在线观看全网站 |