九大经典排序算法归纳及JAVA 的实现

import java.util.*;
 
public class InsertionSort {
    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=i*10){
            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;
    }
}