DevOps 九大经典排序算法归纳及JAVA 的实现|Jooop's blog

aqing · November 10, 2019 · 8 hits

各排序算法实现原理和分类、对比

各排序算法实现原理和分类、对比

JAVA 实现

直接插入排序

import java.util.;
 
public class  {    public int[] insertionSort(int[] arr) {      if(arr==null||arr.length==0)            return null;        int k;        int temp;        for(int i=1;i<arr.length;i++){            k = i-1;            temp = arr[i];            while(k>=0&&temp<arr[k]){                arr[k+1] = arr[k];                k--;            }            arr[k+1] = temp;        }        return arr;    }}

希尔排序

import java.util.; 
public class ShellSort {    public int[] shellSort(int[] arr) {        int gap;        for (gap = arr.length/2; gap>0; gap = gap/2){            for (int i=gap; i<arr.length; i++){                if(arr[i] < arr[i-gap]){                    int temp = arr[i];                    int key = i-gap;                    while ( key>=0 && temp<arr[key] ){                        arr[key+gap] = arr[key];                        key = key - gap;                    }                    arr[key+gap] = temp;                }            }        }        return arr;    }}

冒泡排序

import java.util.;
 
public class BubbleSort {    public int[] bubbleSort(int[] arr) {       if(arr==null||arr.length==0)           return null;        int temp = arr[0];        for(int i=0;i<arr.length;i++){            for(int j=i;j<arr.length;j++){                if(arr[i]>arr[j]){                    temp=arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }        return arr;    }}

快速排序

import java.util.; 
public class QuickSort {    public int[] quickSort(int[] arr) {        if(arr==null)            return null;        sort(arr,0,arr.length-1);        return arr;    }         public void sort(int []arr,int begin,int end){        if(begin<end){            int middle = getMiddle(arr,begin,end);            sort(arr,begin,middle-1);            sort(arr,middle+1,end);        }    }         public int getMiddle(int []arr,int begin,int end){        int middle = arr[begin];        while(begin<end){            while(arr[end]>=middle&&begin<end){                end--;            }            arr[begin] = arr[end];            while(arr[begin]<=middle&&begin<end){                begin++;            }            arr[end] = arr[begin];        }        arr[begin] = middle;        return begin;    }}

简单选择排序

import java.util.;
 
public class SelectionSort {    public int[] selectionSort(int[] arr) {        if(arr==null||arr.length==0)            return null;        int number = 0;        for(int i=0;i<arr.length;i++){            number = i;            for(int j=i;j<arr.length;j++){                if(arr[number]>arr[j]){                    number = j;                }            }            int temp = arr[number];            arr[number] = arr[i];            arr[i] = temp;        }        return arr;    }}

堆排序

import java.util.; 
public class HeapSort {    public int[] heapSort(int[] arr) {        if(arr==null || arr.length==0)            return arr;        buileHeap(arr);        int temp = 0;        for(int i=arr.length-1; i>0; i--){            temp = arr[i];            arr[i] = arr[0];            arr[0] = temp;            adjustHeap(arr,0,i);        }        return arr;    }              public void buileHeap(int []arr){        for(int i=arr.length/2-1; i>=0; i--){            adjustHeap(arr,i,arr.length);        }    }         public void adjustHeap(int []arr,int index,int length){        int max;        while(index*2+1 < length){            max = index*2+1;            if(index*2+2 < length){                if(arr[index*2+2] > arr[max])                    max = index*2+2;            }            if(arr[max] <= arr[index]){                break;            }else{                int temp = arr[max];                arr[max] = arr[index];                arr[index] = temp;                index = max;            }        }    }}

归并排序

import java.util.;
 
public class MergeSort {    public int[] mergeSort(int[] arr) {        if(arr==null||arr.length==0)            return arr;        sort(arr,0,arr.length-1);        return arr;    }         private void sort(int []arr,int left,int right){        if(left<right){            int middle = (left+right)/2;            sort(arr,left,middle);            sort(arr,middle+1,right);            merge(arr,left,middle,right);        }    }         private void merge(int []arr,int left,int middle,int right){        int [] tempArr = new int[right-left+1];        int l = left;        int m = middle+1;        int index = 0;        while(l<=middle&&m<=right){            if(arr[l]<arr[m]){                tempArr[index++]=arr[l++];            }else{                tempArr[index++]=arr[m++];            }        }        while(l<=middle){            tempArr[index++] = arr[l++];        }        while(m<=right){            tempArr[index++] = arr[m++];        }        for(int i=0;i<tempArr.length;i++){            arr[left+i] = tempArr[i];        }    }}

计数排序

import java.util.; 
public class CountingSort {    public int[] countingSort(int[] arr) {        if(arr==null || arr.length==0)            return arr;        int max = arr[0];        int min = arr[0];        for(int i=1; i<arr.length; i++){            max = Math.max(max, arr[i]);            min = Math.min(min, arr[i]);        }        int []bucket = new int[max-min+1];        for(int i=0; i<arr.length; i++){            bucket[arr[i]-min]++;        }        int index = 0;        for(int i=0; i<bucket.length; i++){            while(bucket[i]-->0){                arr[index++] = min+i;            }        }        return arr;    }}

基数排序

import java.util.;
 
public class RadixSort {    public int[] radixSort(int[] arr) {        if(arr==null || arr.length==0)            return arr;                 int [][]bucket =new int[10][arr.length];        int []len = new int[10];        int p = 0;        for(int i=1; i<1000; i=i10){            for(int j=0; j<arr.length; j++){                p = arr[j]/i%10;                bucket[p][len[p]++] = arr[j];            }             p = 0;            for(int j=0; j<bucket.length; j++){                for(int k=0; k<len[j]; k++){                    arr[p++] = bucket[j][k];                    bucket[j][k] = 0;                }                len[j] = 0;            }        }        return arr;    }}


No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.