简单排序算法

先说说 排序 吧，
书上的定义：假设含有n个记录的序列为{ r1, r2, r3, r4, ......, r5 }，其相应的关键字为{ k1, k2, k3, ......, k4 }，需确定1，2，3，......,n的一种排列p1, p2, p3, ...... ,pn，使其相应的关键字满足Kp1 <= Kp2 <= ......<=Kpn（非递减或非递增）关系，即使的序列成为一个按关键字有序的序列{ Rp1, Rp2, ........ Rpn }，这样的 操作就成为排序。
不知道你感觉如何，反正我看得一头雾水。简单的讲排序就是将一组记录按一定的规律排列的这个操作就叫排序。需要注意的是：

1. 通常把数据元素称为记录。
2. 关键字就是指排列参照的条件，关键字有主关键字和次关键字之分。
3. 多个关键字的排序可以转换成单个关键字的排序。
4. 排序的稳定性：

简单的讲，主关键字相同的两个记录根据次关键字再次进行排序，在排序前后的顺序两个记录的前后顺序不变就排序方法是稳定的，反之排序方法则是非稳定。

5. 内排序与外排序

内排序是在排序的整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数过多，不能同时放置在内存中，整个排序过程需要在内外存之间多次进行数据交换才能进行。

这里我们主要介绍内排序的多种方法。

6. 排序算法主要受三个方面的影响：

1. 时间性能：时间复杂度
2. 空间性能：空间复杂度
3. 算法的复杂性：算法本身的复杂性

冒泡排序（由于比较简单，不过多解释 ）

屌丝冒泡排序（非正宗）

#include<stdio.h>
void Bboblesort( int a[], int n )
{
    int i, j, temp, count1=0, count2=0;
    for ( i = 0; i < n; ++i)
    {   
        for ( j = i+1; j < n; ++j)
        {
            count1++;
            if( a[i] > a[j] )
            {
                count2++;
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    printf("总共比较%d次，交换%d次\n", count1, count2 );
}
int main(int argc, char const *argv[])
{
    int a[10] = { 4, 5, 5, 6, 7, 8, 9, 0, 1, 3 };
    Bboblesort( a, 10 );
    for (int i = 0; i < 10; ++i)
    {
        printf(" %d ", a[i] );
    }
    printf("\n");
    return 0;
}

正宗冒泡排序（优化后）：

#include<stdio.h>
void Bboblesort( int a[], int n )
{
    int i, j, temp, count1=0, count2=0, flag=1; /*flag 起到标志作用，让算法得以优化*/
    for ( i = 0; i < n && flag; ++i)
    {   
        for ( j = n-1; j > i; --j)
        {
            count1++;
            flag = 0;
            if( a[j-1] > a[j] )
            {
                count2++;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
                flag = 1;
            }
        }
    }
    printf("总共比较%d次，交换%d次\n", count1, count2 );
}
int main(int argc, char const *argv[])
{
    int a[10] = { 4, 5, 5, 6, 7, 8, 9, 0, 1, 3 };
    Bboblesort( a, 10 );
    for (int i = 0; i < 10; ++i)
    {
        printf(" %d ", a[i] );
    }
    printf("\n");
    return 0;
}

选择排序：

#include <stdio.h>
void StrSel( int a[], int n )
{
    int i, j, min, temp, count1=0, count2=0;
    for ( i = 0; i < n-1; ++i)
    {
        min = i;
        for ( j = i+1; j < n; ++j)
        {
            count1++;
            if( a[j] < a[min] )
            {
                min = j;
            }
        }
        if( min != i )
        {
            count2++;
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }

    }
    printf("比较%d次，交换%d次\n", count1, count2 );
}
int main(int argc, char const *argv[])
{
    int a[10] = { 5, 6, 7, 2, 3, 1, 9, 8, 4, 0};
    StrSel( a, 10 );
    for (int i = 0; i < 10; ++i)
    {
        printf(" %d ", a[i]);
    }
    printf("\n");
    
    return 0;
}

未完，后续再更新