链接：https://blog.csdn.net/xu__jun/article/details/78331111

1、选择排序-简单选择排序

选择排序是最简单的一种基于O(n^2)时间复杂度的排序算法，基本思想是从 i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最大（小）值。

数据结构——排序（C实现)

实现：

void selectSort(int arr[],int n)
{
    int i,j,minValue,tmp;
    //一趟确定一个有序元素，最后一次不要确定，所以只需n-1次
    for(i=0;i<n-1;i++)
    {
        minValue=i;
        //  确定无序区最小元素下标
        for(j=i+1;j<n;j++)
        {
            if(arr[minValue]>arr[j])
            {
                minValue=j;
            }
        }
        //如果无序区第一个元素最小，则没有必要交换
        if(minValue!=i)
        {
            tmp=arr[i];
            arr[i]=arr[minValue];
            arr[minValue]=tmp;
        }
    }
}
//打印函数
printArray(int arr[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

int main()
{

    int arr[10]={28,9,7,6,5,1,3,11,45,66};
    printArray(arr,10);
    selectSort(arr,10);
    printArray(arr,10);
    return 0;
}

数据结构——排序（C实现)

如上所示，简单的选择排序复杂度固定为O(n^2)，每次内循环找出没有排序数列中的最小值，然后跟当前数据进行交换。由于选择排序通过直接查找最值得方法进行排序，循环次数几乎是固定的（n次）

优化：（链接：https://blog.csdn.net/hansionz/article/details/80862590）

另外一种优化方法是每次循环同时找出最大值和最小值可以使循环减少为（n/2次）

数据结构——排序（C实现)

优化实现：

void selectSort(int arr[],int n)
{
    int left=0;
    int right=n-1;
    while(left<right)
    {
        int max=left;  //记录无序区最大元素下标
        int min=left;  //记录无序区最小元素下标
        int j=0;
        for(j=left+1;j<=right;j++)
        {
            //找出最小元素的下标
            if(arr[j]<arr[min])
            {
                min=j;
            }
            //找出最大元素的下标
            if(arr[j]>arr[max])
            {
                max=j;
            }
        }
        //最小值若是第一个则没有必要交换
        if(min!=left)
        {
            int tmp=arr[left];
            arr[left]=arr[min];
            arr[min]=tmp;
        }
        //若最大元素的下标是left，前面已经和最小元素交换过了，此时最大元素的下标应该是min
        if(max==left)
        {
            max=min;
        }
        //最大值如果是最后一个则没必要交换
        if(max!=right)
        {
            int tmp=arr[right];
            arr[right]=arr[max];
            arr[max]=tmp;
        }
        left++;
        right--;
    }
}
//打印函数
printArray(int arr[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

int main()
{

    int arr[10]={10,9,8,7,6,5,4,3,2,1};
    printArray(arr,10);
    selectSort(arr,10);
    printArray(arr,10);
    return 0;
}

数据结构——排序（C实现)

2、冒泡排序

冒泡排序在一组需要排序的数组中，对前后两后数据进行比较，交换数据，使大的数据往后移，每趟怕许将最大的数放到最后的位置上：

数据结构——排序（C实现)

代码实现：

bubbleSort(int arr[],int n)
{
    int i,j,tmp;
    for(i=0;i<n-1;i++)  //最后一趟不用比较，故n-1次
    {
        for(j=1;j<n;j++)
        {
            if(arr[j]<arr[j-1])
            {
                tmp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=tmp;
            }
        }
    }
}
//打印函数
printArray(int arr[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[10]={10,9,8,7,6,5,4,3,2,1};
    printArray(arr,10);
    bubbleSort(arr,10);
    printArray(arr,10);
    return 0;
}

数据结构——排序（C实现)

优化：

（1）、对于外层循环，如当前序列已经有序，即不再进行交换，应该不再进行接下来的循环直接跳出

（2）、对于内层循环后面最大值1已经有序的情况应该不再进行循环

代码实现：

bubbleSort(int arr[],int n)
{
    int i,nflag,tmp;
    do
    {
        nflag=0;
        for(i=0;i<n-1;i++)
        {
            if(arr[i]>arr[i+1])
               {
                   tmp=arr[i+1];
                   arr[i+1]=arr[i];
                   arr[i]=tmp;
                   nflag=i+1;
               }
        }
        n=nflag;
    }while(nflag);  
    //当nflag为0时，说明本次循环没有发生交换，序列已经有序不用再循环，如果nflag>0则记录了随后依次发生交换的位置，还位置以后的序列都是有序的，循环不再往后进行
}
//打印函数
printArray(int arr[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d\t",arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[10]={10,9,8,7,6,5,4,3,2,1};
    printArray(arr,10);
    bubbleSort(arr,10);
    printArray(arr,10);
    return 0;
}

数据结构——排序（C实现)

1、选择排序-简单选择排序

2、冒泡排序

相关推荐