Java实现的各种排序算法（包括冒泡，快排等）详解编程语言

//堆排序   不稳定 
import java.util.Arrays; 
 
public class HeapSort { 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64}; 
        int arrayLength=a.length;   
        //循环建堆   
        for(int i=0;i<arrayLength-1;i++){   
            //建堆   
            buildMaxHeap(a,arrayLength-1-i);   
            //交换堆顶和最后一个元素   
            swap(a,0,arrayLength-1-i);   
            System.out.println(Arrays.toString(a));   
        }   
    } 
    //对data数组从0到lastIndex建大顶堆 
    public static void buildMaxHeap(int[] data, int lastIndex){ 
         //从lastIndex处节点（最后一个节点）的父节点开始  
        for(int i=(lastIndex-1)/2;i>=0;i--){ 
            //k保存正在判断的节点  
            int k=i; 
            //如果当前k节点的子节点存在   
            while(k*2+1<=lastIndex){ 
                //k节点的左子节点的索引  
                int biggerIndex=2*k+1; 
                //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 
                if(biggerIndex<lastIndex){   
                    //若果右子节点的值较大   
                    if(data[biggerIndex]<data[biggerIndex+1]){   
                        //biggerIndex总是记录较大子节点的索引   
                        biggerIndex++;   
                    }   
                }   
                //如果k节点的值小于其较大的子节点的值   
                if(data[k]<data[biggerIndex]){   
                    //交换他们   
                    swap(data,k,biggerIndex);   
                    //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值   
                    k=biggerIndex;   
                }else{   
                    break;   
                }   
            } 
        } 
    } 
    //交换 
    private static void swap(int[] data, int i, int j) {   
        int tmp=data[i];   
        data[i]=data[j];   
        data[j]=tmp;   
    }  
} 
 
 
//插入排序算法  稳定 
public class InsertSort { 
 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; 
        System.out.println("排序之前："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
        //直接插入排序 
        for (int i = 1; i < a.length; i++) { 
            //待插入元素 
            int temp = a[i]; 
            int j; 
            /*for (j = i-1; j>=0 && a[j]>temp; j--) { 
                //将大于temp的往后移动一位 
                a[j+1] = a[j]; 
            }*/ 
            for (j = i-1; j>=0; j--) { 
                //将大于temp的往后移动一位 
                if(a[j]>temp){ 
                    a[j+1] = a[j]; 
                }else{ 
                    break; 
                } 
            } 
            a[j+1] = temp; 
        } 
        System.out.println(); 
        System.out.println("排序之后："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
    } 
 
} 
 
 
 
 
// 归并排序  稳定 
public class MergSort { 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; 
        System.out.println("排序之前："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
        //归并排序 
        mergeSort(a,0,a.length-1); 
        System.out.println(); 
        System.out.println("排序之后："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
    } 
 
    private static void mergeSort(int[] a, int left, int right) { 
        if(left<right){ 
            int middle = (left+right)/2; 
            //对左边进行递归 
            mergeSort(a, left, middle); 
            //对右边进行递归 
            mergeSort(a, middle+1, right); 
            //合并 
            merge(a,left,middle,right); 
        } 
    } 
 
    private static void merge(int[] a, int left, int middle, int right) { 
        int[] tmpArr = new int[a.length]; 
        int mid = middle+1; //右边的起始位置 
        int tmp = left; 
        int third = left; 
        while(left<=middle && mid<=right){ 
            //从两个数组中选取较小的数放入中间数组 
            if(a[left]<=a[mid]){ 
                tmpArr[third++] = a[left++]; 
            }else{ 
                tmpArr[third++] = a[mid++]; 
            } 
        } 
        //将剩余的部分放入中间数组 
        while(left<=middle){ 
            tmpArr[third++] = a[left++]; 
        } 
        while(mid<=right){ 
            tmpArr[third++] = a[mid++]; 
        } 
        //将中间数组复制回原数组 
        while(tmp<=right){ 
            a[tmp] = tmpArr[tmp++]; 
        } 
    } 
} 
 
 
 
 
//冒泡排序   稳定 
public class mp { 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; 
        System.out.println("排序之前："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
        //冒泡排序 
        for (int i = 0; i < a.length; i++) { 
            for(int j = 0; j<a.length-i-1; j++){ 
                //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了 
                if(a[j]>a[j+1]){ 
                    int temp = a[j]; 
                    a[j] = a[j+1]; 
                    a[j+1] = temp; 
                } 
            } 
        } 
        System.out.println(); 
        System.out.println("排序之后："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
    } 
} 
 
 
 
 
//快排    不稳定 
public class QuickSort { 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; 
        System.out.println("排序之前："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
        //快速排序 
        quick(a); 
        System.out.println(); 
        System.out.println("排序之后："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
    } 
 
    private static void quick(int[] a) { 
        if(a.length>0){ 
            quickSort(a,0,a.length-1); 
        } 
    } 
 
    private static void quickSort(int[] a, int low, int high) { 
        if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常 
            int middle = getMiddle(a,low,high); 
            quickSort(a, 0, middle-1); 
            quickSort(a, middle+1, high); 
        } 
    } 
 
    private static int getMiddle(int[] a, int low, int high) { 
        int temp = a[low];//基准元素 
        while(low<high){ 
            //找到比基准元素小的元素位置 
            while(low<high && a[high]>=temp){ 
                high--; 
            } 
            a[low] = a[high];  
            while(low<high && a[low]<=temp){ 
                low++; 
            } 
            a[high] = a[low]; 
        } 
        a[low] = temp; 
        return low; 
    } 
} 
 
 
 
 
 
//基数排序    稳定 
import java.util.ArrayList; 
import java.util.List; 
 
public class RaSort { 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; 
        System.out.println("排序之前："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
        //基数排序 
        sort(a); 
        System.out.println(); 
        System.out.println("排序之后："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
    } 
 
    @SuppressWarnings({ "rawtypes", "unchecked" }) 
	private static void sort(int[] array) { 
        //找到最大数，确定要排序几趟 
        int max = 0; 
        for (int i = 0; i < array.length; i++) { 
            if(max<array[i]){ 
                max = array[i]; 
            } 
        } 
        //判断位数 
        int times = 0; 
        while(max>0){ 
            max = max/10; 
            times++; 
        } 
        //建立十个队列 
        List<ArrayList> queue = new ArrayList<ArrayList>(); 
        for (int i = 0; i < 10; i++) { 
            ArrayList queue1 = new ArrayList(); 
            queue.add(queue1); 
        } 
        //进行times次分配和收集 
        for (int i = 0; i < times; i++) { 
            //分配 
            for (int j = 0; j < array.length; j++) { 
                int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i); 
                ArrayList queue2 = queue.get(x); 
                queue2.add(array[j]); 
                queue.set(x,queue2); 
            } 
            //收集 
            int count = 0; 
            for (int j = 0; j < 10; j++) { 
                while(queue.get(j).size()>0){ 
                    ArrayList<Integer> queue3 = queue.get(j); 
                    array[count] = queue3.get(0); 
                    queue3.remove(0); 
                    count++; 
                } 
            } 
        } 
    } 
} 
 
 
 
 
 
//选择排序   不稳定 
public class SelectSort { 
 
    public static void main(String[] args) { 
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; 
        System.out.println("排序之前："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
        //简单的选择排序 
        for (int i = 0; i < a.length; i++) { 
            int min = a[i]; 
            int n=i; //最小数的索引 
            for(int j=i+1;j<a.length;j++){ 
                if(a[j]<min){  //找出最小的数 
                    min = a[j]; 
                    n = j; 
                } 
            } 
            a[n] = a[i]; 
            a[i] = min; 
             
        } 
        System.out.println(); 
        System.out.println("排序之后："); 
        for (int i = 0; i < a.length; i++) { 
            System.out.print(a[i]+" "); 
        } 
    } 
 
}