冒泡排序 插入排序 选择排序 希尔排序 快速排序 归并排序 二分查找
package com.demo.test;
import java.util.Arrays;
import java.util.Scanner;
public class TestDemo{
public static void main(String[] args) {
//随机输入n个数,存放在数组a中
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int a[]=new int[n];
//这是第一种输入方法
/*for (int i=0;i<n;i++) {
a[i]=scanner.nextInt();
}*/
//这是第二种输入方法
int k=0;
while(true) {
if(k<n) {
a[k]=scanner.nextInt();
k++;
}else {
break;
}
}
int[] b=choicSort(a);
for (int j=0;j<b.length;j++) {
System.out.print(b[j]+" ");
}
}
//冒泡排序
private static int[] bubbleSort(int[] array) {
for (int i=1;i<array.length;i++) {
for (int j=0;j<array.length-i;j++) {
if (array[j]>array[j+1]) {
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
return array;
}
//插入排序
private static int[] insertSort(int[] array) {
for (int i=1;i<array.length;i++) {
int j=i;
int temp=array[i];
while (j>0&&array[j-1]>temp) {
array[j]=array[j-1];
j--;
}
array[j]=temp;
}
return array;
}
//选择排序
private static int[] choicSort(int[] array) {
for (int i=0;i<array.length-1;i++) {
int min=i;
for (int j=i+1;j<array.length;j++) {
if (array[j]<array[min]) {
min=j;
}
}
if (min!=i) {
int temp=array[i];
array[i]=array[min];
array[min]=temp;
}
}
return array;
}
//希尔排序
private static int[] shellSort(int[] array) {
int step=(array.length-1)/2;
while (step>0) {
for (int i=step;i<array.length;i++) {
int j=i;
int temp=array[i];
while(j>(step-1)&&array[j-step]>=temp) {
array[j]=array[j-step];
j=j-step;
}
array[j]=temp;
}
step=step/2;
}
return array;
}
//快速排序
private static void quickSort(int[] array) {
reQuickSort(array,0,array.length-1);
}
private static void reQuickSort(int[] array,int left,int right) {
if (left>=right) {
return ;
}else {
int partition=partitionIt(array,left,right);
reQuickSort(array,left,partition-1);
reQuickSort(array,partition+1,right);
}
}
private static int partitionIt(int[] array,int left,int right) {
int i=left;
int j=right+1;
int povit=array[left];
while (true) {
while (i<right&&array[++i]<povit) {}
while (j>0&&array[--j]>povit) {}
if (i<j) {
swap(array,i,j);
}else {
break;
}
}
swap(array,left,j);
return j;
}
private static void swap(int[] array,int i,int j) {
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
//归并排序
private static int[] sort(int[] a,int low,int high){
int mid = (low+high)/2;
if(low<high){
sort(a,low,mid);
sort(a,mid+1,high);
//左右归并
merge(a,low,mid,high);
}
return a;
}
private static void merge(int[] a, int low, int mid, int high) {
int[] temp = new int[high-low+1];
int i= low;
int j = mid+1;
int k=0;
// 把较小的数先移到新数组中
while(i<=mid && j<=high){
if(a[i]<a[j]){
temp[k++] = a[i++];
}else{
temp[k++] = a[j++];
}
}
// 把左边剩余的数移入数组
while(i<=mid){
temp[k++] = a[i++];
}
// 把右边边剩余的数移入数组
while(j<=high){
temp[k++] = a[j++];
}
// 把新数组中的数覆盖nums数组
for(int x=0;x<temp.length;x++){
a[x+low] = temp[x];
}
}
//二分查找
private static int binarySerach(int[] array,int left,int right,int value) {
int i=left;
int j=right;
int mid=(i+j)/2;
if (i>j) {
return -1;
}
if (array[mid]>value) {
return binarySerach(array,0,mid-1,value);
}else if(array[mid]<value){
return binarySerach(array,mid+1,right,value);
}else {
return mid;
}
}
}