八大排序（二）

一、堆排序

1.大顶堆的构建

1.大顶堆的构建
（大、小顶堆）
堆排序运用到完全二叉树（完全二叉树：从上到下，从左到右依次铺满）
堆排序是利用了平衡二叉树的一些特点来实现完全二叉树

完全二叉树：
完全二叉树是一种特殊的二叉树，要求从上到下从左到右依次平铺
[5,7,4,2,0,3,1,6]

大顶堆：
在完全二叉树的基础之上，每个节点的值都大于或者等于左右孩子的值

小顶堆：
在完全二叉树的基础之上，每个节点的值都小于或者等于左右孩子的值
上述完全二叉树转换为大顶堆为

实际上是利用了完全二叉树的特点来构建大顶堆

任何一个节点的左子节点：arr[2i+1]

任何一个节点的右子节点：arr[2i+2]

任何一个节点的父子节点：arr[(i-1)/2]

构建大顶堆
1.parent游标从后往前移动，如果当前节点没有子树直接跳过
2.如果当前节点有字数，先让child游标执行左子树
3.判断该节点有没有左子树，如果有child游标指向左右子树当前最大的值
4.当前节点和child节点的值进行对比，如果当前节点大于child的值，parent游标继续向前移动
5.如果当前节点小于child的值，父子节点的值进行交换
5.1parent游标指向child游标的位置，child游标的地址：2*child+1
5.1.1如果child游标指向空，parent游标继续向前移动
5.1.2如果child游标指向不为空，那么重复第五步
构建大顶堆的代码如下：

public static void main(String[] args) {
    
	int[] arr=new int[] {
    5,7,4,2,0,3,1,6};
	for(int p=arr.length-1;p>=0;p--) {
    
		sort(arr,p);
		
	}
			
}

public static void sort(int[] arr,int parent) {
    
	//定义左子树
	int child=2*parent+1;
	while(child<arr.length-1) {
    
		//排序
		//判断有没有右子树，以及比较左右字数谁大，child指针指向大的
		int rchild=child+1;
		if(rchild<=arr.length-1 && arr[rchild]>arr[child]) {
    
			child++;
		}
		//父子节点进行对比交换
		if(arr[parent]<arr[child]) {
    
			//交换
			int temp=arr[parent];
			arr[parent]=arr[child];
			arr[child]=temp;
			
			parent=child;
			
			 child = 2 * child+1;
			
		}else {
    
			break;
		}
		
	}
	
}

2.堆顶元素和堆底元素互换

//堆底元素和堆顶元素进行互换，如何保证当前最大值不在参与构建
		//每次大顶堆排序结束之后，进行堆顶堆底元素交换，最后一个节点将不在进行下一次大顶堆的构建，要进行排序的数据长度减去1
		for(int a=arr.length-1;a>0;a--) {
    
			int temp=arr[0];
			arr[0]=arr[a];
			arr[a]=temp;
			sort(arr,0,a);
		}

综上可得堆排序的整体代码为：

public static void main(String[] args) {
    
		int[] arr = new int[] {
    2,6,8,5,4,7,9,3,1,0};
		//构建大顶堆
		for(int p=arr.length-1;p>=0;p--) {
    
			sort(arr,p,arr.length);
		}
		//堆底元素和堆顶元素进行互换，如何保证当前最大值不在参与构建
		//每次大顶堆排序结束之后，进行堆顶堆底元素交换，最后一个节点将不在进行下一次大顶堆的构建，要进行排序的数据长度减去1
		for(int a=arr.length-1;a>0;a--) {
    
			int temp=arr[0];
			arr[0]=arr[a];
			arr[a]=temp;
			sort(arr,0,a);
		}
		
		System.out.println("堆排序的输出结果是：");
		
		System.out.println(Arrays.toString(arr));
	}
	
	public static void sort(int[] arr,int parent,int length) {
    
		
		//因为有孩子一定是先有左孩子
		int Child = 2*parent + 1;
		//判断程序是否执行的条件
		while(Child<length) {
    
			
			//判断左右孩子谁更大
			//定义一个右孩子
			//判断有没有右子树，以及比较左右字数谁大，child指针指向大的
			int rChild = Child + 1 ;
			if(rChild < length && arr[rChild]>arr[Child]) {
    
				Child++;
			}
			//父子节点的值进行对比
			if(arr[parent] < arr[Child]) {
    
				//如果parent游标的值比Child游标的值小，就进行位置交换
				int temp=arr[parent];
				arr[parent] = arr[Child] ;
				arr[Child] = temp;
				
				//parent游标指向Child游标的位置
				parent=Child;
				//Child游标的地址是：2*Child+1
				Child=2*Child+1;
			}
			//为了避免出现死循环
			else {
    
				break;
			}
		}
	}
	

二、快速排序

在了解快速排序之前首先要了解递归的思想

1.方法1

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);//递归关系
		
		
	}

1，2，3，4，5，…，n 求它的前n项和
利用循环方法：

int sun=0;
for(int i=1;i<n;i++){
    
	sun=sun+i;
}

递归出口：当n=1时，返回值为n；
递归关系：其他时候，返回值是（n-1）+1；
代码：

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

1.2 快速排序的总体代码

public static void sort(int[] arr,int left,int right) {
    
		
		int l=left;
		int r=right;
		while(l< r) {
    
			
			if(arr[l]>=arr[l+1]) {
    
				int temp=arr[l];
				arr[l]=arr[l+1];
				arr[l+1]=temp;
				l++;
			}
			else if(arr[l]<arr[l+1]) {
    
				int temp=arr[l+1];
				arr[l+1]=arr[r];
				arr[r]=temp;
				r--;
			}
		}
		if(left<l-1) {
    
			sort(arr,left,l-1);
		}
		if(l+1<right) {
    
			sort(arr,l+1,right);
		}
		
		
	}

快速排序输出的结果：

2.方法2

2.2 基本思想

①把左边第一个数当作基数；
②定义两个指针在第一个（i）和最后一个位置（j）；
③j指针先移动，然后好到比基准数小的数后，停止；
④i指针向后移动，找到比基准数大的数后，停止；
⑤数据互换
⑥i和j相遇时 指针的位置与基准数进行互换，基准数到达其相应的位置
⑦ 进行递归直到排好序

①②：
③④：

⑤
⑥

2.2 代码

public static void main(String[] args) {
    
		int[] arr=new int[]{
    2,6,9,3,5,8,7,4,1,0};
		sort(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
		
	}

	public static void sort(int[] arr,int left,int right) {
    
		
		//递归出口
		if(left>=right) {
    
			return;
		}
		
		
		//1+ 定义一个数作为基准数
		int base=arr[left];
		//2+ 定义i和j两个游标
		int i=left;
		int j=right;
		//3+ i和j不相遇
		while(i!=j) {
    
			//j从后向前移动，去找比当前基准数小的数值
			while(arr[j]>=base && i<j) {
    
				j--;
			}
			//i游标向前移动去找比当前基准数大的数值
			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;
		
		//递归关系
		sort(arr,left,i-1);
		sort(arr,i+1,right);
		
	}
	

三、归并排序

归并排序也用到了递归的思想对数据进行拆分

	public static void main(String[] args) {
    
		int[] arr=new int[] {
    1,5,9,6,3};
		sort(arr,0,arr.length-1);
		System.out.println("归并排序的输出结果是：");
		System.out.println(Arrays.toString(arr));
	}
	
	//采用递归进行拆分
	public static void sort(int[] arr,int left,int right) {
    
		//递归出口
		if(left>=right) {
    
			return;
		}
		int mid=(left+right)/2;
		//递归关系
		sort(arr,left,mid);
		sort(arr,mid+1,right);
		merage(arr,left,mid,right);
		
	}
	
	public static void merage(int[] arr,int left,int mid,int right) {
    
		
		//定义出临时数组
		int[] temp=new int[right - left+1];
		
		//定义s1，s2
		int s1=left;
		int s2=mid+1;
		//遍历临时数组
		int i=0;
		
		//将数据写入到临时数组中去 
		while(s1<=mid && s2<=right) {
    
			//谁小谁往当前的数组当中去 arr[s1]小 所以s1到临时数组
			if(arr[s1]<=arr[s2]) {
    
				temp[i]=arr[s1];
				i++;
				s1++;
			}
			else {
    
				temp[i]=arr[s2];
				i++;
				s2++;
			}
		}
		
		//判断s1当中是否还有数据
		//当前还有数据
		while(s1<=mid) {
    
			temp[i] =arr[s1];
			i++;
			s1++;
		}
		//判断s2当中还有没有数据
		while(s2<=right) {
    
			temp[i]=arr[s2];
			i++;
			s2++;
		}
		//将临时数组中的数据放回到原来的数组当中去
		for(int j=0;j<temp.length;j++) {
    
			arr[j+left]=temp[j];
		}
	}

结果图：