几种排序的方法-蒲公英云

几种排序的方法

你的名字 2022-05-21 06:11 455阅读 0赞

1、冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

void bubbletSort(int a[],int n)
{
    int i,j;
    int temp=0;
    for (i=0;i<n-1;i++)
    {
        for (j=i+1;j<n;j++)
        {
            if (a[i]>a[j])
            {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;}
        }
    }
}

2、简单选择排序的基本思想：第i趟简单选择排序是指通过n-i次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。

void selectsort(int *a,int n)
    {
        int i;
        int j;
        int temp = 0;
        int flag = 0;
        for(i = 0; i < n-1; i++) // 大循环，用于控制程序不再对已经排好序的数进行操作
        {
            temp = a[i];
            flag = i;
            for(j = i+1; j < n; j++) // 小循环，用于从前往后扫描数组并选择最小数
            {
                if(a[j] < temp)
                {
                    temp = a[j];
                    flag = j; // 目前最小的元素的下标
                }
            }
            if(flag != i) // 如果最小的元素不是进行筛选的数据中的第一个，则将最小数据与第一个筛选数据交换
            {
                a[flag] = a[i];
                a[i] = temp;
            }
        } 
    }

3、插入排序法：输入一个元素，检查数组列表中的每个元素，将其插入到一个已经排好序的数列中的适当位置，使数列依然有序，当最后一个元素放入合适位置时，该数组排序完毕。

void InsertSort(int *a,int length)  
{  
    int i,j;  
    for(i=1;i<length;i++)  
    {  
        int key=a[i];  
        for(j=i-1;j>=0;j--)  
        {  
            if(key>a[j])  
                break;  
            else  
            {  
                a[j+1]=a[j];  
                a[j]=key;  
            }  
        }  
    }  
}