3种简单排序：冒泡、选择、插入排序的概念及实现代码

　　做题时遇到排序的问题，解题思路还是比较清晰，涉及到数据的排序，打算直接用插入排序直接快速水过去，没想到来到排序部分这里，内外的循环边界不清晰，导致直接越界出错，浪费时间，调试了多遍。因为这部分比较重要掌握不好直接影响后面其他快排算法的学习，所以写这篇当作复习巩固。

影响排序的效率因素

简单来说主要有：排序的稳定性，时间性能，辅助空间，算法的复杂度

• 排序的稳定性

比如排序（2，3，1（第一个），1（第二个），5，6）

不稳定的排序，可能会排出（1（第二个），1（第一个），2，3，5，6）；

不稳定的情况下程序需要做更多的比较和移动，相当稳定的排序效率低

• 时间性能

是排序算法的重要衡量标志，在排序时主要进行比较和移动，高效率的排序应该尽可能少的元素比较和尽可能少的移动

• 辅助空间

即执行算法所需要的辅助存储空间，以及待排序所占用的空间

• 算法复杂性

这里指的是算法本身的复杂度，如果算法本身庞大且复杂显然会影响其排序的性能

本文排序用到的公共结构与函数

采用简单、易于理解的顺序表(数组)来演示

typedef strut{
    int data[MAXSIZE+1]; //使用data[0]作为哨兵，提高程序可读性
    int length;                  //记录顺序表长度 
}list;

排序时最常用到的操作就是交换，将他写成函数swap

void swap(list *s,int i,int j){
    int temp = s->data[i];
    s->data[i]=s->data[j]
    s->data[j]=temp;
}

冒泡排序

排序原理：每两个相邻元素之间进行，反序则交换，一直交换到没有反序的元素为止。“冒泡”的含义是从后面开始进行两两比较，交换后符合的元素就往上冒。

实现代码：

void BublleSort(list *s){
    for(int i = 1; i < s->length-1;i++)
        for(int j = s->length-1;j >= i;j--)
            if(s->data[j] > s->data[j+1])
                swap(s,j,j+1);
}

冒泡排序for循环的作用（结果）：

第一层i循环结束时data[i]是i之后的元素中中最小的元素

第二层是为了两两比较交换，作用是将小的往上冒

改进思路：

我们每进行了一次第一层for循环后，data[i]已经是最小了，以及i之后的元素相比上一次for循环是相对有序的，而我们目前的程序没有利用这样以后相对有序的结果，再次进行两两比较，降低了效率。

比如：

当遇到21345的情况时，避免i以及循环了，且交换1，2后为：12345，
i循环到了3发现没有交换，但是i又还继续循环了4，5。

代码改进

int flag = 1;
void BublleSortPlus(list *s){
    for(int i = 1; i < s->length && flag; i++)
    {//当循环了某个i之后没有发生交换，表明i之后的元素以排序
        flag = 0;
        for(int j = s->length - 1;j >= i;j--){
            if(s->data[j] > s->data[j+1])
            {
                swap(s,j,j+1);
                flag = 1;
            }
        }
    }
}

选择排序

排序原理：第i个元素，与他 i 之后的n-i个元素进行比较，如果发现小的元素，记录下标，直到之后所有的元素比较完，就将data[i]和data[min]进行交换

实现代码：

void SelectSort(list *s){
    for(int i = 1; i < s->length;i++){
        int min = i;
        for(int j = i + 1; j <= s->length;j++)
            if(s->data[min] > s->data[j]) 
                min = j;
        if(min != i)    swap(s,i,min);
    }
} 

插入排序

插入排序相对于前面两种平均时间复杂度是比较低的，只有O(n^2/4),不过最差复杂度都是O(n^2)

排序原理：类似我们打扑克牌，拿到牌后进行整牌。拿到第 i 个元素与他前面的i-1个元素进行比较，比较时将元素往后挪，直到遇到比data[i]小的元素，就插入。因为i时从2开始所以确保了i之前的元素时有序的。

void InsertSort(list *s){
    int i,j;
    for(i = 2;i <= s->length;i++){
    //i遍历为第二个到第n个。 
        if(s->data[i]<s->data[i-1]){
            s->data[0] = s->data[i];
            int j;
            for(j = i-1;s->data[j] > s->data[0];j--){
                s->data[j+1] = s->data[j];
            }
            s->data[++j] = s->data[0];
        }
    }
}