【转】冒泡排序

 

public static void BubbleSort(int[] array)
{
    for (int i = 1; i < array.Length; i++)
    {
        for (int j = array.Length-1; j >= i; j--)
        {
            if (array[j]<array[j-1])
            {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
            }
        }
    }
}

static void Main(string[] args)
{
    int[] array = { 49, 38, 65, 97, 76, 13, 27, 0, 34 };
    BubbleSort(array);
    foreach (int item in array)
    {
        Console.Write(item+",");
    }
}

 

性能优化版

 

public static void BubbleSort(int[] array)
{
    bool flag = true;
    for (int i = 1; i < array.Length && flag; i++)
    {
        flag = false;//初始化为false，默认为有序了。但是如果下面的代码执行了，就会置为true
        for (int j = array.Length-1; j >= i; j--)
        {
            if (array[j]<array[j-1])
            {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                flag = true;//有交换，则设为true
            }
        }
    }
}

static void Main(string[] args)
{
    int[] array = { 49, 38, 65, 97, 76, 13, 27, 0, 34 };
    BubbleSort(array);
    foreach (int item in array)
    {
        Console.Write(item+",");
    }
}

 

 

评论

1 楼 北极的。鱼 2015-05-01  

面试题，类似冒泡排序

把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，不能申请额外的空间

一种解法：

#include <stdio.h>  
#include <string.h>  
//题目以及要求：把一个字符串的大写字母放到字符串的后面，  
//各个字符的相对位置不变，不能申请额外的空间。   
//判断是不是大写字母   
int isUpperAlpha(char c){
	if (c >= 'A' && c <= 'Z'){
		return 1;
	}
	return 0;
}
//交换两个字母   
void swap(char *a, char *b){
	char temp = *a;
	*a = *b;
	*b = temp;
}
char * mySort(char *arr, int len){
	if (arr == NULL || len <= 0){
		return NULL;
	}
	int i = 0, j = 0, k = 0;
	for (i = 0; i < len; i++){//循环的次数
		for (j = len - 1 - i; j >= 0; j--){//从最后一个元素开始向前探测
			if (isUpperAlpha(arr[j])){//如果是大写字母，那么逐个与后一个字母交换
				for (k = j; k < len - 1 - i; k++){//len-1-i为本次循环能存放的最后的位置
					swap(&arr[k], &arr[k + 1]);
				}
				break;
			}
			//遍历完了字符数组，但是没发现大写字母，所以没必要再遍历下去  
			if (j == 0 && !isUpperAlpha(arr[j])){
				//结束;  
				return arr;
			}
		}
	}
	//over:   
	return arr;
}
int main(){
	char arr[] = "aAbcAdeBbDc";
	printf("%s\n", mySort(arr, strlen(arr)));
	return 0;
}