冒泡排序

2020-06-21

数据结构

思想 #

特点是两两交换。

相邻的两个数比较，每次比较将大的数放到下面，一次循环后，最大的数就在最下面了。

小数上冒，大数沉底。

经过第一趟排序后，最大的数就移到了最后面。

第二趟排序会将次大值移到倒数第二位。

以此类推，直到所有的数排好位置。

代码实现 #

#include <stdio.h>

void sort(int *a, int length);

int main()
{

    int n[10] = {9, 4, 10, 43, 75, 14, 0, 12, 53, 71};
    sort(n, 10);
    for (int i = 0; i < 10; i++)
    {
        printf("a[%d] is %d\n", i, n[i]);
    }
    return 0;
}

void sort(int *a, int length)
{
    for(int i = 0; i < length; i++)
    {
        for(int j = 1; j < length; j++)
        {
            if(a[j - 1] > a[j])
            {
                int tmp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = tmp;
            }
        }
    }
}

复杂度 #

时间复杂度：O(n²)

空间复杂度：O(1)

稳定的排序算法