Java教程

常见的排序算法,如快速排序,堆排序,插入排序

本文主要是介绍常见的排序算法,如快速排序,堆排序,插入排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
public class TestDemo1 {
    //插入排序
    public static void insertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j;
            for(j=i-1;j>=0;j--){
                if(arr[j]>temp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    //希尔排序
    public static void shellSort(int arr[]){
        int[] gap={3,2,1};
        for(int i=0;i<gap.length;i++){
            insertSort(arr,gap[i]);
        }
    }
    public static void insertSort(int[] arr,int gap){
        for(int i=gap;i<arr.length;i++){
            int temp=arr[i];
            int j;
            for(j=i-gap;j>=0;j=j-gap){
                if(temp<arr[j]){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=temp;
        }
    }
    //选择排序
    public static void selectSort(int[] arr){
        int minIndex;
        for(int i=0;i<arr.length;i++){
            minIndex=i;
            for(int j=i+1;j<arr.length;j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if(minIndex!=i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
    //堆排序
    //向下调整函数
    public static void shiftDown(int len,int[] arr){
        int parent;
        for(int i=(len-1-1)/2;i>=0;i--) {
            parent=i;
            int child = parent * 2 + 1;
            while (child < len) {
                if (child + 1 < len && arr[child] <arr[child+1]) {
                    child++;
                }
                if (arr[child] > arr[parent]) {
                    int temp = arr[child];
                    arr[child] = arr[parent];
                    arr[parent] = temp;
                    parent = child;
                    child = parent * 2 + 1;
                } else {
                    break;
                }
            }
        }
    }
    public static void heapSort(int[] arr){
        shiftDown(arr.length,arr);//调整为大根堆
        for(int i=arr.length-1;i>0;i--){//堆排序
            int temp=arr[i];
            arr[i]=arr[0];
            arr[0]=temp;
            shiftDown(i,arr);
        }
    }

    //冒泡排序
    public static void bubbleSort(int[] arr){
        boolean flag = false;
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                    flag=true;
                }
            }
            if(flag==false){
                break;
            }
        }
    }

    //快速排序
    public static int partition(int[] arr,int i,int j){
        int privot=arr[i];
        while(i<j){
            //
            while(i<j && arr[j]>=privot){
                j--;
            }
            arr[i]=arr[j];
            while(i<j && arr[i]<=privot){
                i++;
            }
            arr[j]=arr[i];
        }
        arr[i]=privot;
        return i;
    }
    public static void quickSort(int[] arr,int start,int end){
        if(start>end){
            return;
        }
        int partition=partition(arr,start,end);// 得到基准
        quickSort(arr,start,partition-1);//  向基准左递归
        quickSort(arr,partition+1,end);//    向基准右递归
    }
}

图解:

 

这篇关于常见的排序算法,如快速排序,堆排序,插入排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!