数据结构-冒泡排序

迷南。 2022-05-13 13:10 199阅读 0赞

冒泡排序算法的基本思想：假设待排序表长为n,从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A\[i-1\]>A\[i\]）,则交换它们，直到序列比较完。我们称为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置（关键字最小的元素如气泡一般逐渐往上”漂浮“直至“水面”，这就是冒泡排序名字的由来）。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中最小的元素放到了序列的最终位置......

以下示例为冒泡排序的优化过程

1.一般排序

//
    // Created by Administrator on 2018/7/13.
    //
    /**
     * 普通排序
     */
    #include <stdio.h>
    
    /**
     * 普通排序
     * @param a
     * @param n
     */
    void sort(int a[], int n) {
    
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
    
    int main() {
        int i, a[10] = {2, 4, 3, 8, 6, 7, 5, 9, 0, 1};
        int n = 10;
        sort(a, n);
        printf("排序后的结果为：");
        for (i = 0; i < n; i++) {
            printf("%d", a[i]);
        }
        printf("\n");
    
        return 0;

2.冒泡排序普通版

//
    // Created by Administrator on 2018/7/13.
    //
    /**
     * 冒泡排序普通版
     */
    #include <stdio.h>
    
    /**
     * 冒泡排序（普通版）
     * @param a
     * @param n
     */
    void sort(int a[], int n) {
    
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) {
                if (a[j - 1] > a[j]) {
                    int temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
    
    int main() {
        int i, a[10] = {2, 4, 3, 8, 6, 7, 5, 9, 0, 1};
        int n = 10;
        sort(a, n);
        printf("排序后的结果为：");
        for (i = 0; i < n; i++) {
            printf("%d", a[i]);
        }
        printf("\n");
    
        return 0;
    }
    3.冒泡排序优化版
    
    
    
    
    
    //
    // Created by Administrator on 2018/7/13.
    //
    /**
     * 冒泡排序优化版
     */
    #include "stdio.h"
    /**
     * 冒泡排序优化版：按顺序排列（即从小到大）
     * @param a
     * @param len
     */
    void sort(int a[], int len) {
        int flag = 1;
        for (int i = 0; i < len - 1; ++i) {
            for (int j = len - 1; j > i; --j) {
                flag = 0;
                if (a[j - 1] > a[j]) {
                    int temp;
                    temp = a[j - 1];
                    a[j - 1] = a[j];
                    a[j] = temp;
                    flag = 1;
                }
            }
            if (!flag) {
                //说明经过内层冒泡比较后，并没有发生位置的改变，则表明该序列有呈有序状态，不在进行比较
                return;
            }
        }
    }
    
    int main(){
        int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
        int len = 10;
        sort(a,len);
        printf("排序后的结果为：");
        for (int i = 0; i < len; ++i) {
            printf("%d",a[i]);
        }
        printf("\n");
    }

执行产生相同的结果：

![70][]

[70]: /images/20220504/2a6678bfb395470fb36236c22b9839d1.png