蓝桥杯基础练习（1）---数列排序

一、数列排序问题的解决

问题描述

　　给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200

输入格式

　　第一行为一个整数n。
　　第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。

输出格式

　　输出一行，按从小到大的顺序输出排序后的数列。

样例输入

5
8 3 6 4 9

样例输出

3 4 6 8 9

代码实现：（冒泡排序实现）

#include <stdio.h>

int main() {
	int n,i,j,temp;
	int a[200];
	
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	} 
	
	for(i=0;i<n-1;i++)
	{
		for(j=0;j<n-1-i;j++)
		{
			if(a[j]>a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		} 
	}
	
	for(i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

代码实现（qsort（）函数实现）

#include<stdlib.h>
#include <stdio.h>


int Cmp(const void *a,const void *b){
	int x = *(int *)a;
	int y = *(int *)b;
	return x-y;
}//当然也可以直接return *(int*)a - *(int*)b;

int main() {
	int n=5,i,j,temp;
	int a[200];
	
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	} 
	qsort(a,n,sizeof(a[0]),Cmp);
	
	for(i=0;i<n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

二、交换排序

1、冒泡排序

（1）主要思想（以从小到大排序为例）

        1）设将需要排序的一组元素放入某个数组中，然后从第一个元素开始，与下一个元素进行比较，若为逆序，则交换；若正序，则继续进行下一次比较。通过这样一次比较，就把这组元素中的最大值交换到了最后一个位置，然后继续重复这个操作，直至实现要求。

        2）通过双重for循环（或者一个while循环，一个for循环）实现相邻元素的比较以及排序。

（2）冒泡法的几种实现代码

        1）双重for循环且第二个循环变量为递增

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

        2)双重for循环且第二个循环变量为递减

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

         3)一个while循环，一个for循环，且第二个循环变量为递增

	int flag = 1, i=0;//flag是用来标记某一次排序是否发生交换
	while(i<n&&flag==1){
		flag = 0;//flag置0，表示若某一趟没有发生交换，则不会进行下一次的排序
		for(j=0;j<n-i-1;j++){
			if(a[j] > a[j+1]){
				flag = 1;
				int tmp = a[j];
				a[j] = a[j+1];
				a[j+1] = tmp;
			}
		}
	} 

        4）一个while循环，一个for循环，且第二个循环变量为递减

                只需要将上述方法中的3）和4）结合一下就好了。

冒泡排序法是所有的排序方法中最简单的一个，只要理解了冒泡排序的思想，基本就可以写出来的。但是最主要的还是自己写，只有自己写了才知道自己哪里会出错，然后记下来，防止下次出错。

（3）冒泡排序法的效率分析

        1）时间复杂度：

最好情况：正序排列，这种情况不需要交换操作，只需要一次排序，n-1次比较操作，所以时间复杂度为O(n);

最坏情况：逆序排列，这种情况需要n-1次排序，比较次数就是达到最大值（以1为公差的1~n前n项和）:O(n²)，交换次数达到最大值（每次交换时移动3次记录，所以为3×以1为公差的1~n前n项和）:O(n²)，所以最坏时间复杂度为O(n²)。

        2）空间复杂度：只有在交换位置时需要一个临时辅助空间做暂存记录，所以为O(1)。

2、快速排序

（1）主要思想（以从小到大排序为例）

        1）在需要排序的一组元素中，设low指向第一个元素，high指向最后一个元素，并且随机找一个元素作为枢轴（一般都是设这些元素的第一个）。

        2）high的指向从右边开始向左移动，选取第一个比枢轴小的元素与枢轴的位置交换；然后low的指向从左边开始向右移动，选取第一个比枢轴大的元素与枢轴的位置交换。重复这两步操作，直至low与high相同，此时，这组元素被分为两个子表，枢轴左边的元素均小于枢轴元素，右边的元素大于枢轴元素，这算完成一次排序。

        3）重新选择一个新的枢轴，重复1）和2）操作，直到完成排序。

（2）快速排序法的实现代码

/*获取枢轴位置，并将数组分为两个子表(左边比枢轴元素小，右边比枢轴元素大)*/
int Partition(int a[],int low,int high){
	int pivot = a[low];
	while(low < high){ //high指针从后向前遍历，寻找第一个比枢轴元素小的元素与枢轴元素交换
		while(low < high && a[high] >= pivot){
            --high;//此处先减后用还是先用后减其实都可以 
        }
        a[low] = a[high]; 
            
       
        while(low < high && a[low] <= pivot){ //low指针从前向后遍历 ,寻找第一个比枢轴元素大的元素与枢轴元素交换
            ++low;
        }
        a[high] = a[low];
    }
    a[low] = pivot;
    return low; 
}
void QuickSort(int a[],int low,int high){
    if(low<high){  //递归出口 
        int pivot = Partition(a,low,high);
        QuickSort(a,low,pivot-1);  //比枢轴元素小的部分继续调用快速排序 
        QuickSort(a,pivot+1,high);   //比枢轴元素大的部分继续调用快速排序 
    } 
}

对于c++中头文件#include<stdlib.h>里面的qsort函数实质上完成了上述的这些操作，所以在会使用这个函数时，可以直接调用，用法在我优势洗牌的那个文章里面有说明，在上面数列排序的代码实现中也用到了。

（3）快速排序法的效率分析

  1）时间复杂度：

最好情况：每一趟排列后都能将记录序列分为两个长度大致相同的子表，此时的递归树就是一个二叉树，类似折半查找；在n个元素的序列中，对枢轴元素定位所需时间为O(n),所以此时时间复杂度大致为为O(nlog2n);

最坏情况：是已经排好序的情况，此时，其递归树为单支树，每次划分只能得到一个比上一次上一个的子序列，这种情况需要n-1趟才能将所有记录定位，而且第i趟需要经过、n-i次比较，所以最坏时间复杂度大致为O(n²)。

平均时间复杂度：O(nlog2n)。

        2）空间复杂度：快速排序是递归的，执行时需要有一个栈来存放相应的数据。最大递归调用次数与递归树的深度一致，所以说最好情况下的空间复杂度是O(log2n)，最坏情况是O(n)。