循环选择的时候可以用二分，效率高
选择排序：
/*O(n方)选择排序*/
public class Main {
public static int [] sort;
public static void swap(int x,int y)
{
int temp;
temp=sort[x];
sort[x]=sort[y];
sort[y]=temp;
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int times=scan.nextInt();
while(times--!=0)
{
int number=scan.nextInt();
System.out.println("please input "+number+" int data:");
sort=new int[number];
for(int i=0;i<number;i++)
{
sort[i]=scan.nextInt();
}
for(int i=number-1;i>=1;i--)
{
int temp=-1,x=0;
for(int j=0;j<=i;j++)
{
if(sort[j]>temp)
{
temp=sort[j];
x=j;
}
}
swap(x,i);
}
System.out.println("output sort array:");
for(int i=0;i<number;i++)
{
System.out.print(sort[i]+" ");
}
System.out.println();
}
}
}
插入排序：
/*O(n方)插入排序*/
public class Main
{
public static int [] sort;
public static void swap(int x,int y)
{
int temp;
temp=sort[x];
sort[x]=sort[y];
sort[y]=temp;
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int times=scan.nextInt();
while(times--!=0)
{
int number=scan.nextInt();
System.out.println("please input "+number+" int data:");
sort=new int[number];
for(int i=0;i<number;i++)
{
sort[i]=scan.nextInt();
}
for(int i=1;i<number;i++)
{
for(int j=i-1;j>=0;j--)
{
if(sort[i]<sort[j])
{
swap(i,j);
i=j;
}
else break;
}
}
System.out.println("output sort array:");
for(int i=0;i<number;i++)
{
System.out.print(sort[i]+" ");
}
System.out.println();
}
}
}
归并排序：
/*O(nlogn)归并排序*/
public class Main
{
public static int [] asort ;
public static int [] bsave;
public static long sum=0;
public static void merge(int []a,int begin,int end,int []b)
{
if(begin==end)return;
int mid=(begin+end)/2;
merge(a, begin, mid, b);
merge(a, mid+1, end, b);
int i=begin,j=mid+1,pos=begin;
while(i<=mid&&j<=end)
{
if(a[i]<=a[j])
{
b[pos++]=a[i++];
}
else {
b[pos++]=a[j++];
}
}
while(i<=mid)b[pos++]=a[i++];
while(j<=end)b[pos++]=a[j++];
for(int k=begin;k<=end;k++)
{
a[k]=b[k];
}
}
public static void main(String []args)
{
Scanner scan=new Scanner(System.in);
int times=scan.nextInt();
while(times--!=0)
{
int number=scan.nextInt();
System.out.println("please input "+number+" int data:");
asort=new int[number];
bsave=new int[number];
for(int i=0;i<number;i++)
{
asort[i]=scan.nextInt();
}
merge(asort,0,number-1,bsave);
System.out.println("output sort array:");
for(int i=0;i<number;i++)
{
System.out.print(asort[i]+" ");
}
System.out.println();
}
}
}
快速排序：
/*快速排序,平均和最好的时间复杂度是ologn，最坏的是o（n方）*/
class Qsort
{
public int number,low,height;
public int [] qsort;
Scanner scanner=null;
public Qsort(int number,Scanner scanner) {
this.number = number;
this.scanner=scanner;
}
public void init()
{
low=0;
height=number-1;
System.out.println("please input "+number+" int data:");
qsort=new int[number];
for(int i=0;i<number;i++)
{
qsort[i]=scanner.nextInt();
}
qsortnumber(qsort, low, height);
}
public void qsortnumber(int []qsort,int low,int height)
{
if(low<height){
int middle=getMiddleNumber(qsort, low, height);
//System.out.println(middle);
qsortnumber(qsort, low, middle-1);
qsortnumber(qsort, middle+1, height);
}
}
public int getMiddleNumber(int [] qsort,int low,int height)
{
int temp=qsort[low];
while(low<height)
{
while(low<height&&qsort[height]>temp)
{
height--;
}
qsort[low]=qsort[height];
while(low<height&&qsort[low]<=temp)//应该有等于号，不然会死循环
{
low++;
}
qsort[height]=qsort[low];
}
qsort[low]=temp;
return low;
}
public void result()
{
init();
System.out.println("output sort array:");
for(int i=0;i<number;i++)
{
System.out.print(qsort[i]+" ");
}
System.out.println();
}
}
public class Main
{
public static void main(String [] args)
{
Scanner scan=new Scanner(System.in);
int times=scan.nextInt();
while(times--!=0)
{
Qsort qsort=new Qsort(scan.nextInt(),scan);
qsort.result();
}
}
}
堆排序：
/*堆排序，效率最坏是ologn,结合了快速排序节省空间和归并排序时间快的优点，可以用堆实现优先队列*/
class Node
{
public Node(int key) {
this.key = key;
}
public int key;
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
class Heap
{
private int maxSize;
private int currentSize=0;
private Node [] heapNodes;
public Heap(int maxSize) {
this.maxSize = maxSize;
heapNodes=new Node[maxSize];
}
public boolean insertHeapNodes(int index)
{
if(currentSize==maxSize)
{
System.out.println("堆已满，不能插入");
return false;
}
Node node=new Node(index);
heapNodes[currentSize]=node;
convertUp(currentSize++);
return true;
}
//在插入数据时，会产生不是堆的情况，需要自底向上比较。
public void convertUp(int index)
{
Node node=heapNodes[index];
int parent=(index-1)/2;
while(index>0&&node.getKey()>heapNodes[parent].getKey())
{
heapNodes[index]=heapNodes[parent];//找到该插入的位置，如果小于父节点就插入，否则一直向上寻找
index=parent;
parent=(parent-1)/2;
}
heapNodes[index]=node;
}
public Node removeHeapNodes()
{
Node root=heapNodes[0];
heapNodes[0]=heapNodes[--currentSize];
convertDown(0);
return root;
}
//删除数据时，也是一样，但是是自上向下比较
public void convertDown(int index)
{
Node top=heapNodes[index];
int largeTop;
while(index<currentSize/2)
{
int leftChild=2*index+1;
int rightChild=2*index+2;
if(heapNodes[leftChild].getKey()<heapNodes[rightChild].getKey()&&rightChild<currentSize)
{
largeTop=rightChild;
}
else {
largeTop=leftChild;
}
if(top.getKey()>=heapNodes[largeTop].getKey())//判断top是否大于largeTop
break;
heapNodes[index]=heapNodes[largeTop];
index=largeTop;
}
heapNodes[index]=top;
}
//利用每次删除的都是最大的那个节点，可以对堆排序
public void heapSort(){
while(currentSize>0){
System.out.print(this.removeHeapNodes().getKey()+" ");
}
System.out.println();
}
}
public class Main
{
public static void main(String []args)
{
Scanner scanner=new Scanner(System.in);
int times=scanner.nextInt();
while(times--!=0)
{
Heap heap=new Heap(10);
int number=scanner.nextInt();
for(int i=0;i<number;i++)
{
heap.insertHeapNodes(scanner.nextInt());
}
heap.heapSort();
}
}
}