package cn.sort;
import java.util.Scanner;
//各种控排序算法
public class Test {
    public static void main(String[] args) {
        int array[] = {22, 11, 9, 8,90, 7, 42};
        System.out.println("没有排序之前：");
        Sortall.print(array);
        System.out.println();
        int num =1;
        
        System.out.println("请输入需要排序的方法序号：");
        System.out.println("1:简单选择排序");
        System.out.println("2:堆排序");
        System.out.println("3:冒泡排序");
        System.out.println("4:归并排序");
        System.out.println("5:基数排序");
        System.out.println("6:快速排序");
        
        System.out.println("0：退出程序");
        
        boolean loop = true;
        while(loop){
            Scanner sc = new Scanner(System.in);
            num = sc.nextInt();
        switch(num){
        case 0:
            loop=false;
            System.out.println("退出程序");
            break;
        case 1://简单选择排序
            Sortall.SelectSort(array);    
            System.out.println();
            break;
        case 2:
            //堆排序
            Sortall.HeapSort(array);
            System.out.println();
            break;
        case 3:    
            //冒泡排序
            Sortall.BubbleSort(array);
            System.out.println();
            break;
        case 4:
            //归并排序
            Sortall.MergeSort(array);
            System.out.println();
            break;
        case 5:
            //基数排序
            Sortall.BaseSort(array);
            System.out.println();
            break;
        case 6:
            //快速排序
            Sortall.QuickSort(array);
            System.out.println();
            break;
        default: 
            System.out.println("无效输入\n");
            break;
        }
        }
    }
}

package cn.sort;

import java.util.ArrayList;
import java.util.List;

public class Sortall{
    //重写print方法输出数组
    static void print(int array[]) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+"    ");
        }
    }
    //交换函数
    static void Swap(int a [],int i,int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    //1.选择排序
  public static void SelectSort(int []array){
      System.out.println("----------------1.使用选择排序之后:    ----------------------");
     for(int i=0;i<array.length;i++){
       int lowindex=i;
     for(int j=i+1;j<array.length;j++){
       if(array[j]<array[lowindex]){
         lowindex=j;
     }
    }
      int temp=array[i];
      array[i]=array[lowindex];
      array[lowindex]=temp;
   }
     print(array);
  }
//-------------------------另一种选择排序的写方法--------------------------------------------------------
 public static void xuanZe1(int []array){
     for(int i=0;i<array.length;i++){
     for(int j=i+1;j<array.length;j++){
       if(array[j]<array[i]){
      Swap(array, i, j);
       }
    }
     
   }
     for(int i=0;i<array.length;i++){
       System.out.print(array[i]+" ");
    }
  }
 //2.二分法查找数据
public static int BinarySearch(int[] array, int num) {
    
    int begin = 0;
    int end = array.length-1;
    while (begin <= end) {
        int mid = (int)Math.floor((begin+end)/2);
        for (int i = 0; i < array.length; i++) {
            if (array[mid] == num) {
                System.out.println("在数组中找到"+num+"的位置为："+mid);
                return mid;
            }else if (array[mid] < num) {
                begin = mid +1;
            }else{
                end = mid -1;
            }
        }
    }
    return -1;
}
  //3.冒泡排序
public static void BubbleSort(int[] array) {
    System.out.println("----------------3.使用冒泡排序之后:    -----------------------");
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = array.length - 1; j >i ; j--) {
            if (array[j]<array[j-1]) {
                Swap(array, j, j-1);
            }
        }
    }
}
//堆排序
public static void HeapSort(int[] array) {
    System.out.println("----------------2.使用堆排序之后:    -----------------------");
    //循环建堆
    for (int i = 0; i < array.length; i++) {
        buidMaxHeap(array, array.length - 1 - i);
        //交换堆顶和最后一个元素
        Swap(array, 0, array.length-i-1);
    }
    System.out.println("输出排序：");
    print(array);        
}
//建堆
private static void buidMaxHeap(int[] data,int lastIndex) {
    //从lastIndex处最后一个节点的父节点开始
    for (int i = (lastIndex - 1)/2; i  >= 0; i--) {
        //k保存正在判断的节点
        int k = i;
        //如果当前k节点的子节点存在
        while (k*2+1 <= lastIndex) {
            //k节点的左子节点的索引
            int biggerIndex = 2*k + 1;
            //如果biggerIndex小于lastIndex，即biggerIndex代表的k节点的右子节点存在
            if (biggerIndex < lastIndex) {
                //如果右子节点的值较大
                if (data[biggerIndex] < data[biggerIndex + 1]) {
                    //biggerIndex总是记录较大子节点的索引
                    biggerIndex++;
                }
            }
            //如果k节点的值小于其较大的子节点的值
            if (data[k]<data[biggerIndex]) {
                //交换他们
                Swap(data, k, biggerIndex);
            }else{
                break;
            }
        }
    }
    print(data);
}
//快速排序
public static void QuickSort(int[] array) {
    System.out.println("----------------6.使用快速排序之后:    -----------------------");
    if (array.length>0) {
        quick(array, 0, array.length-1);
    }
    print(array);
}
static void quick(int a[], int low, int high){
    if (low < high) {
        int middle = getMiddle(a, low, high);
        quick(a, 0, middle-1);
        quick(a, middle+1, high);
    }
}
static int getMiddle(int a[],int low,int high){
    int temp = a[low];
    while(low < high){
        while(low < high && a[low]<= temp){
            low ++;
        }
        a[high] = a[low];
    }
    a[low] = temp;
    return low;
}
//归并排序
public static void MergeSort(int[] array) {
    System.out.println("----------------4.使用归并排序之后:    -----------------------");
    if (array.length>0) {
        mergeSort(array, 0, array.length - 1);
    }
    print(array);
}
private static void mergeSort(int[] a, int left, int right) {
    if(left<right){
        int middle = (left+right)/2;
        //对左边进行递归
        mergeSort(a, left, middle);
        //对右边进行递归
        mergeSort(a, middle+1, right);
        //合并
        merge(a,left,middle,right);
    }
}
private static void merge(int[] a, int left, int middle, int right) {
    int[] tmpArr = new int[a.length];
    int mid = middle+1; //右边的起始位置
    int tmp = left;
    int third = left;
    while(left<=middle && mid<=right){
        //从两个数组中选取较小的数放入中间数组
        if(a[left]<=a[mid]){
            tmpArr[third++] = a[left++];
        }else{
            tmpArr[third++] = a[mid++];
        }
    }
    //将剩余的部分放入中间数组
    while(left<=middle){
        tmpArr[third++] = a[left++];
    }
    while(mid<=right){
        tmpArr[third++] = a[mid++];
    }
    //将中间数组复制回原数组
    while(tmp<=right){
        a[tmp] = tmpArr[tmp++];
    }
}
//基数排序
public static void BaseSort(int[] array) {
    System.out.println("----------------5.使用基数排序之后:    -----------------------");
     //找到最大数，确定要排序几趟
    int max = 0;
    for (int i = 0; i < array.length; i++) {
        if(max<array[i]){
            max = array[i];
        }
    }
    //判断位数
    int times = 0;
    while(max>0){
        max = max/10;
        times++;
    }
    //建立十个队列
    List<ArrayList> queue = new ArrayList<ArrayList>();
    for (int i = 0; i < 10; i++) {
        ArrayList queue1 = new ArrayList();
        queue.add(queue1);
    }
    //进行times次分配和收集
    for (int i = 0; i < times; i++) {
        //分配
        for (int j = 0; j < array.length; j++) {
            int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
            ArrayList queue2 = queue.get(x);
            queue2.add(array[j]);
            queue.set(x,queue2);
        }
        //收集
        int count = 0;
        for (int j = 0; j < 10; j++) {
            while(queue.get(j).size()>0){
                ArrayList<Integer> queue3 = queue.get(j);
                array[count] = queue3.get(0);
                queue3.remove(0);
                count++;
            }
        }
    }
    print(array);
}

}