基本排序算法的实现

1.冒泡：

#include <stdio.h>
/* 冒泡排序算法实现 */
void println(int array[], int len)
{
    int i = 0;

    for(i=0; i<len; i++)
    {
        printf("%d ", array[i]);
    }

    printf(" ");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;
}
//冒泡排序如下
void BubbleSort(int array[], int len) // O(n*n)
{
    int i = 0;
    int j = 0;
    int exchange = 1;
    //大数沉淀小数漂浮
    for(i=0; (i<len) && exchange; i++)
    {
      //表示是否发生交换优化
        exchange = 0;

        for(j=len-1; j>i; j--)
        {
            if( array[j] < array[j-1] )
            {
                swap(array, j, j-1);

                exchange = 1;
            }
        }
    }
}

int main()
{
    int array[] = {21, 25, 49, 25, 16, 8};
    int len = sizeof(array) / sizeof(*array);

    println(array, len);

    BubbleSort(array, len);

    println(array, len);

    return 0;
}
2.选择：

#include <stdio.h>
//排序结果打印
void println(int array[], int len)
{
    int i = 0;

    for(i=0; i<len; i++)
    {
        printf("%d ", array[i]);
    }

    printf(" ");
}
//数据的交换
void swap(int array[], int i, int j)
{
    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;
}
//选择排序如下
void SelectionSort(int array[], int len) // O(n*n)
{
    int i = 0;
    int j = 0;
    int k = -1;

    for(i=0; i<len; i++)
    {
      //临时变量
        k = i;

        for(j=i; j<len; j++)
        {
            if( array[j] < array[k] )
            {
                k = j;
            }
        }
        //数据交换
        swap(array, i, k);
    }
}

int main()
{
    //初始化数据
    int array[] = {21, 25, 49, 25, 16, 8};
    int len = sizeof(array) / sizeof(*array);

    println(array, len);

    SelectionSort(array, len);

    println(array, len);

    return 0;
}

3.插入：

#include <stdio.h>
/* 插入排序的实现 */
void println(int array[], int len)
{
    int i = 0;

    for(i=0; i<len; i++)
    {
        printf("%d ", array[i]);
    }

    printf(" ");
}

void swap(int array[], int i, int j)
{
    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;
}
//实现插入排序
void InertionSort(int array[], int len) // O(n*n)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;

    for(i=1; i<len; i++)
    {
        k = i;
        temp = array[k];
        //向已经排好序的一组数中插入数据(一个元素也可以看着是排好序的)
        for(j=i-1; (j>=0) && (array[j]>temp); j--)//查找有序序列进行比较temp代表目前插入的数
        {
            array[j+1] = array[j];
            k = j;
        }

        array[k] = temp;
    }
}

int main()
{
    int array[] = {21, 25, 49, 25, 16, 8};
    int len = sizeof(array) / sizeof(*array);

    println(array, len);

    InertionSort(array, len);

    println(array, len);

    return 0;
}

基本排序算法的实现

相关推荐