三种简单排序算法：选择、插入、冒泡

选择排序

从要排序的数据中找出（选择）最小的那个数，放在所有数据的最左边，记为已排序数据，其余数据记为未排序数据；
之后从未排序数据中找出（选择）最小的数，放入已排序数据的末尾；（通过交换两个数的位置实现）
直至所有数据全部加入已排序数据中，选择排序结束。

#include <stdio.h>
#include <windows.h>
// #include <ctime>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)

int* selectionSort_1(int* arr, int size) {
    //clock_t start_time = clock();
    for (int i = 0; i < size-1; i++) {
        for (int j = i+1; j < size; j++) {
            // 当发现未排序数据中存在比第一个未排序数小的数时，两者交换位置
            // 交换次数较多、效率较低
            if (arr[i] > arr[j]) {
                int tem = arr[j];
                arr[j] = arr[i];
                arr[i] = tem;
            }            
        }
    }
    //clock_t end_time = clock();
    //arr[size] = end_time - start_time;
    return arr;
}

int* selectionSort_2(int* arr, int size) {
    for (int i = 0; i < size-1; i++) {
        int t = i;  // 保存未排序数据中扫描到的最小数的下标
        for (int j = i+1; j < size; j++) {
            if (arr[t] > arr[j])    t = j;
        }
        int tem = arr[t];
        arr[t] = arr[i];
        arr[i] = tem;
    }
    return arr;
}

int main()
{
    int arr[10] = { 1,25,3,4,85,6,2,4,7,65 };

    int* a = selectionSort_1(arr, 10);
    int* b = selectionSort_2(arr, 10);

    printf("selectionSort_1 的运行结果\n");
    for (int i = 0; i < 10; i++)    printf("%d ", a[i]);
    printf("\n\nselectionSort_2 的运行结果\n");
    for (int i = 0; i < 10; i++)    printf("%d ", b[i]);

    Sleep(3000);
    return 0;
}

插入排序

将要排序的数据分为两组，并假设第一个元素为已排序的数据，其余元素为未排序的数据；
将未排序的数据中的第一个数据，与已排序的数据比较，在已排序数据中发现的第一个比该数大的数时，将该数插入到第一个比该数大的数的位置；（通过将插入位置之后的元素后移实现）
直到所有的数都插入到已排序数据中，插入排序结束。

#include <stdio.h>
#include <windows.h>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)

void insertionSort(int* arr, int size) {
    for (int j = 1; j < size; j++) {
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[j]) {
                int tem = arr[j];
                for (int k = j; k > i; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[i] = tem;
                break;
            }
        }
    }
}

int main()
{
    int arr[10] = { 1,25,3,4,85,6,2,4,7,65 };

    insertionSort(arr,10);

    for (int i = 0; i < 10; i++)    printf("%d ", arr[i]);

    Sleep(3000);
    return 0;
}

冒泡排序

冒泡排序 size 个数，依次比较相邻的两个数，当大数在小数前面时，就交换两个数的位置；
当从左到右全部扫描一边之后，小数会左移一位，而最大的数会移到最后，此时算作完成一次冒泡；
第二遍从左到右扫描结束，小数会再次左移一位，而第二大的数会移到倒数第二个位置；
当完成 size-1 次冒泡后，所有的数全部排序完成，冒泡排序结束。

#include <stdio.h>
#include <windows.h>
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable : 4996)

void bubbleSort_1(int* arr, int size) {
    // 冒泡排序中，i 表示冒泡的次数，而不表示元素下标。
    // 假设有 size 个数要排序，那么最多最需经过 size-1 次冒泡
    for (int i = 0; i < size-1; i++) {
        // 每次冒泡都会完成一个数的排序，所以每次比较的次数较上次减一
        for (int j = 0; j < size-1-i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tem = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tem;
            }
        }
    }
}

// 有时不用达到冒泡排序的最多次数就可以完成排序，可以通过设置 元素交换的标志 优化冒泡排序
void bubbleSort_2(int* arr, int size) {
    for (int i = 0; i < size - 1; i++) {
        bool bubble = false;
        for (int j = 0; j < size - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tem = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tem;
                bubble = true;
            }
        }
        if (bubble == false) {
            break;
        }
    }
}

int main()
{
    int arr[10] = { 1,25,3,4,85,6,2,4,7,65 };

    //bubbleSort_1(arr, 10);
    bubbleSort_2(arr, 10);
    for (int i = 0; i < 10; i++)  printf("%d ", arr[i]);

    Sleep(3000);
    return 0;
}

The End

在以上代码的示例中，都是从左至右遍历数据的。此时，选择排序 & 插入排序已排序的数据先出现在左边，而冒泡排序已排序的数据先出现在右边。当然，通过改变遍历的方向可以改变已排序数据先出现的位置。
在传统解释中，选择排序，即选择未排序数据中最小的数，排列到已排序数据的末尾。
插入排序，即将未排序数据中的第一个数据插入到已排序数据的合适位置。这两者都较容易理解。
冒泡排序，一般理解为使较小的数像冒泡一样逐渐上浮至靠前排的位置。而笔者认为，冒泡排序更明显的特征在于，每一次冒泡都会使未排序的数据中最大的那个数据沉淀到最右边（从左至右扫描时）。所以对笔者而言，可能叫“沉淀排序”比冒泡排序更容易理解些。