排序初探

冒泡排序

1、概念

将一组无序的记录序列调整为有序的记录序列（升、降序）

2、冒泡排序的基本原理

两两相邻，不停比较，不停交换，比较n轮

3、代码实现

第一步 如何比较数组中两两相邻的数
从头开始，第n个数和第n+1个数比较
for(int n =0; n < arr.Length - 1; n ++){	//arr.Length-1 因为数组下标是从0开始，所以比较次数也就相当于数组个数-1
    if( arr[n] > arr[n+1]){
        //第二步 交换位置
        int temp = arr[n];
        arr[n] = arr[n+1];
        arr[n+1] = temp;
    }
}

//第三步 换m轮 有m个数比较m轮
int[] arr = new int[]{8,7,6,1,5,4,2,6,3,9};
for(int m = 0; m < arr.Length; m++){
    for(int n =0; n < arr.Length - 1; n ++){
   		if( arr[n] > arr[n+1]){
        	int temp = arr[n];
        	arr[n] = arr[n+1];
        	arr[n+1] = temp;
    	}
	}	
}
//查看排序结果
for(int i =0; i<arr.Length;i++){
    Console.WriteLine(arr[i]);
}

第四步 优化
int[] arr = new int[]{8,7,6,1,5,4,2,6,3,9};
1、确定位置最大的数字，不用比较
    确定一轮，极值（最大、最小值）已经放到了对应的位置
    所以每完成n轮，后面位置的数，就不用再参与比较了
for(int m = 0; m < arr.Length; m++){
    for(int n =0; n < arr.Length - 1 - m; n ++){
   		if( arr[n] > arr[n+1]){
        	int temp = arr[n];
        	arr[n] = arr[n+1];
        	arr[n+1] = temp;
    	}
	}	
}
for(int i =0; i<arr.Length;i++){
    Console.WriteLine(arr[i]);
}

int[] arr = new int[]{8,7,6,1,5,4,2,6,3,9};
再优化
bool isSort = false;
for(int m = 0; m < arr.Length; m++){
    isSort = false;
    for(int n =0; n < arr.Length - 1 - m; n ++){
   		if( arr[n] > arr[n+1]){
            isSort = true;
        	int temp = arr[n];
        	arr[n] = arr[n+1];
        	arr[n+1] = temp;
    	}
	}	
}
//当一轮结束后，如果isSort是false，就是最终排序了，不需要再去多余交换了
if(!isSort){
    break;
}
for(int i =0; i<arr.Length;i++){
    Console.WriteLine(arr[i]);
}

思考1 随机数冒泡排序

//定义一个数组，长度为20，每个元素值随机0~100
//使用冒泡排序进行升序
int[] arr = new int[20];
Random random = new Random();
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = random.Next(0, 101);
    Console.Write(arr[i] + " ");
}

//外层轮数
for (int i = 0; i < arr.Length; i++)
{
    //内层比较
    for (int j = 0; j < arr.Length - 1 - i; j++)
    {
        //做比较，满足条件交换
        if (arr[j] > arr[j + 1])
        {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
Console.WriteLine();
for (int i = 0; i < arr.Length; i++)
{
    Console.Write(arr[i] + " ");
}

思考2 函数实现排序

Random random = new Random();
int[] arr = new int[10];
for (int i = 0; i < arr.Length; i++)
{
    arr[i] = random.Next(1,21);
    Console.Write(arr[i]+" ");
}
Sort(arr, false);
Console.WriteLine();
for (int i = 0; i < arr.Length; i++)
{
    Console.Write(arr[i] + " ");
}
static int[] Sort(int[] array,bool isAscendingOrder)
{
    int temp; bool order;
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length - 1 -i; j++)
        {
            order = isAscendingOrder ? array[j] > array[j + 1] : array[j] < array[j + 1];
            if (order)
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array; //数组是引用类型，不用new，直接改
}