排序算法（总结）

浏览数：17 / 时间：2015年06月08日

1. 冒泡排序

　　算法思想：两两比较相邻的记录的关键字，如果反序则交换顺序，直到没有反序记录为止！

　　算法实现：

void BubleSort(int *a, int size)
{
    int i, j;
    int flag = 1;//weather need sorted
    for(i = 0; (i < size - 1) && flag; i++)
    {
        flag = 0;
        for(j = size - 1; j > i; j--)
        {
            if(a[j-1] > a[j])
            {
                printf("compare\n");
                int temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
                flag = 1;
            }
        }
    }
}

2. 简单选择排序

　　算法思想：选择排序的第 i 次是“选择”数组中第 i 小的记录，并将该记录放到数组的第 i 个位置。其独特之处在于从未排序的序列中找到第 i 小的关键码，而很少做记录的交换，前面部分是已排序的，后面部分是未排序的。

　　算法实现：

void selectSort(int *a, int size)
{
    int i, j;
    int minIndex;
    for(i = 0; i < size; i++)
    {
        minIndex = i;
        for(j = i+1; j < size; j++)
        {
            if(a[j] < a[minIndex])
                minIndex = j;
        }
        if(i != minIndex)
        {
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
            printf("compare");
        }
    }
}

3. 直接插入排序，在基本有序队列中效率很高。

　　算法思想：将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

　　算法实现：

void insertSort(int *a, int size)
{
    int i, j, temp;
    for(i = 1; i < size; i++)
    {
        if(a[i] < a[i-1])
        {
            temp = a[i];
            for(j = i-1; j >= 0 && a[j] > temp; j--)
            {
               a[j+1] = a[j];
            }
            a[j+1] = temp;
        }
        print(a, 8);
    }
}

4. 希尔排序

　　算法思想：希尔排序利用了插入排序的最佳时间代价特性。希尔排序试图将待排序序列变成基本有序的，然后再用插入排序来完成最后的排序工作。

　　　　　　希尔排序是这样来分组并排序的：将序列分成子序列，然后分别对子序列进行排序，然后将子序列组合起来。

　　算法实现：

void inssort2(int *a, int n, int incr)
{
    int i, j;
    for(i = incr; i < n; i += incr)
    {
        for(j = i; (j >= incr) && (a[j] < a[j-incr]); j -= incr)
        {
            int temp = a[j];
            a[j] = a[j-incr];
            a[j-incr] = temp;
        }
    }
}

void shellSort(int *a, int size)
{
    int i, j;
    for(i = size/2; i>2; i/=2)
    {
        for(j=0; j<i; j++)
        {
            inssort2(&a[j], size-j, i);
        }
        print(&a[0], size);
    }
    inssort2(a, size, 1);
}