Java实现的各种排序算法（包括冒泡，快排等）

<div class="cnblogs_Highlighter">
<pre class="brush:java;gutter:true;">//堆排序 不稳定
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,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(k2+1<=lastIndex){
//k节点的左子节点的索引
int biggerIndex=2k+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,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 &amp;&amp; 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,1,8};
System.out.println("排序之前：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
//归并排序
mergeSort(a,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,middle,right);
    }
}

private static void merge(int[] a,int middle,int right) {
    int[] tmpArr = new int[a.length];
    int mid = middle+1; //右边的起始位置
    int tmp = left;
    int third = left;
    while(left<=middle &amp;&amp; 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,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,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,a.length-1);
    }
}

private static void quickSort(int[] a,int low,int high) {
    if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
        int middle = getMiddle(a,low,high);
        quickSort(a,middle-1);
        quickSort(a,high);
    }
}

private static int getMiddle(int[] a,int high) {
    int temp = a[low];//基准元素
    while(low<high){
        //找到比基准元素小的元素位置
        while(low<high &amp;&amp; a[high]>=temp){
            high--;
        }
        a[low] = a[high]; 
        while(low<high &amp;&amp; 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,176,213,227,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,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]+" ");
    }
}

}
　　

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!