1.冒泡排序
//冒泡排序public static void bubblingSort(int[] array,int ord){boolean isSort=true;//优化for (int i=0;i<array.length-1;i++){isSort=false;for (int j=0;j<array.length-1-i;j++){if (array[j]>array[j+1] && ord==1){//正序int tmp=array[j];array[j]=array[j+1];array[j+1]=tmp;isSort=true;}else if (array[j]<array[j+1] && ord==2){//倒序int tmp=array[j];array[j]=array[j+1];array[j+1]=tmp;isSort=true;}}}}
2.选择排序
//选择排序public static void selectionSort(int[] array,int ord){for (int i=0;i<array.length-1;i++){for (int j=i+1;j<array.length;j++){if (array[i]>array[j] && ord==1){//正序int tmp=array[i];array[i]=array[j];array[j]=tmp;}else if (array[i]<array[j] && ord==2){//倒序int tmp=array[i];array[i]=array[j];array[j]=tmp;}}}}
3.插入排序
//插入排序public static void insertionSort(int[] array,int ord){for (int i=0;i<array.length-1;i++){if (array[i+1]<array[i] && ord==1){//正序int tmp=array[i+1];int j;for (j=i+1;j>0 && array[j-1]>tmp;j--){array[j]=array[j-1];}array[j]=tmp;}else if (array[i+1]>array[i] && ord==2){//倒序int tmp=array[i+1];int j;for (j=i+1;j>0 && array[j-1]<tmp;j--){array[j]=array[j-1];}array[j]=tmp;}}}
4.快速排序
//快速排序public static void quickSort(int[] arr,int low,int high,int ord){int i,j,temp,t;if(low>high){return;}i=low;j=high;temp = arr[low];//temp就是基准位while (i<j && ord==1) {//正序while (temp<=arr[j]&&i<j) {//先看右边，依次往左递减j--;}while (temp>=arr[i]&&i<j) {//再看左边，依次往右递增i++;}if (i<j) {//如果满足条件则交换t = arr[j];arr[j] = arr[i];arr[i] = t;}}while (i<j && ord==2) {//倒序while (temp>=arr[j]&&i<j) {//先看右边，依次往左递减j--;}while (temp<=arr[i]&&i<j) {//再看左边，依次往右递增i++;}if (i<j) {//如果满足条件则交换t = arr[j];arr[j] = arr[i];arr[i] = t;}}//最后将基准为与i和j相等位置的数字交换arr[low] = arr[i];arr[i] = temp;quickSort(arr, low, j-1,ord);//递归调用左半数组quickSort(arr, j+1, high,ord);//递归调用右半数组}
5.希尔排序
//希尔排序public static void shellSort(int[] arr,int ord){//增量gap并逐步的缩小增量for (int gap=arr.length/2;gap>0;gap/=2){//从第gap个元素 逐步对其所在组进行//直接插入如排序for (int i=gap;i<arr.length;i++){int j=i;int temp=arr[j];if (arr[j]<arr[j-gap] && ord==1){//正序while (j-gap>=0 && temp<arr[j-gap]){arr[j]=arr[j-gap];j -= gap;}// 当退出while后就给temp//找到插入的位置arr[j]=temp;}else if (arr[j]>arr[j-gap] && ord==2){//倒序while (j-gap>=0 && temp>arr[j-gap]){arr[j]=arr[j-gap];j -= gap;}// 当退出while后就给temp//找到插入的位置arr[j]=temp;}}}}
6.归并排序
//归并排序public static void mergerSort(boolean flag, int[] a ,int left, int mid, int right){//定义辅助数组int [] t = new int[a.length];int m = left; //记录第一个序列首编号int n = mid+1; //记录第二个序列首编号int k = left;if (flag) {//升序while(m<=mid && n<=right) {if (a[m] <= a[n]) { //这个“=”需要在这里，否则不能保证其优点中的第二点。t[k] = a[m];k++;m++;} else {t[k] = a[n];k++;n++;}}}else{//降序while (m<=mid && n<=right){if(a[m]>=a[n]){t[k++]=a[m++]; //这种形式与升序中的 t[k]=a[m]; k++; m++;的效果是一样的}else{t[k++]=a[n++];}}}while(m<=mid){ //若第一个序列还有数字，就把数字插入辅助数组后面t[k++]=a[m++];}while(n<=right){t[k++]=a[n++];}//将辅助数组中的元素复制到原数组相应位置while(left < k){a[left]=t[left];left++;}}public static void divide(boolean flag, int[] a, int first, int last){int mid = 0;if (first < last){mid = (first+last)/2;divide(flag, a, first, mid); //对第一序列进行递归排序divide(flag, a, mid+1,last); //对第二序列进行递归排序mergerSort(flag, a, first, mid, last); //进行合并}}
7.堆排序
//堆排序public static void heapSort(int[] arr,int ord){if (ord==1){bigHeap(arr);// 大顶堆}else if (ord==2){smallHeap(arr);// 小顶堆}int size = arr.length;while (size > 1 && ord==1){//将堆顶与最小叶子节点进行交换swap(arr,0,size-1);// 将此时最小叶子节点移除（前堆顶）size--;// 将剩余数组重新变成大堆顶heapRestRec(arr,0,size);}while (size > 1 && ord==2){//将堆顶与最小叶子节点进行交换swap(arr,0,size-1);// 将此时最小叶子节点移除（前堆顶）size--;// 将剩余数组重新变成小堆顶smallHeapRes(arr,0,size);}}// 将一个数组变成大堆顶形式public static void bigHeap(int[] arr){for (int i = 0; i < arr.length; i++) {int currentIndex = i;int fatherIndex = (i-1)/2;while (arr[fatherIndex]<arr[currentIndex]){swap(arr,fatherIndex,currentIndex);// 将现节点往上移，看上面是否满足情况currentIndex = fatherIndex;fatherIndex = (currentIndex-1)/2;}}}// 将其重新变成大堆顶形式// 迭代写法public static void heapRest(int[] arr, int index, int size){int left = index*2 +1;int right = index*2 +2;int bigIndex;// 直到所有节点都大于子节点退出while (left < size){// 比较左右叶子节点大小，记录为bigindexif (right <size && arr[right] > arr[left] ){bigIndex = right;}else {bigIndex = left;}// 如果子节点的最大值大于父节点，则进行交换if (arr[bigIndex] > arr[index]){swap(arr,bigIndex,index);// 为了确保交换后的子节点仍然大于其子子节点，将index换为bigIndex,继续与其子节点进行比较index = bigIndex;left = index*2 +1;right = index*2 +2;}else {// 如果父节点大于子节点，则跳出循环break;}}}// 将其重新变成大堆顶形式// 递归写法public static void heapRestRec(int[] arr, int index, int size){int left = index*2 +1;int right = index*2 +2;int bigIndex;// 确定递归的出口，即右节点超出数组引索范围if (left >= size){return;}if (right<size && arr[right]> arr[left]){bigIndex = right;}else {bigIndex = left;}if (arr[bigIndex] > arr[index]){swap(arr,bigIndex,index);// 将bigindex作为父节点，继续下探heapRestRec(arr,bigIndex,size);}}// 将数组转换为小顶堆public static void smallHeap(int[] arr){for (int i = 0; i < arr.length; i++) {int cur = i;int father = (i-1)/2;while (arr[cur] < arr[father]){swap(arr,cur,father);cur = father;}}}// 将剩余数组转换为小顶堆private static void smallHeapRes(int[] arr, int index, int size) {int left = index*2+1;int right = index*2 +2;int smallInd;if (left >= size){return;}if (right < size && arr[right]<arr[left]){smallInd = right;}else {smallInd = left;}if (arr[index] > arr[smallInd]){swap(arr,index,smallInd);smallHeapRes(arr,smallInd,size);}}public static void swap(int[] arr, int ind1, int ind2){int temp = arr[ind1];arr[ind1] = arr[ind2];arr[ind2] = temp;}
程序主入口：
控制台输入一串数字，选择排序方法，进行排序（正序、倒序）
//程序入口public static void main(String[] args){Scanner scan=new Scanner(System.in);do {System.out.println("请选择排序方法(1.冒泡排序 2.选择排序 3.插入排序 4.快速排序 5.希尔排序 6.归并排序 7.堆排序)");int choose=scan.nextInt();System.out.println("请选择:1.正序 2.倒序");int ord=scan.nextInt();System.out.println("请乱序输入一串数字(以逗号分隔,并以回车结束):");String num=scan.next();String[] nums= num.split(",");if (choose==1){int[] array1=new int[nums.length];for (int i=0;i<array1.length;i++){array1[i]= Integer.parseInt(nums[i]);}bubblingSort(array1,ord);if (ord==1){System.out.println("冒泡排序升序:"+ Arrays.toString(array1));}else if(ord==2){System.out.println("冒泡排序降序:"+Arrays.toString(array1));}}else if (choose==2){int[] array2=new int[nums.length];for (int i=0;i<array2.length;i++){array2[i]= Integer.parseInt(nums[i]);}selectionSort(array2,ord);if (ord==1){System.out.println("选择排序升序:"+Arrays.toString(array2));}else if(ord==2){System.out.println("选择排序降序:"+Arrays.toString(array2));}}else if (choose==3){int[] array3=new int[nums.length];for (int i=0;i<array3.length;i++){array3[i]= Integer.parseInt(nums[i]);}insertionSort(array3,ord);if (ord==1){System.out.println("插入排序升序:"+Arrays.toString(array3));}else if(ord==2){System.out.println("插入排序降序:"+Arrays.toString(array3));}}else if (choose==4){int[] array4=new int[nums.length];for (int i=0;i<array4.length;i++){array4[i]= Integer.parseInt(nums[i]);}quickSort(array4,0,array4.length-1,ord);if (ord==1){System.out.println("快速排序升序:"+Arrays.toString(array4));}else if(ord==2){System.out.println("快速排序降序:"+Arrays.toString(array4));}}else if (choose==5){int[] array5=new int[nums.length];for (int i=0;i<array5.length;i++){array5[i]= Integer.parseInt(nums[i]);}shellSort(array5,ord);if (ord==1){System.out.println("希尔排序升序:"+Arrays.toString(array5));}else if(ord==2){System.out.println("希尔排序降序:"+Arrays.toString(array5));}}else if (choose==6){int[] array6=new int[nums.length];for (int i=0;i<array6.length;i++){array6[i]= Integer.parseInt(nums[i]);}if (ord==1){//正序divide(true,array6,0,array6.length-1);System.out.println("归并排序升序:"+Arrays.toString(array6));}else if (ord==2){//倒序divide(false,array6,0,array6.length-1);System.out.println("归并排序降序:"+Arrays.toString(array6));}}else if (choose==7){int[] array7=new int[nums.length];for (int i=0;i<array7.length;i++){array7[i]= Integer.parseInt(nums[i]);}heapSort(array7,ord);if (ord==1){System.out.println("堆排序升序:"+Arrays.toString(array7));}else if(ord==2){System.out.println("堆排序降序:"+Arrays.toString(array7));}}}while (true);}
