笔试中常考的排序算法

#include <stdio.h>
//打印函数
void print(int a[])
{
    int i;
    for(i=0;i<10;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
/*插入排序
    思想：顺序的把待排序的数据元素按关键字的大小插入到已排序数据元素子集合适当的位置
         子集合的数据元素个数从只有一个数据元素开始，逐次增大，当子集合大小最终和集合大小相同时，排序完毕
    平均时间复杂度：O(n^2)
*/
void insert_sort(int a[],int n)
{
    printf("fun::sizeof(a)=%d\n",sizeof(a));
    int i;
    int temp;//form 1 to the end
    for(i=0;i<n-1;i++){
        temp=a[i+1];
        int j=i;
        while(j>-1 && temp<a[j]){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;
    }
}
/*选择排序:
        思想：从待排的数据元素集合中选取关键字最小的数据元素，
        并放到数据元素集合的最前面，数据元素集合不断缩小，
        当数据元素集合为空时，选择排序结束
直接选择排序的平均时间复杂度：O(n^2)
堆排序的时间复杂度：o(nlb^n)

*/
//直接选择排序
void select_insert(int a[],int n)
{
    int i,j,min;
    int temp;
    for (i = 0; i < n-1; i++)
    {
        min=i;//每次设集合中的第一个元素关键字最小
        //
        for(j=i+1;j<n;j++){
            if(a[j]<a[min])
                min=j;
        }
        if (i!=min)
        {
            temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }

    }

}
/*
    交换排序：主要是靠交换数据元素的位置进行排序
    冒泡排序时间复杂度：O(n^2)
    快速排序时间复杂度：O(nlb^n)

*/

//冒泡排序
void bubble_sort(int a[],int n)
{
    int i,j;
    int flag=1;
    int temp;
    for (i = 0; i < n && flag==1; ++i)
    {
        flag=0;
        for (j = 0; j <n-i; ++j)
        {
            if (a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;

                flag=1;

            }
        }
    }


}
//快速排序
/*
    快速排序基本思想
        设数组元素a中存放了n个数据元素,low为数组的低端下标，
        high为数组的高端下标，从a中任取一个元素作为标准，调整数组a中各个
        元素的位置，使排在标准元素前面的元素的关键字都小于标准元素的的关键
        字，排在标准元素后面元素的关键字都大于等于标准元素的关键字。这样，标准
        元素放在了该放的位置，另外将这个数组分为了两个子数组。对这两个子数组
        再进行一样的递归快速排序，递归结束条件是low<high
    快速排序平均时间复杂度:O(nlb^n)
*/

void quick_sort(int a[],int low,int high)
{
    int i=low,j=high;
    int temp=a[low];
    while(i<j){
        while(i<j&&a[j]>a[low]) j--;//在数组右端扫描
        if (i<j)
        {
            a[i]=a[j];
            i++;
        }
        while(i<j && a[i]<a[low]) i++;//在数组左端扫描
        if (i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=temp;
    if (low<i) quick_sort(a,low,i-1);
    if (i<high) quick_sort(a,j+1,high);

}
int main()
{
    int a[10]={1,2,4,5,3,6,8,7,9,0};
    //printf("main::sizeof(a)=%d\n",sizeof(a));

    //insert_sort(a,10);
    //select_insert(a,10);
    //bubble_sort(a,10);
    quick_sort(a,0,9);
    print(a);
    return 0;
}