几种排序的方法

你的名字 2022-05-21 06:11 279阅读 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、插入排序法：输入一个元素，检查 [数组][Link 1] 列表中的每个元素，将其插入到一个已经排好序的数列中的适当位置，使数列依然有序，当最后一个元素放入合适位置时，该数组排序完毕。

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;  
                }  
            }  
        }  
    }

[Link 1]: http://baike.baidu.com/view/209670.htm