冒泡排序、插入法排序及选择排序

宅蓝三木

发布于 2024-10-09 20:56:40

8300

代码可运行

文章被收录于专栏：三木的博客三木的博客

运行总次数：0

代码可运行

冒泡排序、插入法排序以及选择排序是排序算法中比较基础的三种，其平均时间复杂度都是O(n^2)。

原理介绍

冒泡排序

冒泡排序的步骤是：比较相邻两个数，看是否满足大小关系，如果不满足则交换这两个数，使他们满足大小关系，这样可以保证最大（最小）的数始终会向后流动，循环一次之后，最大（最小）的数就会被交换到数组的最后。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

插入法排序

插入法排序的思路是：把数组分成两个部分：排好序的，和未排序的。开始的时候，数组的第一个元素会被当做拍好序的部分，对其余未排好序的数值进行迭代，将其插入到排好序的部分中合适的位置。

选择法排序

选择法排序和插入法排序类似，都是将数组分为排好序的和未排序的两个部分。不同的是，选择法排序每次迭代都会选择未排序部分中的最小（最大）值，将其插入到排好序部分的队首（队尾）。

C语言实现

需要实现四个函数，第一个是打印数组，接下来三个函数分别实现三种排序算法：

void print_arry(int *a, int len)
static inline void insertion_sort(int *a, int len)
static inline void bubble_sort(int *a, int len)
static inline void selection_sort(int *a, int len)

main函数中，首先需要用户输入指定数目(#define LEN 10)的数值，如果用户输入-1则随机生成这些数值。然后需要用户输入排序算法。输入完成后打印排序前的数组，然后根据相应的排序算法进行排序，最后再打印出排序后的数组。代码如下：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define LEN 10
#define NR_METHOD 3
#define RAND_RANGE 100

void print_arry(int *a, int len) {
    int i = 0;
    for (int i = 0; i < len; i++) {
        printf("%d ", a\[i\]);
    }
    printf("\\n");
}

static inline void insertion_sort(int *a, int len) {
    int tmp = 0;
    int i, j;
    for (i = 1; i < len; i++) {
        tmp = a\[i\];
        for (j = i - 1; j >= 0; j--) {
            if (a\[j\] > tmp) {
                a\[j + 1\] = a\[j\];
            } else {
                break;
            }
        }
        a\[j + 1\] = tmp;
    }
}

static inline void bubble_sort(int *a, int len) {
    int i, j;
    int tmp;
    int swapped = 0;
    for (i = len - 1; i >= 0; i--) {
        for (j = 0; j < i; j++) {
            if (a\[j\] > a\[j + 1\]) {
                tmp = a\[j\];
                a\[j\] = a\[j + 1\];
                a\[j + 1\] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

static inline void selection_sort(int *a, int len) {
    int i, j, min, tmp;
    for (i = 0; i < len -1; i++) {
        min = i;
        for (j = i + 1; j < len; j++) {
            if(a\[j\] < a\[min\]) {
                min = j;
            }
        }
        if (min != i) {
            tmp = a\[min\];
            a\[min\] = a\[i\];
            a\[i\] = tmp;
        }
    }
}

int main(int argc, char **argv) {
    srand(time(NULL));

    int a\[LEN\];
    int data;

    for (int i = 0; i < LEN; i++) {
        printf("Please input a number: %d left: (-1 for random numbers)", LEN - i);
        scanf("%d", &data);
        if(data != -1) {
            a\[i\] = data;
        } else {
            for (int j = 0; j < LEN; j++) {
                a\[j\] = rand() % RAND_RANGE;
            }
            break;
        }
    }

    while (1) {
        printf("Please select a sort method:\\n");
        printf("0: Insertion sort\\n");
        printf("1: Bubble sort \\n");
        printf("2: Selection sort \\n");
        scanf("%d", &data);
        if(data >= 0 && data < NR_METHOD) {
            break;
        } else {
            printf("Please input a valid number!\\n");
        }
    }

    printf("Original Array: \\n");
    print_arry(a, LEN);

    switch(data) {
        case 0:
        printf("You selected insertion sort\\n");
        insertion_sort(a, LEN);
        break;
        case 1:
        printf("You selected bubble sort\\n");
        bubble_sort(a, LEN);
        break;
        case 2:
        printf("You selected selection sort\\n");
        selection_sort(a, LEN);
        break;
    }

    printf("Sorted Array: \\n");
    print_arry(a, LEN);

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-11-22，如有侵权请联系 cloudcommunity@tencent.com 删除

数组