冒泡排序与选择排序的 C 语言实现及思想解析

冒泡排序

算法思想

冒泡排序的核心思想是将数组中相邻的两个数进行比较，如果左边的数比右边的数大，则交换数据，接着继续比较下一组相邻的数据。一直比较到一组相邻数据中包含了数组末尾的数据，才算是结束。

单趟排序的目的是将待排序数组中的最大值放到待排序数组的结尾处，紧接着缩小待排序的区间范围。因为单趟排序的最大数已经放到了正确的位置上，下一次排序可以不用动它了。只要一开始数组有 n 个元素，执行单趟排序的次数就为 n-1 次。

代码实现

// 交换两个数字
void Swap(int* p1, int* p2) {
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 冒泡排序 -- 第一种写法
void BubbleSort(int* a, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n - i; j++) {
            if (a[j - 1] > a[j]) {
                Swap(&a[j - 1], &a[j]);
            }
        }
    }
}

// 冒泡排序 -- 第二种写法
void BubbleSort(int* a, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                Swap(&a[j + 1], &a[j]);
            }
        }
    }
}

算法改进

如果给定的数组是一个已经有序的数组，标准冒泡排序仍会进行一次完整的遍历。为了优化这种情况，可以引入一个标志位来标记该数组是否有序。

void BubbleSort {
     ( i = ; i < n; i++) {
         flag = ; 
         ( j = ; j < n - i; j++) {
             (a[j - ] > a[j]) {
                flag = ; 
                Swap(&a[j - ], &a[j]);
            }
        }
         (flag == ) {
            ;
        }
    }
}