数组的常用五种排序算法

2024-01-14 21:03:19 作者:欧亿体育

目录

一、排序算法介绍

二、算法代码实现

1、选择法排序

2、冒泡法排序

3、交换法排序

4、插入法排序

5、折半法排序


一、排序算法介绍

1、选择法排序

    选择法排序在排序过程中一共需要进行 n(n-1)/2 次比较,互相交换 n-1 次。选择法排序简单、容易实现,适用于数量较小的排序。

2、冒泡法排序

    最好的情况是正序,因此只要比较一次即可;最坏的情况是逆序,需要比较 n*n 次。冒泡法排序是稳定的排序方法,当待排序列有序时,效果比较好。

3、交换法排序

    交换法排序和冒泡法排序类似,正序时最快,逆序时最慢,排列有序数据时效果最好。

4、插入法排序

    插入法排序需要经过 n-1 次插入过程,如果数据恰好应该插入到序列的最后端,则不需要移动数据,可节省时间。因此,若原始数据基本有序,此算法具有较快的运算速度。

5、折半法排序

    折半法排序对于较大的 n 时,是速度最快的排序算法;当时当 n 很小时,此方法往往比其他排序算法还要慢。折半法排序是不稳定的,对应有相同关键字的记录,排序后的结果可能会颠倒次序。

    以上5种排序算法:插入法、冒泡法、交换法排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能打到较快的速度;当 n 较小时,对稳定性不做要求时,宜选用选择法排序;对稳定性有要求时,宜选用插入法或者冒泡法排序

二、算法代码实现

1、选择法排序

(1)选择法排序是指 每次选择所要排序的数组中的最大值(最小值)的数组元素,将这个数组元素与最前边没有进行排序的数组元素的值互换。

(2)每次都将下一个数字和剩余数字中的最小数字进行位置互换,直到将一组数字按从小到大排序。

(3) 排序的比较次数:n(n-1)/2,每次循环选出最大(最小)值,并交换位置。

#include
int main()
{
    int i,j;                                        // 存储数值最小的数组元素的数值和该元素的位置
    int a[10];                                      // 存储输入的数据
    int iTemp;
    int iPos;
    printf("为数组元素赋值: \n");

    // 从键盘为数组元素赋值
    for(i=0; i<10; i++)
    {
        printf("a[%d] = ",i);
        scanf("%d",&a[i]);
    }

    // 从小到大排序
    for(i=0; i<9; i++)                              // 设置外层循环为下标 0~8 的元素
    {
        iTemp = a[i];                               // 设置当前元素的最小值
        iPos = i;                                   // 记录当前元素的位置
        for(j=i+1; j<10; j++)                       // 设置内层循环为 i+1 ~ 9
        {
            if(a[j] < iTemp)                        // 如果当前元素比最小值还小
            {
                iTemp = a[j];                       // 重新设置最小值
                iPos = j;                           // 记录新的元素位置
            }
        }
        // 交换两个元素值
        a[iPos] = a[i];
        a[i] = iTemp;
    }

    // 输出数组
    for(i=0; i<10; i++)
    {
        printf("%d\t",a[i]);                        // 输出制表符
        if(i == 4)                                  // 如果是第五个元素,则换行,方便查看
        {
            printf("\n");
        }
    }
    return 0;
}

2、冒泡法排序

(1)冒泡法排序是指 每次比较数组中相邻的两个数组元素的值,将较小的数排在较大的数前面(从小到大排列)。

(2)第一次排序过程中将最小的数字移动到第一的位置,并将其他数字依次向后移动。

(3)每次都将剩余数字中的最小数字移动到当前剩余数字的最前方,直到将一组数字按从小到大的排序为止。

#include
int main()
{
    int i,j;
    int a[10];                                      // 声明一个整形数组
    int iTemp;
    printf("为数组元素赋值:\n");

    // 通过键盘为数组元素赋值
    for(i=0; i<10; i++)
    {
        printf("a[%d]=",i);
        scanf("%d",&a[i]);
    }

    // 从小到大排序
    for(i=1; i<10; i++)                             // 外层循环元素下标为1~9
    {
        for(j=9; j>=i; j--)                         // 内层循环元素下标为i~9
        {
            if(a[i] < a[j-1])                       // 如果前一个数比后一个数大,交换数据
            {
                iTemp = a[j-1];
                a[j-1] = a[j];
                a[j] = iTemp;
            }
        }
    }

    // 输出数组
    for(i=0; i<10; i++)
    {
        printf("%d\t",a[i]);
        if(i == 4)
        {
            printf("\n");
        }
    }
    return 0;
}

3、交换法排序

(1)交换法排序是指 将每一位数字与其后的所有数一一进行比较,如果发现符合条件的的数据则交换数据。

(2)首先,用第一个数依次与其后的所有数字进行比较,如果存在比其值大(小)的数,则交换这两个数后,继续向后比较其他数,直到最后一个数。

(3)如果遇到比当前数字小的数则交换位置,依次类推,直到将一组数字按照从小到大排序为止。

#include
int main()
{
    int i,j;
    int a[10];
    int iTemp;
    printf("请为数组元素赋值:\n");

    // 通过键盘为数组元素赋值
    for(i=0; i<10; i++)                             // 为元素循环赋值
    {
        printf("a[%d]= ",i);
        scanf("%d",&a[i]);
    }

    // 从小到大排序
    for(i=0; i<9; i++)                              // 外层循环元素下标为 0~8
    {
        for(j=i+1; j<10; j++)                       // 内层循环元素下标为 i+1到9
        {
            if(a[j] < a[i])                         // 如果当前值比其他值大
            {
                iTemp = a[i];                       // 交换两个数值
                a[i] = a[j];
                a[j] = iTemp;
            }
        }
    }

    // 输出数组
    for(i=0; i<10; i++)
    {
        printf("%d\t",a[i]);
        if(i == 4)
        {
            printf("\n");
        }
    }
    return 0;
}

4、插入法排序

(1)插入法排序是指 抽出一个数据,在前面的数据中寻找相应的位置插入,然后继续下一个数据,直到完成排序。

(2)第一次排序时将第一个数字取出,放在第一的位置;然后进行第二次排序,先取出第二个数字,与第一个进行比较,如果小则插入在前,如果大则插入在后。

(3)不断取出未进行排序的数字与排序好的数字进行比较,(先与排在后的面的数字进行比较),并插入到相应的位置,直到完成排序。

#include
int main()
{
    int i;                                          
    int a[10];                                      // 存储用户输入的数字
    int iTemp;                                      // 存储两个元素交换时的中间变量和记录元素位置
    int iPos;
    printf("请为数组元素赋值:\n");

    // 通过键盘为数组元素赋值
    for(i=0; i<10; i++)                             // 为元素循环赋值
    {
        printf("a[%d]= ",i);
        scanf("%d",&a[i]);
    }

    // 从小到大排序
    for(i=0; i<10; i++)                             // 循环数组中的元素
    {
        iTemp = a[i];                               // 设置插入值
        iPos = i-1;
        while((iPos >= 0) && (iTemp < a[iPos]))     // 寻找插入值的位置
        {
                a[iPos+1] = a[iPos];                // 插入数值
                iPos--;
        }
        a[iPos+1] = iTemp;
    }

    // 输出数组
    for(i=0; i<10; i++)
    {
        printf("%d\t",a[i]);
        if(i == 4)
        {
            printf("\n");
        }
    }
    return 0;
}

5、折半法排序

(1)折半法排序又称为快速法排序,是指 选择一个中间值 middle(在程序中使用数组的中间值),然后把比中间值小的数据放在左边,比中间值大的数据放在右边。

(2)第一次比较完成后分别对中间值两边的数据进行递归比较,直到将一组数字按照从小到大排序为止。

        1)在第一次排序中,首先取中间值,从左右两侧分别取出数据与中间值进行比较:

        2)(左侧比较从第一个元素开始)   当左侧取出的数据比中间值大时,则交换两个互相比较的数组元素值;

        3)(右侧比较从最后一个元素开始) 当右侧取出的数据比中间值大时,取前一个数组元素的值继续与中间值进行比较,如果右侧这个值比中间值小,则交换位置。

        4)当中间值两侧的数据都比较一遍以后,数组以第一个元素为起点,以中间值的元素为终点,按照上面的方法继续进行比较;

        5)右侧以中间值为起点,数组最后一个元素为终点,按照上述方法继续比较。

#include

// 声明一个排序函数
void CelerityRun(int left, int right, int array[]);

int main()
{
    int i;
    int a[10];
    printf("为数组元素赋值:\n");
    // 通过键盘为数组元素赋值
    for(i=0; i<10; i++)
    {
        printf("a[%d]=",i);
        scanf("%d",&a[i]);
    }

    // 从小到大排序函数
    CelerityRun(0,9,a);

    // 输出数组
    for(i=0; i<10; i++)
    {
        printf("%d\t",a[i]);                        // 输出制表符
        if(i == 4)                                  // 如果是第五个元素,则换行,方便查看
        {
            printf("\n");
        }
    }
    return 0;
}

// 排序函数功能实现
void CelerityRun(int left, int right, int array[])
{
    int i,j;
    int middle,iTemp;
    i = left;
    j = right;
    middle = array[(left + right)/2];               // 求中间值
    do
    {
        while((array[i] < middle) && (i < right))   // 第一个内层循环,从最左边开始找小于中间值的数,如果找到大于中间值的数结束
        {
            i++;                                    // 左侧数组的值分别与中间值比较一次,找打大于中间值的数结束左侧循环
        }
        while((array[j] > middle) && (j > left))    // 第二个内层循环,从最右边开始找大于中间值的数,如果找到小于中间值的数结束
        {
            j++;
        }
        if(i <= j)                                  // 找到了一对值,进行数值交换
        {
            iTemp = array[i];
            array[i] = array[j];
            array[j] = iTemp;
            i++;
            j--;
        }
    } while (i <= j);                               // do-while 设计外层循环,如果两边的下标交错(保证左右两边的数都与中间值比较了一次),就停止循环(完成一次排序)

    // 递归排序左边的数据
    if(left < j)
    {
        CelerityRun(left,j,array);
    }
    
    // 递归排序右边的数据
    if(right > i)
    {
        CelerityRun(right,i,array);
    }
}

在线咨询 拨打电话

电话

010-67916526

微信二维码

微信二维码