冒泡排序

优点：写起来简单

缺点：运算量过大每两个之间就要比较一次

冒泡排序在一组需要排序的数组中，对两两数据顺序与要求顺序相反时，交换数据，使大的数据往后移，每趟排序将最大的数放在最后的位置上

如下图：

#include<stdio.h>
 
#define ARR_LEN 255 /*数组长度上限*/
 
void bubble_Sort(int *arr, int len) 
{
    int i, j,temp;
    for (i = 0; i < len - 1;i++) /* 外循环为排序趟数，len个数进行len-1趟 */
    { 
        for(j = 0; j < len-1-i; j++) /* 内循环为每趟比较的次数，第i趟比较len-i次 */
        { 
            if (arr[j] > arr[j + 1]) /* 相邻元素比较，若逆序则交换（升序为左大于右，降序反之）*/
            { 
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
 
int main()
{
 
    int len = 0;
    int arr[ARR_LEN] = {0};
 
    printf("please input arr len:");
    scanf("%d",&len);
 
    printf("please input arr member......\n");
    for(int j = 0;j < len;j++)
    {
        scanf("%d",&arr[j]);
    }
    puts("");
 
    printf("sort after is ......\n");
    bubble_Sort(arr,len);
    for(int j = 0;j < len;j++)
    {
        printf("%d  ",arr[j]);
    }
    putchar('\n');
 
    return 0;
}

如上是一种最简单的实现方式，需要注意的可能是i, j的边界问题，这种方式固定循环次数，肯定可以解决各种情况，不过算法的目的是为了提升效率，根据冒泡排序的过程图可以看出这个算法至少可以从两点进行优化：

对于外层循环，如果当前序列已经有序，即不再进行交换，应该不再进行接下来的循环直接跳出。

对于内层循环后面最大值已经有序的情况下应该不再进行循环。

优化代码实现：

#include <stdio.h>

#define ARR_LEN 255 /*数组长度上限*/

void bubble_Sort(int *arr, int len)
{
    int i, flag, temp;
    do
    {
        flag = 0;
        for (i = 0; i < len - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                flag = i + 1;                            
            }
        }     
        len = flag;

    }while (flag);
}

int main()
{

    int len = 0;
    int arr[ARR_LEN] = {0};

    printf("please input arr len:");
    scanf("%d", &len);

    printf("please input arr member......\n");
    for (int j = 0; j < len; j++)
    {
        scanf("%d", &arr[j]);
    }
    puts("");

    printf("sort after is ......\n");
    bubble_Sort(arr, len);
    for (int j = 0; j < len; j++)
    {
        printf("%d  ", arr[j]);
    }
    putchar('\n');

    return 0;
}

如上，当nflag为0时，说明本次循环没有发生交换，序列已经有序不用再循环，如果nflag>0则记录了最后一次发生交换的位置，该位置以后的序列都是有序的，循环不再往后进行。

---

选择排序-简单选择排序

这种方法其实和冒泡的差别不大，只是减少了交换的次数，对冒泡进行了优化。

选择排序是最简单的一种基于O（n2）时间复杂度的排序算法，基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小（大）值。

void selectSort(int arr[], int n)
{
    int i, j , minValue, tmp;
    for(i = 0; i < n-1; i++)
    {
        minValue = i;
        for(j = i + 1; j < n; j++)
        {
            if(arr[minValue] > arr[j])
            {
                minValue = j;
            }
        }
        if(minValue != i)
        {
            tmp = arr[i];
            arr[i] = arr[minValue];
            arr[minValue] = tmp;
        }
    }
}

void printArray(int arr[], int n)
{
    int i;
    for(i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

void main()
{
    int arr[10] = {2,5,6,4,3,7,9,8,1,0};
    printArray(arr, 10);
    selectSort(arr, 10);
    printArray(arr, 10);
    return;
}
#include <stdio.h>

void choose_sort(int *arr, int n);
void show(int *arr, int n);

int main()
{
    int arr[10] = {10, 8, 3, 15, 18, 16, 11, 9, 7, 6};

    /*选择排序*/
    choose_sort(arr, 10);
    show(arr, 10);
    
    return 0;
}

void choose_sort(int *arr, int n)
{
    int i = 0;
    int j = 0;
    int index = 0;
    int swap = 0;

    for(i = 0; i < n; i++) {
        index = i;
        for(j = i; j <n; j++ ) {
            if(arr[index] > arr[j]) {
                index = j;
            }
        }
        swap = arr[i];
        arr[i] = arr[index];
        arr[index] = swap;
    }
}

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

如实现所示，简单的选择排序复杂度固定为O(n2)，每次内循环找出没有排序数列中的最小值，然后跟当前数据进行交换。由于选择排序通过查找最值的方式排序，循环次数几乎是固定的，一种优化方式是每次循环同时查