Sort

发自简书

public class Array {
    private int[] array;
    //数组有多少个数字
    private int nElement;

    public Array(int max) {
        this.array = new int[max];
        this.nElement = 0;
    }

    public void display(){
        for(int i=0;i<nElement;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    public void add(int value){
        array[nElement++]=value;
    }
    //交换
    private void swap(int index1,int index2){
        int temp=array[index1];
        array[index1]=array[index2];
        array[index2]=temp;
    }
    //冒泡排序
    public void bubbleSort(){
        int in,out;
        for(out=nElement-1;out>0;out--){
            for(in=0;in<out;in++){
                if(array[in]>array[in+1]){
                    swap(in,in+1);
                }
            }
        }
    }
    //插入排序
    public void insertSort(){
        int out,in;
        for(out=1;out<nElement;out++){
            int temp=array[out];
            in=out;
            while(in>0&&array[in-1]>=temp){
                array[in]=array[in-1];
                in--;
            }
            array[in]=temp;
        }
    }
    //选择排序
    public void selectSort(){
        int in,out;
        int min;
        for(out=0;out<nElement-1;out++){
            min=out;
            for(in=out+1;in<nElement;in++){
                if(array[in]<array[min]){
                    min=in;
                }
            }
            swap(min,out);
        }
    }
    //快速排序
    public void quickSort(){
        recQuickSort(0,nElement-1);
    }
    private void recQuickSort(int left,int right){
        if(left>=right){
            return;
        }
        int leftPtr=left-1;
        int rightPtr=right;
        while(true){
            while(array[++leftPtr]<array[right]);
            while(array[--rightPtr]>array[right]);
            if(leftPtr>rightPtr){
                swap(leftPtr,right);
                break;
            }
            swap(leftPtr,rightPtr);
        }
        recQuickSort(left,leftPtr-1);
        recQuickSort(leftPtr+1,right);
    }
    public static void main(String[] args) {
        Array a=new Array(10);
        for(int i=0;i<10;i++){
            a.add((int) (Math.random()*100));
        }
        a.display();
        a.quickSort();
        a.display();
    }
}

堆排序

import java.io.*;
class Node{
    private int iData;
    public Node(int key){
        iData=key;
    }
    public int getKey(){
        return iData;
    }
}
class Heap {
    private Node[] heapArray;
    private int maxSize;
    private int currentSize;
    public Heap(int mx){
        maxSize=mx;
        currentSize=0;
        heapArray=new Node[maxSize];
    }
    public Node remove(){
        Node root=heapArray[0];
        heapArray[0]=heapArray[--currentSize];
        trickleDown(0);
        return root;
    }
    public void trickleDown(int index){
        int largerChild;
        Node top=heapArray[index];
        while(index<currentSize/2){
            int leftChild=2*index+1;
            int rightChild=leftChild+1;
            if(rightChild<currentSize&&heapArray[leftChild].getKey()<heapArray[rightChild].getKey())
                largerChild=rightChild;
            else
                largerChild=leftChild;
            if(top.getKey()>=heapArray[largerChild].getKey())
                break;
            heapArray[index]=heapArray[largerChild];
            index=largerChild;
        }
        heapArray[index]=top;
    }
    public void displayHeap(){
        int nBlanks=32;
        int itemsPerRow = 1;
        int column=0;
        int j=0;
        String dots="...........................";
        System.out.println(dots+dots);
        while(currentSize>0){
            if(column==0){
                for(int k=0;k<nBlanks;k++)
                    System.out.print("  ");
            }
            System.out.print(heapArray[j].getKey());
            if(++j==currentSize)
                break;
            if(++column==itemsPerRow){
                nBlanks/=2;
                itemsPerRow*=2;
                column=0;
                System.out.println();
            }
            else
                for(int k=0;k<nBlanks*2-2;k++)
                    System.out.print("  ");
        }
        System.out.println("\n"+dots+dots);

    }
    public void displayArray(){
        for(int j=0;j<maxSize;j++){
            System.out.print(heapArray[j].getKey()+"  ");
        }
        System.out.println("");
    }
    public void insertAt(int index,Node newNode){
        heapArray[index]=newNode;
    }
    public void incrementSize(){
        currentSize++;
    }
}
class HeapSortApp{
    public static String getString() throws IOException {
        InputStreamReader isr=new InputStreamReader(System.in);
        BufferedReader br=new BufferedReader(isr);
        String s=br.readLine();
        return s;
    }
    public static int getInt() throws IOException {
        String s=getString();
        return Integer.parseInt(s);
    }
    public static void main(String[] args) throws IOException {
        int size,j;
        System.out.println("Enter number of items:  ");
        size=getInt();
        Heap theHeap=new Heap(size);
        for(j=0;j<size;j++){
            int random=(int)(Math.random()*100);
            Node newNode=new Node(random);
            theHeap.insertAt(j,newNode);
            theHeap.incrementSize();
        }
        System.out.print("Random: ");
        theHeap.displayArray();
        for(j=size/2-1;j>=0;j--){
            theHeap.trickleDown(j);
        }
        System.out.print("Heap: ");
        theHeap.displayArray();
        theHeap.displayHeap();
        for(j=size-1;j>=0;j--){
            Node biggestNode=theHeap.remove();
            theHeap.insertAt(j,biggestNode);
        }
        System.out.println("Sorted: ");
        theHeap.displayArray();
    }
}