1 堆排序
步骤(以升序排列为例,排序完结后数组开端为最大值):
- 从最初一个非叶子结点开始(叶结点天然不必调整,第一个非叶子结点 arr.length/2-1),从左至右,从下至上进行调整,最终将一个无序序列结构成一个大根堆,此时序列头就是最大值。
- 将堆顶元素与开端元素进行替换 ,使开端元素最大, 即 将最大元素 ” 沉 ” 到数组末端 。而后持续调整堆;再将 堆顶元素与次开端元素替换,失去第二大元素; 如此重复进行替换、重建、替换。
import java.util.ArrayList;
import java.util.Arrays;
public class HeapSort {public static void main(String[] args){int []arr = {7,6,7,11,5,12,3,0,1};
System.out.println("排序前:"+ Arrays.toString(arr));
sort(arr);
System.out.println("排序后:"+Arrays.toString(arr));
}
public static void sort(int[] array){
//1. 构建大顶堆
// 从第一个非叶子节点开始,从左至右,从下到上调整
for(int i=array.length/2-1;i>=0;i--){adjustHeap(array,i,array.length);
}
//2. 重复替换堆顶和开端元素,最终实现排序
for(int i=array.length-1;i>0;i--){swap(array,0,i);
adjustHeap(array,0,i);
}
}
// 调整大顶堆
//len 示意调整到数组的第几个元素,比方第 n 轮替换,阐明是倒数第 n 个元素与顶部替换,那么 len=array.length-n
public static void adjustHeap(int[] array,int index,int len){int temp=array[index];
for(int i=index*2+1;i<len;i++){ // 从左子节点开始调整
// 如果存在左右子节点,抉择左右子节点中值较大的点
if(i+1<len && array[i]<array[i+1])
i++;
if(array[i]>temp){array[index]=array[i];// 此处只将子节点的值赋值给父节点,并不是替换
index=i; ////index 调整到换下来的子节点的地位,持续看子结构有没有呈现凌乱
}else
break;
}
array[index]=temp; // 将 temp 值放到最终的地位
}
public static void swap(int []array,int a ,int b){int temp=array[a];
array[a] = array[b];
array[b] = temp;
}
}
2 疾速排序
重点:
- public static void quickSort(int[] array,int left,int right){}办法
- 每次先右指针左移,保障了最初 l,r 相遇当前所对应的值,肯定是小于参照点的值的,因而间接替换参照点与该点即可。
import java.util.Arrays;
public class QuickSort {public static void main(String[] args) {int[] array = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(array);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int[] array){quickSort(array,0,array.length-1);
}
public static void quickSort(int[] array,int left,int right){if(left>right)
return;
int temp=array[left];
int l=left,r=right;
while(l<r){// 每次先右指针左移,保障了最初 l,r 相遇时肯定指向 <temp 的值,这样最初与 array[left]替换当前肯定是右边小左边大。while(array[r]>=temp && l<r)
r--;
while(array[l]<=temp && l<r) {l++;}
if(l<r){// 做一次判断
swap(array,l,r);
}
}
array[left]=array[l];
array[l]=temp;
// 递归调用
quickSort(array,left,l-1);
quickSort(array,l+1,right);
}
public static void swap(int[] array,int a,int b){int temp=array[b];
array[b]=array[a];
array[a]=temp;
}
}