一. 选择排序

  1. 原理
    首先在未排序序列中找到最小的元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小元素，翻到排序序列末尾，以此类推，直到所有的元素均排序完毕.

  2. 基本思想

    第一趟排序在所有待排序的n个记录中选出关键字最小的记录,将它与数据表中的第一个记录交换位置,使关键字最小的记录处于数据表的最前端;第二趟在剩下的n-1个记录中再选出关键字最 小的记录,将其与数据表中的第二个记录交换位置,使关键字次小的记录处于数据表的第二个位置;重复这样的操作,依次选出数据表中关键字第三小、第四小…的元素,将它们分别换到数据表的第三、第四…个位置上。排序共进行n-1趟,最终可实现数据表的升序排列。

  3. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    // 需要排序的数组
    int nums[8] = {99, 12, 88, 34, 5, 44, 12, 100};
    // 计算数组长度
    int length = sizeof(nums) / sizeof(nums[0]);
    printf("length = %i\n", length);

    for (int i = 0; i < length; i++) {
    	printf("排序前: nums[%i] = %i\n", i, nums[i]);
    }
        
    printf("=====================\n");
        
    // 排序
    for (int i = 0; i < length - 1; i++) {
        for (int j = i+1; j < length; j++) {
            if (nums[i] > nums[j]) {
                // 交换位置
    			int temp = nums[i];
    			nums[i] = nums[j];
    			nums[j] = temp;
            }
        }
    }
        
    for (int i = 0; i < length; i++) {
        printf("排序后: nums[%i] = %i\n", i, nums[i]);
    }

二. 冒泡排序

  1. 原理

    它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来 是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  2. 基本思想

    • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应 该会是最大的数。
    • 针对所有的元素重复以上的步骤,除了最后一个。
    • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  3. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int nums[8] = {99, 12, 88, 34, 5, 44, 12, 100};
    int length = sizeof(nums) / sizeof(nums[0]);

    for (int i = 0; i < length; i++) {
        printf("排序前: nums[%i] = %i\n", i, nums[i]);
    }

    printf("----------\n");

    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < length; i++) {
        printf("排序后: nums[%i] = %i\n", i, nums[i]);
    }

    ​

三. 插入排序

  1. 原理

    插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中……第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。

  2. 基本思想

    插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

  3. 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int nums[8] = {99, 12, 88, 34, 5, 44, 12, 100};
    int length = sizeof(nums) / sizeof(nums[0]);

    for (int i = 0; i < length; i++) {
        printf("排序前: nums[%i] = %i\n", i, nums[i]);
    }

    printf("----------\n");

    int i, j, temp;
    for (i = 1; i < length; i++) {
        if (nums[i] < nums[i - 1]){
            temp = nums[i];
            for (j = i - 1; j >= 0 && nums[j] > temp; j--)
                nums[j + 1] = nums[j];
            nums[j + 1] = temp;
        }
    }

    for (int i = 0; i < length; i++) {
        printf("排序后: nums[%i] = %i\n", i, nums[i]);
    }

    ​