package 数组排序算法;

public class 反转排序 {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int [] arr =  new int[] {2,4,6,8,10,9,7,5,3,1};
		反转排序.sort(arr);
	}
	public static void sort(int[] arr) {
		System.out.println("原一维数组:");
		反转排序.showarr(arr);
		for (int i = 0; i <arr.length/2;i++) {
			arr[i] 				^= 	arr[arr.length-1-i];
			arr[arr.length-1-i] ^= arr[i];
			arr[i] 				^= arr[arr.length-1-i];
		}
		System.out.println("反转排序后的一维数组:");
		反转排序.showarr(arr);
	}
	public  static void showarr(int[]arr) {
		for (int tmp:arr) {
			System.out.print(tmp+"\t");
		}
		System.out.println();
	}
}

执行结果：

//已有一个升序排列的整数数组(含20个整数)，要求从键盘输入一个整数后，将该数插入数组，并保持升序，输出该数组的数值验证程序的正确性。
package test_Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Scanner;
public class ArrayTest {
public static void main(String[] args){
ArrayTest at = new ArrayTest();
at.sortArray();
//为了体现Java语言的封装特性，我们将主要的执行方法至于main()方法之外
}
Object sortArray(){
/*
*这里我们首先创建一个数组并初始化
*然后讲数组转化为集合后加入从键盘输入的数
*最后将集合再转化为数组
*然后调用Arrays.sort()方法在foreach中输出
*
*/
int[] array = new int[]{-9,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9};
//这里加入泛型机制，是程序安全性更高
Collection arrayList = new ArrayList();
System.out.println("Old array‘s length:"+array.length);
for(int i=0;i
System.out.print(" "+array[i]);
arrayList.add(new Integer(array[i]));
}
System.out.print("\n"+"Please input a number:");
arrayList.add(new Integer(input()));
System.out.println("Current array‘length:"+arrayList.size());
Object[] now=arrayList.toArray();
Arrays.sort(now);
for(Object currentArray:now){
System.out.print(" "+currentArray);
}
return arrayList;
}
static int input() {
int input = (new Scanner(System.in)).nextInt();
return input;
}
}

1、自动排序用到了java.util.Arrays里面的sort方法，导好包直接使用就好。
2、倒序就是将第一个和倒数第一个交换、第二个和倒数第二个交换…以此类推，找到规律就用for循环将他们进行交换就好。
import java.util.Arrays;

public class ArraySortText {
	public static void main(String[] args) {
		
		//声明构建初始化数组
		int[] arr = {5,3,9,4,6,8,2};
		/*
		 * 
		 * 使用java.util.Arrays里面的sort方法
		 * 对数组arr进行升序排列（这个方法只能升序排列）
		 *
		 */
		Arrays.sort(arr);
		
		//遍历自动排序数组
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		
		//对排列好的数组进行倒序（从大排到小）
		for (int i = 0; i < arr.length/2; i++) {
			int x = arr[i];
			arr[i] = arr[arr.length-i-1];
			arr[arr.length-i-1] = x;
		}
		//对倒序好的数组进行遍历
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}
/*
 * 结果：
 * 2 3 4 5 6 8 9 
 * 9 8 6 5 4 3 2 
 */


倒序的第二种做法：
		//倒序的第二种做法
		for (int start = 0,end = arr.length-1;start <= end; start++,end--) {
			int x = arr[start];
			arr[start] = arr[end];
			arr[end] = x;
		}

作为java语言的使用者，我们应该都知道java自动封装了Array的工具类，其中我们可能常用的Sort排序方法到底是调用了哪个排序方法呢？

JDK8中Arrays.sort的底层原理，调用的是插入排序，归并排序和快速排序。简单来说就是根据数组长度的大小选择合适排序方法。
元素少于47用插入排序
元素大于等于47小于286的用快速排序
至于大于286的，它会进入归并排序（Merge Sort），但在此之前，它有个小动作（就是看数据具不具备结构）
结构简单来说也就是局部有序。


下面是测试算法
public class ArraySorts {

    /**
     * 不带参数的快速排序
     * @param arr
     */
    public static  void  quickSort(int[] arr){
        int start = 0;
        int end  = arr.length-1;
        quickSortHelp(arr,start,end);

    }
    /*
        调用快速排序
     */
    public static  void  quickSortHelp(int[] arr,int start,int end) {
        if(start<end){
            int middle = quickHelp(start,end,arr);
            quickSortHelp(arr,middle+1,end);
            quickSortHelp(arr,start,middle-1);
        }
    }

    /**
     *
     * @param start
     * @param end
     * @param arr
     * @return 第一个元素应该在的位置
     */
    public static int  quickHelp(int start,int end, int[] arr){

        int temp = arr[start];
        while (start<end){

            while (arr[end]>temp&&start<end){
                end--;
            }
            //从尾部找到比temp小的值  然后换到前面
            arr[start] = arr[end];

            while (arr[start]<temp&&start<end){
                start++;
            }
            //同理
            arr[end] = arr[start];
        }
        //放置temp
        arr[start] = temp;
        //返回位置索引
        return start;
    }

    /**
     * 插入排序
     * @param arr
     */
    public static void insertSort(int arr[])
    {
        //数组的长度为1 直接返回
        if(arr.length<=1){
            return;
        }
        else {
            //记录保存插入的值
            int temp;
            for (int i = 1; i <arr.length ; i++) {
                //记录插入的值
                temp = arr[i];
                while (i>0&&arr[i-1]>temp) {
                    arr[i] = arr[i-1];
                    i--;
                }
                arr[i] = temp;
            }
        }


    }


    /**
     * 合并有序数组
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] mergeArray(int[]arr1,int[] arr2){
        //申请一个新数组
        int[] arr3 = new int[arr1.length+arr2.length];
        int flag1 = 0;
        int flag2 = 0;
        int flag3 = 0;
        while (flag1<arr1.length&&flag2<arr2.length){
            if(arr1[flag1]<arr2[flag2]){
                arr3[flag3] = arr1[flag1];
                flag1++;
            }
            else {
                arr3[flag3] = arr2[flag2];
                flag2++;
            }
            flag3++;
        }
        //数组1 元素结束
        if(flag1>=arr1.length){
            for (int i = flag2; i <arr2.length ; i++) {
                arr3[flag3] = arr2 [i];
                flag3++;
            }
        }else {
            for (int i = flag1; i <arr1.length ; i++) {
                arr3[flag3] = arr1 [i];
                flag3++;
            }
        }
        return arr3;
    }

    //数组的压缩
    /**
     * 二维数组
     * @param arr
     * @return
     */
    public static int [][] twoArray(int[][] arr){
        int[][] result;
        //判断arr的长度
        if(arr.length%2 ==0){
            result = new int[arr.length/2][];
        }else {
            result = new int[arr.length/2+1][];
        }
        for (int i = 0; i <result.length ; i++) {
            if( (i * 2 + 1) >= arr.length ) {
                result[i] = mergeArray(arr[i*2],new int[] {});
            }else {
                result[i] = mergeArray(arr[i*2],arr[i*2 + 1]);
            }
        }
        return result;
    }

    //调用返回
    public static int[] mergeArray(int[] arr){

        int [][]arrx = new int[arr.length][1];

        /**
         * 将数组分成子数组，每一个子数组内有一个数，所以都是有序的
         */

        for(int i=0;i<arr.length;i++)
        {
            arrx[i] = new int[]{arr[i]};
        }

        int arry[][] = arrx;
        while (arry.length>1){
            arry = twoArray(arry);
        }

        return arry[0];

    }

}