排序--------简单排序

/*-------冒泡排序----------
    函数名: bubble_sort
	功能  : 实现升序排序
	参数  : 带排序的数组，数组的长度
	返回值 :为空
	描述：时间复杂度为O(n^2)，辅助空间为O(1)；
	      有一种变形的冒泡排序--　鸡尾酒排序，
		  它是双向的冒泡排序，时间复杂度也为O(n^2).
	-------------------------*/
void bubble_sort(int *bubble, int Length)
{
	int i,j;
	int  temp;
	int count;
	count = Length;
	for(i = 0; i < Length; i++)
	{
		count--;             //每一次产生最大数后，下面要遍历的数组长度减1；
		for(j = 0; j < count; j++)
		{
			if(bubble[j] < bubble[j+1])
			{
				temp = bubble[j];
				bubble[j] = bubble[j+1];
				bubble[j+1] = temp;
			}
		}
	}
}

/*--------插入排序-----------
    函数名: insert_sort
	功能  : 实现升序排序
	参数  : 带排序的数组，数组的长度
	返回值 :为空
	描述：时间复杂度为O(n^2)，辅助空间为O(1)；
	-------------------------*/
void insert_sort(int *insertion, int Length)
{
	int i,j;
	int temp;
	for(i = 0; i < Length; i++)
	{
		for(j = i; j >= 1; j--)
		{
			if(insertion[j] > insertion[j-1])
			{
				temp = insertion[j];
				insertion[j] = insertion[j-1];
				insertion[j-1] = temp;
			}
		}
	}
}
/*--------选择排序-----------
    函数名: select_sort
	功能  : 实现升序排序
	参数  : 带排序的数组，数组的长度
	返回值 :为空
	描述：时间复杂度为O(n^2)，辅助空间为O(1)；
	-------------------------*/
void select_sort(int *selection, int Length)
{
	int i, j;
	int flag=0,temp;//flag标志最小的位置
	int Min;
	for(i = 0; i < Length; i++)
	{
		Min = selection[i];
		for(j = i; j < Length; j++)
		{
			if(Min > selection[j])
			{
				flag = j;
				Min = selection[j];
			}
		}
		temp = selection[i];
		selection[i] = Min;
		selection[flag] = temp;
	}
}

  关于冒泡排序的，后来看到如果在进行length遍之前就已经排序好的话，也就会做白白的循环，所以下面改了程序设置了一个标志，但没有发生交换的时候，证明已经排完序了。

 

void bubble_sort(int *bubble, int Length)  
{  
    int i,j;  
    int  temp;  
    int count, flag = 0;  
    count = Length;
	
    for(i = 0; i < Length; i++)  
    {  
        count--;             //每一次产生最大数后，下面要遍历的数组长度减1；  
        for(j = 0; j < count; j++)  
        {  
            if(bubble[j] > bubble[j+1])  
            { 
				flag = 1;
                temp = bubble[j];  
                bubble[j] = bubble[j+1];  
                bubble[j+1] = temp; 
            } 
			

        }  
		if(flag == 0)
			{
				break;
			}
		else
		{
			flag=0;
		}
    }  
}

评论

2 楼 梅陇菜粿 2011-08-11  

加油！

1 楼 中国小虫 2011-08-08