冒泡排序

  基本思想:比较相邻的两个数,如果前者比后者大,则进行交换。每一轮排序结束,选 出一个未排序中最大的数放到数组后面。

动图演示

冒泡排序

C代码

#include<stdio.h>
//冒泡排序算法
void bubbleSort(int *arr, int n) {
    for (int i = 0; i<n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
        {
            //如果前面的数比后面大,进行交换
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
            }
        }
}
int main() {
    int arr[] = { 10,6,5,2,3,8,7,4,9,1 };
    int n = sizeof(arr) / sizeof(int);
    bubbleSort(arr, n);
    printf("排序后的数组为:\n");
    for (int j = 0; j<n; j++)
        printf("%d ", arr[j]);
    printf("\n"); 
    return 0;
}

分析:

  最差时间复杂度为O(n^2),平均时间复杂度为O(n^2)。稳定性:稳定。辅助空间O(1)。

升级版冒泡排序

  基本思想:通过从低到高选出最大的数放到后面,再从高到低选出最小的数放到前面, 如此反复,直到左边界和右边界重合。当数组中有已排序好的数时,这种排序比传统冒泡排序性能稍好。

#include<stdio.h>
//升级版冒泡排序算法
void bubbleSort_1(int *arr, int n) {
    //设置数组左右边界
    int left = 0, right = n - 1;
    //当左右边界未重合时,进行排序
    while (left<right) {
        //从左到右遍历选出最大的数放到数组右边
        for (int i =left; i < right; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                int temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp;
            }
        }
        right--;
        //从右到左遍历选出最小的数放到数组左边
        for (int j = right;j>= left; j--)
        {
            if (arr[j + 1] < arr[j])
            {
                int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;
            }
        }
        left++;
    }

}
int main() {
    int arr[] = { 10,6,5,2,3,8,7,4,9,1 };
    int n = sizeof(arr) / sizeof(int);
    bubbleSort_1(arr, n);
    printf("排序后的数组为:\n");
    for (int j = 0; j<n; j++)
        printf("%d ", arr[j]);
    printf("\n");
    return 0;
}
Copyright © liyang.com 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-01 15:22:50

results matching ""

    No results matching ""