package SortMethods;
//排序算法
public class Sort {
//插入排序
//1.直接插入排序
//思想：从第二个数开始，找到在前面排好序列中的位置，
//将排好序列最后一个开始往后移动一个位置，然后插入
public void insertSort(int[] nums) {
int i, j;
for (i = 2; i < nums.length; i++) {
if (nums[i] < nums[i-1]) {
//哨兵
nums[0] = nums[i];
//将大元素后移
for (j = i - 1; nums[0] < nums[j]; j--) {
nums[j + 1] = nums[j];
}
//插入正确位置
nums[++j] = nums[0];
}
}
for (int k = 1; k < nums.length; k++) {
System.out.print(nums[k] + " ");
}
}
//2.折半插入排序
//在直接插入排序的基础上对寻找插入位置使用折半查找的方法
public void halfInsertSort(int[] nums){
int i,j,low,high,mid;
for(i=2;i<nums.length;i++){
nums[0]=nums[i];
low = 1;
high = i-1;
while(low<=high){
mid = (low+high)/2;
if(nums[i]<nums[mid]){
high = mid-1;
}else{
low = mid+1;
}
}
for(j=i-1;j>=high+1;j--){
nums[j+1]=nums[j];
}
nums[high+1]=nums[0];
}
for (int k = 1;k<nums.length;k++){
System.out.print(nums[k]+" ");
}
}
//交换排序
//1.冒泡排序
//思路：从最后一个元素开始，与前面一个元素两两比较，若倒序，则交换，经历n-1次冒泡，
// 每次将一个元素放到最终的位置上
public void bubbleSort(int[] nums){
for(int i=0;i<nums.length-1;i++){ //n-1次冒泡排序
boolean flag = false;
for(int j=nums.length-1;j>i;j--){ //从最后一个元素开始
if(nums[j]<nums[j-1]){ //倒序则交换
flag = true;
int tmp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = tmp;
}
}
if(!flag){ //如果此次没有交换说明已经有序
for (int num : nums) {
System.out.print(num + " ");
}
return;
}
}
}
//2.快速排序
//思路：默认第一个元素为基准值，将数组元素根据基准值放在基准值左右两侧，分别对左右的子数组仔进行快速排序
public void quickSort(int[] nums,int low,int high){
if(low<high){
int pivot = partition(nums,low,high);
quickSort(nums,low,pivot-1);
quickSort(nums,pivot+1,high);
}
}
public int partition(int[] nums,int low,int high){
int pivot = nums[low];
while(low<high){
while(low<high&&nums[high]>=pivot) high--;
nums[low]=nums[high];
while(low<high&&nums[low]<=pivot) low++;
nums[high]=nums[low];
}
nums[high]=pivot;
return high;
}
//选择排序
// 1.简单选择排序
//思路：每次选择剩余待排序列中最小的一个元素与待排序列第一个位置交换
public void selectSort(int[] nums){
int min;
for(int i=0;i<nums.length-1;i++){
min=i;
for(int j=i+1;j<nums.length;j++){
if(nums[j]<nums[min]){
min=j;
}
}
if(min!=i){
int temp = nums[i];
nums[i]=nums[min];
nums[min]=temp;
}
}
for(int i=0;i<nums.length;i++){
System.out.print(nums[i]+" ");
}
}
//2.堆排序
//思路：首先将数组调整为小顶堆， 然后输出第一个元素，并且与最后一个元素交换，然后调整前n-1个元素为小顶堆继续上述操作，直到只剩一个元素
//建立大顶堆
public void buildMinHeap(int[] nums,int len){
for(int i=len/2;i>0;i--){
adjustDown(nums,i,len);
}
}
//向下调整
public void adjustDown(int[] nums,int k,int len){
nums[0]=nums[k]; //nums[0]不存数据，用来暂存数据
for(int i=2*k;i<=len;i*=2){
if(i<len&&nums[i+1]>nums[i]) i++; //取值较大的子节点的下标
if(nums[0]>=nums[i]) {
break; //符合大顶堆，结束
} else{
nums[k]=nums[i]; //将较大元素调整到双亲结点上
k=i; //从当前位置继续向下筛选
}
}
nums[k]=nums[0]; //将本次调整的根节点放入最终位置
}
//堆排序
public void heapSort(int[] nums){
buildMinHeap(nums,nums.length-1);//初始建堆
for(int i=nums.length-1;i>1;i--){ //n-1趟建堆和交换
//交换堆顶元素和堆底元素
int temp = nums[i];
nums[i]=nums[1];
nums[1]=temp;
adjustDown(nums,1,i-1);
}
for(int i=1;i<nums.length;i++){
System.out.print(nums[i]+" ");
}
}
//归并排序
//思路：将整个序列从中间分为两段分别进行归并排序，再将结果进行merge，形成最终有序序列
public void merge(int[] nums,int low,int mid,int high){
//将nums复制到辅助数组中
int[] temp = new int[nums.length];
for(int i=0;i<nums.length;i++){
temp[i]=nums[i];
}
int i,j,k;
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){ //遍历辅助数组的左右两部分
//将较小的元素复制到nums中
if(temp[i]<=temp[j]){
nums[k]=temp[i++];
}else{
nums[k]=temp[j++];
}
}
//将左右两部分未检测完的复制到nums中
while(i<=mid) nums[k++]=temp[i++];
while(j<=high) nums[k++]=temp[j++];
}
public void mergeSort(int[] nums,int low,int high){
if(low<high){
int mid = (low+high)/2;
mergeSort(nums,low,mid);
mergeSort(nums,mid+1,high);
merge(nums,low,mid,high);
}
}
public static void main(String[] args) {
//待排序列
//插入排序中，第一个位置为哨兵，不存放数据
int[] nums = {0, 2, 1, 4, 3, 7, 6, 5};
Sort test = new Sort();
//直接插入排序
// System.out.println("直接插入排序：");
// test.insertSort(nums);
// //折半插入排序
// System.out.println("\n折半插入排序：");
// test.halfInsertSort(nums);
//冒泡排序
// System.out.println("\n冒泡排序：");
// test.bubbleSort(nums);
//快速排序
// System.out.println("\n快速排序：");
// test.quickSort(nums,0,nums.length-1);
// for (int num:nums){
// System.out.print(num+" ");
// }
// //简单选择排序
// System.out.println("\n简单选择排序：");
// test.selectSort(nums);
// //堆排序
// System.out.println("\n堆排序：");
// test.heapSort(nums);
//归并排序
System.out.println("\n归并排序：");
test.mergeSort(nums,0,nums.length-1);
for (int i:
nums) {
System.out.print(i+" ");
}
}
}
