Eight Common Sorting Algorithms in Java with Full Code Implementations

1. Direct Insertion Sort

Frequently encountered when a new element must be inserted into an already sorted sequence. The algorithm builds a sorted subsequence by repeatedly inserting the next element into its correct position.

public void insertSort(int[] a){
    int length=a.length; // array length for speed
    int insertNum; // element to insert
    for(int i=1;i<length;i++){ // number of insertions
        insertNum=a[i];
        int j=i-1; // size of already sorted part
        while(j>=0 && a[j]>insertNum){ // shift larger elements right
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=insertNum; // place the element
    }
}

2. Shell Sort

Improves insertion sort for large data sets by sorting elements that are a certain gap apart, gradually reducing the gap until it becomes 1, at which point a simple insertion sort finishes the job.

public void sheelSort(int[] a){
    int d=a.length;
    while(d!=0){
        d=d/2;
        for(int x=0;x<d;x++){
            for(int i=x+d;i<a.length;i+=d){
                int j=i-d;
                int temp=a[i];
                for(;j>=0 && temp<a[j];j-=d){
                    a[j+d]=a[j];
                }
                a[j+d]=temp;
            }
        }
    }
}

3. Simple Selection Sort

Useful for extracting the smallest (or largest) elements from a sequence. It repeatedly selects the minimum element from the unsorted portion and swaps it with the first unsorted position.

public void selectSort(int[] a){
    int length=a.length;
    for(int i=0;i<length;i++){
        int key=a[i];
        int position=i;
        for(int j=i+1;j<length;j++){
            if(a[j]<key){
                key=a[j];
                position=j;
            }
        }
        a[position]=a[i]; // swap
        a[i]=key;
    }
}

4. Heap Sort

An optimized version of selection sort that first builds a max‑heap from the array, then repeatedly swaps the heap root with the last element and restores the heap property.

public void heapSort(int[] a){
    System.out.println("开始排序");
    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(java.util.Arrays.toString(a));
    }
}
private void swap(int[] data,int i,int j){
    int tmp=data[i];
    data[i]=data[j];
    data[j]=tmp;
}
private void buildMaxHeap(int[] data,int lastIndex){
    for(int i=(lastIndex-1)/2;i>=0;i--){
        int k=i;
        while(k*2+1<=lastIndex){
            int biggerIndex=2*k+1;
            if(biggerIndex<lastIndex && data[biggerIndex]<data[biggerIndex+1]){
                biggerIndex++;
            }
            if(data[k]<data[biggerIndex]){
                swap(data,k,biggerIndex);
                k=biggerIndex;
            }else{
                break;
            }
        }
    }
}

5. Bubble Sort

Generally not recommended for large data sets. It repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order, bubbling the largest element to the end each pass.

public void bubbleSort(int[] a){
    int length=a.length;
    int temp;
    for(int i=0;i<a.length;i++){
        for(int j=0;j<a.length-i-1;j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

6. Quick Sort

Chosen when the fastest sorting time is required. It selects a pivot, partitions the array into elements less than and greater than the pivot, and recursively sorts the partitions.

public static void quickSort(int[] numbers,int start,int end){
    if(start<end){
        int base=numbers[start];
        int i=start,j=end;
        do{
            while(numbers[i]<base && i<end) i++;
            while(numbers[j]>base && j>start) j--;
            if(i<=j){
                int temp=numbers[i];
                numbers[i]=numbers[j];
                numbers[j]=temp;
                i++; j--;
            }
        }while(i<=j);
        if(start<j) quickSort(numbers,start,j);
        if(end>i) quickSort(numbers,i,end);
    }
}

7. Merge Sort

Second only to quick sort in speed, suitable when memory is limited or when parallel processing is possible. It repeatedly merges adjacent sorted sub‑arrays into larger sorted sequences.

public static void mergeSort(int[] numbers,int left,int right){
    int t=1;
    int size=right-left+1;
    while(t<size){
        int s=t;
        t=2*s;
        int i=left;
        while(i+(t-1)<size){
            merge(numbers,i,i+(s-1),i+(t-1));
            i+=t;
        }
        if(i+(s-1)<right)
            merge(numbers,i,i+(s-1),right);
    }
}
private static void merge(int[] data,int p,int q,int r){
    int[] B=new int[data.length];
    int s=p, t=q+1, k=p;
    while(s<=q && t<=r){
        if(data[s]<=data[t]) B[k++]=data[s++];
        else B[k++]=data[t++];
    }
    if(s==q+1) B[k++]=data[t++];
    else B[k++]=data[s++];
    for(int i=p;i<=r;i++) data[i]=B[i];
}

8. Radix Sort

Best for sorting large numbers or very long integers. It processes the numbers digit by digit, from least significant to most significant, using bucket queues for each base‑10 digit.

public void sort(int[] array){
    int max=array[0];
    for(int i=1;i<array.length;i++) if(array[i]>max) max=array[i];
    int time=0;
    while(max>0){ max/=10; time++; }
    java.util.List<java.util.ArrayList<Integer>> queue=new java.util.ArrayList<>();
    for(int i=0;i<10;i++) queue.add(new java.util.ArrayList<>());
    for(int i=0;i<time;i++){
        for(int j=0;j<array.length;j++){
            int x=array[j] % (int)Math.pow(10,i+1) / (int)Math.pow(10,i);
            java.util.ArrayList<Integer> bucket=queue.get(x);
            bucket.add(array[j]);
            queue.set(x,bucket);
        }
        int count=0;
        for(int k=0;k<10;k++){
            while(queue.get(k).size()>0){
                java.util.ArrayList<Integer> bucket=queue.get(k);
                array[count++]=bucket.remove(0);
            }
        }
    }
}