Linux C語言高級編程數據結構之排序(1)冒泡排序與插入排序!筆試面試必備!

    -回復 -瀏覽
    樓主 2020-11-16 15:37:20
    舉報 只看此人 收藏本貼 樓主

    簡 ?介

    首先祝大家圣誕快樂,萬事如意!現在讓我們開始本章的學習吧,本章主要介紹數據結構中最常見的幾種排序方式,數據結構中常見的排序算法包括:冒泡排序、插入排序、選擇排序、快速排序與歸并排序,本章介紹一下冒泡排序與插入排序。


    冒泡排序

    冒泡排序的過程:

    1、將待排序的數組中的第一個元素與第二個元素相對比,如果這兩個元素的大小順序不是我們要求的順序,則將它們交換過來

    2、將待排序的數組中的第二個元素與第三個元素相對比,如果這兩個元素的大小順序也不是我們要求的順序,則也將它們交換過來。下一步,是對比第三個元素與第四個元素,直至倒數第二個元素與最后一個元素相對比。

    3、這樣一趟對比下來,小的數據元素會一點一點的往前放,而大的數據元素會一點一點的往后放。反復多趟的這樣對比,直到所有數據都排好序為止。

    冒泡排序代碼實現:

    #include<stdio.h>

    typedef int Data;

    /*冒泡排序實現 按照從小到大順序排列*/

    void bubble(Data* a, int n) {

    ????for (int i = 0; i < n - 1; i++) {

    ????????bool flag = true;//設置標記

    //內層循環實現一次交換

    ????????for (int j = 0; j < n - ?i - 1; j++)

    ? ?{

    ????????????if (a[j] > a[j + 1]){

    ????????????????Data t = a[j];

    ????????????????a[j] = a[j + 1];

    ????????????????a[j + 1] = t;

    ????????????????flag = false;

    ????????????}

    ????????}

    ????????/*當該標記為true時表明數組順序已經是有序狀態,不需要繼續排序*/

    ????????if (flag)

    break;

    ????}

    }

    //打印數組

    void print(Data* a, int n) {

    ????for (int i = 0; i < n; i++)

    ????????printf("%d ", a[i]);

    ????printf("\n");

    }

    int main() {

    int a[10] = {3, 2, 4, 5, 7, 8, 9, 1, 6, 0};

    //冒泡排序數組

    bubble(a, 10);

    //打印排序后的數組

    print(a, 10);

    return 0;

    }

    插入排序

    插入排序的過程:

    1、將待排序的數組分成兩部分,一部分是已經排好序的部分,另一部分是未排好序的部分。在開始排序前,已排好序的部分只有一個數組元素,即數組的第一個元素;未排好序的部分是數組中除第一個元素外的其它所有元素。

    2、將未排好序部分中的第一個數組元素,插入到已排序部分當中適當的位置,以保證已排序部分仍然是保持排序狀態。此時,已排序部分就變成兩個數組元素,而未排序部分的數組元素同時少了一個。

    3、依次類推,逐個從未排好序的部分拿出一個元素,插入到已排序部分當中適當的位置,直至數組按順序排好為止。

    插入排序代碼實現:

    #include<stdio.h>

    typedef int Data;

    //插入排序實現

    void insert(Data *a, int n) {

    ????/*逐個將未排序部分元素取出來,插入到已排序部分*/

    ????for (int i = 1; i < n; i++) {

    ????????//把選擇的元素放在臨時變量中

    ????????Data t = a[i];

    ????????int j = 0;

    ????/*將未排序部分的第一個元素t插入到已排序部分的適當位置a[j] */

    ????????for (j = i; j > 0 && a[j - 1] > t; j--) {

    ????????????a[j] = a[j - 1];

    ????????}

    ????????a[j] = t;

    ????}

    }

    void print(DataType* a, int n) {

    ????for (int i = 0; i < n; i++)

    ????????printf("%d ", a[i]);

    ????printf("\n");

    }

    int main() {

    ????int a[10] = {3, 2, 4, 5, 7, 8, 9, 1, 6, 0};

    ????insert(a, 10);

    ????print(a, 10);

    ????return 0;

    }



    冒泡排序與插入排序的比較


    我要推薦
    轉發到
    cp彩票