經典算法學習——冒泡排序

冒泡排序是我們學習的第一種排序算法，應該也算是最簡單、最常用的排序算法瞭。不管怎麼說，學會它是必然的。今天我們就用C語言來實現該算法。示例代碼已經上傳至：https://github.com/chenyufeng1991/BubbleSort

算法描述如下：

（1）比較相鄰的前後兩個數據，如果前面數據大於後面的數據，就將兩個數據交換；

（2）這樣對數組的第0個數據到N-1個數據進行一次遍歷後，最大的一個數據就到瞭最後一個位置，也就是下標為N-1的位置（沉到瞭水底）。

（3）N = N-1，如果N不為0就重復（1）（2）兩步，否則排序完成，也就是對數組的第0個數據到N-2個數據再次進行遍歷；

 

完整的代碼實現如下：

 

//
//  main.c
//  BubbleSort
//
//  Created by chenyufeng on 16/1/28.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//


#include 

typedef int BOOL;
#define true 1
#define false 0

int *bubbleSort01(int arr[],int len);
void bubbleSort03(int arr[],int len);

int main(int argc, const char * argv[]) {

    int array[7] = {150,111,1000,99,300,10,189};

    /**
     *指針向後移位；
     */

    //    int *p = bubbleSort02(array, 7);
    //
    //    for (int i = 0; i < 7; i++) {
    //        printf("%d ",*(p+i));
    //    }

    /**
     *  可以使用傳引用的方式，實現如下;
     這裡不需要返回值，直接打印即可,推薦使用這種方式，方便；
     */
    bubbleSort04(array, 7);
    for (int i = 0; i < 7; i++) {
        printf("%d ",array[i]);
    }

    return 0;
}

//常規的冒泡；
int *bubbleSort01(int arr[],int len){

    int temp;
    for (int i = 0; i < len; i++){
        for (int j = 1; j < len - i; j++) {
            if (arr[j - 1] > arr[j]) {

                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

//常規的冒泡，不需要返回值；
void bubbleSort03(int *arr,int len){

    int temp;
    for (int i = 0; i < len; i++){
        for (int j = 1; j < len - i; j++) {
            if (arr[j - 1] > arr[j]) {

                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

 

 

當然也可以把上面的交換元素的代碼抽取出來，寫成一個交換函數swap。代碼實現如下：

 

//
//  main.c
//  BubbleSort
//
//  Created by chenyufeng on 16/1/28.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//


#include 

typedef int BOOL;
#define true 1
#define false 0

int *bubbleSort01(int arr[],int len);
void swap(int *a,int *b);

int main(int argc, const char * argv[]) {

    int array[7] = {150,111,1000,99,300,10,189};

    /**
     *指針向後移位；
     */

    //    int *p = bubbleSort02(array, 7);
    //
    //    for (int i = 0; i < 7; i++) {
    //        printf("%d ",*(p+i));
    //    }

    /**
     *  可以使用傳引用的方式，實現如下;
     這裡不需要返回值，直接打印即可,推薦使用這種方式，方便；
     */
    bubbleSort01(array, 7);
    for (int i = 0; i < 7; i++) {
        printf("%d ",array[i]);
    }

    return 0;
}

//常規的冒泡；
int *bubbleSort01(int arr[],int len){

    int temp;
    for (int i = 0; i < len; i++){
        for (int j = 1; j < len - i; j++) {
            if (arr[j - 1] > arr[j]) {

//                temp = arr[j - 1];
//                arr[j - 1] = arr[j];
//                arr[j] = temp;

                //這裡也可以使用swap交換函數；
                swap(&arr[j - 1], &arr[j]);
            }
        }
    }
    return arr;
}


void swap(int *a,int *b){

    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}