c语言排序方法有哪几种

c语言排序方法有：1、简单选择排序，基于O（n2）时间复杂度的排序算法；2、冒泡排序；3、简单插入排序；4、希尔排序；5、归并排序，基于归并操作的一种排序算法；6、快速排序，属于分治法的一种；7、堆排序等。

本教程操作环境：windows7系统、C++17版本、Dell G3电脑。

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

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

算法实现：

void selectSort(int arr[], int n)
{    int i, j , minValue, tmp;    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;
        }
    }
}void printArray(int arr[], int n)
{    int i;    for(i = 0; i < n; i++)
    {        printf("%d ", arr[i]);
    }    printf("\n");
}void main()
{    int arr[10] = {2,5,6,4,3,7,9,8,1,0};
    printArray(arr, 10);
    selectSort(arr, 10);
    printArray(arr, 10);    return;
}

如实现所示，简单的选择排序复杂度固定为O(n2)，每次内循环找出没有排序数列中的最小值，然后跟当前数据进行交换。由于选择排序通过查找最值的方式排序，循环次数几乎是固定的，一种优化方式是每次循环同时查找最大值和最小值可以是循环次数减少为（n/2），只是在循环中添加了记录最大值的操作，原理一样，本文不再对该方法进行实现。

2.冒泡排序

冒泡排序在一组需要排序的数组中，对两两数据顺序与要求顺序相反时，交换数据，使大的数据往后移，每趟排序将最大的数放在最后的位置上，如下：

算法实现：

void bubbleSort(int arr[], int n)
{    int i, j, tmp;    for(i = 0; i < n - 1; i++)
    {        for(j = 1; j < n; j++)
        {            if(arr[j] < arr[j - 1])
            {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
            }
        }
    }
}void printArray(int arr[], int n)
{    int i;    for(i = 0; i <b>本文来源gao@dai!ma.com搞$代^码!网7</b>< n; i++)
    {        printf("%d ", arr[i]);
    }    printf("\n");
}void main()
{    int arr[10] = {2,5,6,4,3,7,9,8,1,0};
    printArray(arr, 10);
    bubbleSort(arr, 10);
    printArray(arr, 10);    return;
}

如上是一种最简单的实现方式，需要注意的可能是i, j的边界问题，这种方式固定循环次数，肯定可以解决各种情况，不过算法的目的是为了提升效率，根据冒泡排序的过程图可以看出这个算法至少可以从两点进行优化：
1)对于外层循环，如果当前序列已经有序，即不再进行交换，应该不再进行接下来的循环直接跳出。
2)对于内层循环后面最大值已经有序的情况下应该不再进行循环。

优化代码实现：

void bubbleSort_1(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];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                nflag = i + 1;
            }
        }
        n = nflag;
    }while(nflag);
}

喜欢 (0)赏

[搞代码]

分享 (0)