排序方式（3）==＞快速排序和归并排序

4.快速排序
快速排序简称快排，主要运用的是递归的主要思想
递归
递归是一个方法调用自身的方法

递归主要是包括递归关系和递归出口
例：
①数组{1，2，3，4，5，…，n}
递归出口：当n=1时，返回值为n；
递归关系：其他时候，返回值是（n-1）+1；
代码：

public static int run(int n) {
		if(n==1)
			return 1;//递归出口
		return run(n-1)+1;//递归关系
	}

②斐波那契数列
{1，1，2，3，5，8，13，…}
第三项等于前两项相加
递归出口：当n=1，n=2时，返回值均为1；
递归关系：其他情况下，返回前两项的和，即为F（n-1）+F（n-2）；
代码：

public static int FI(int n) {
		if(n==1) {
			return 1;
		}
		else if(n==2) {
			return 1;//递归出口
		}
		else
			return FI(n-1)+FI(n-2);//递归关系
		
		
	}

③数组的前n项和
递归出口：当n=1时，输出值为1；
递归关系：其他情况，输出前（n-1）项和加第n项的值，即为sum(n-1)+n
代码：

public static int sum(int n) {
		if(n==1) {
			return 1;//递归出口
		}
		else
			return sum(n-1)+n;//递归关系
	}

递归步骤：
①把左边第一个数当作基数；
②定义两个指针在第一个和最后一个位置；
③后边的指针先移动，然后好到比基准数小的数后，停止；
④前边的指针向后移动，找到比基准数大的数后，停止；
⑤数据互换
代码：

public class QuickSort {
	public static void main(String[] args) {
		int[] arr=new int[] {5,9,2,1,7,6,3,4,8,0};
		qucik(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	public static void qucik(int arr[],int left,int right) {
		if(left>right) {
			return;
		}
		int base=arr[left];
		int i=left;
		int j=right;
		while(i!=j) {
			while(arr[j]>=base && i<j) {
				j--;
			}
			while(arr[i]<=base && i<j) {
				i++;
			}
			int temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;	
		}
		arr[left]=arr[i];
		arr[i]=base;
		
		qucik(arr,left,i-1);
		qucik(arr,i+1,right);
		
	}
	
	

结果图：

5.归并排序
归并排序运用了分治法的主要思想，主要通过寻找中间变量进行排序
代码：

public static void main(String[] args){
		int[] arr=new int[] {5,8,2,1,7,6,3,4,9,0};
	
	}
	
	public static void fen(int arr,int left, int right) {
		if(left>right) {
			return ;
		}
		int mid=(left + right)/2;
		
		fen(arr,left,mid);
		fen(arr,mid+1,right);
		
	}
	public static void he(int[] arr,int left, int right,int mid) {
		int s1=left;
		int s2=mid+1;
		//定义临时数组
		int[] temp=new int[right-left+1];
		int index=0;
		//将两个数组当中的小的数据放到临时数组中去
		while(s1<mid && s2<=right) {
			if(arr[s1]<=arr[s2]){
				temp[index]=arr[s1];
				index ++;
				s1 ++;
			}
			else {
				temp[index]=arr[s1];
				index ++;
				s2 ++;
			}
		}
		while(s1<mid) {
			temp[index]=arr[s1];
			index ++;
			s1 ++;
		}
		while(s1<right) {
			temp[index]=arr[s1];
			index ++;
			s2 ++;
		}
		for(int j=0;j<temp.length;j++) {
			arr[j+left]=temp[j];
		}
		
		
	}
	

结果图：