Master Sorting Algorithms: From Bubble to Radix with Java Code

Introduction

Sorting and searching algorithms are fundamental knowledge that frequently appear in technical interviews; mastering their ideas and implementations is essential for a strong start.

Bubble Sort

The simplest sorting method swaps adjacent elements to bubble the smallest value to the front. Example with the sequence 5,3,8,6,4 shows how one pass moves the smallest element to the beginning. Time complexity is O(n^2).

Implementation:

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

Selection Sort

Selection sort also places the smallest element at the front each pass, but it selects the minimum from the whole unsorted portion instead of swapping adjacent elements, reducing the number of swaps. Time complexity is O(n^2).

Implementation:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}

Insertion Sort

Insertion sort builds a sorted portion by inserting each new element into its correct position, similar to sorting a hand of playing cards. Time complexity is O(n^2), but it performs well on nearly sorted data.

Implementation:

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

Quick Sort

Quick sort is a high‑performance divide‑and‑conquer algorithm. It selects a pivot, partitions the array so that elements smaller than the pivot move left and larger ones move right, then recursively sorts the sub‑arrays. Average time complexity O(n·log n), worst‑case O(n^2), and it is unstable.

Implementation (optimized version):

public class QuickSort {
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int i = left, j = right;
        int pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] <= pivot) i++;
            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
}

Heap Sort

Heap sort builds a binary heap (usually a max‑heap for ascending order) from the unsorted array, then repeatedly extracts the heap top and restores the heap property. Time complexity O(n·log n), space O(1), unstable.

Implementation:

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // Extract elements from heap
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    private static void heapify(int[] arr, int heapSize, int root) {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;
        if (left < heapSize && arr[left] > arr[largest])
            largest = left;
        if (right < heapSize && arr[right] > arr[largest])
            largest = right;
        if (largest != root) {
            int swap = arr[root];
            arr[root] = arr[largest];
            arr[largest] = swap;
            heapify(arr, heapSize, largest);
        }
    }
}

Shell Sort

Shell sort is an improved insertion sort that sorts elements separated by a gap, gradually reducing the gap to 1. It reduces the number of movements compared with plain insertion sort.

Implementation:

public class ShellSort {
    public static void shellInsert(int[] arr, int d) {
        for (int i = d; i < arr.length; i++) {
            int j = i - d;
            int temp = arr[i]; // record element to insert
            while (j >= 0 && arr[j] > temp) { // find position
                arr[j + d] = arr[j]; // shift right
                j -= d;
            }
            if (j != i - d) // if a smaller element exists
                arr[j + d] = temp;
        }
    }
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return ;
        int d = arr.length / 2;
        while (d >= 1) {
            shellInsert(arr, d);
            d /= 2;
        }
    }
}

Merge Sort

Merge sort uses the divide‑and‑conquer strategy: recursively split the array into halves, sort each half, and merge them. It guarantees O(n·log n) time and is stable, but requires O(n) auxiliary space.

Implementation:

public class MergeSort {
    public static void mergeSort(int[] arr) {
        mSort(arr, 0, arr.length - 1);
    }
    public static void mSort(int[] arr, int left, int right) {
        if (left >= right)
            return ;
        int mid = (left + right) / 2;
        mSort(arr, left, mid); // sort left half
        mSort(arr, mid + 1, right); // sort right half
        merge(arr, left, mid, right); // merge
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        // [left,mid] and [mid+1,right]
        int[] temp = new int[right - left + 1]; // temporary array
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }
}

Counting Sort

Counting sort achieves linear time O(n) when the input consists of integers within a known limited range. It counts occurrences of each value and then reconstructs the sorted array.

Implementation:

public class CountSort {
    public static void countSort(int[] arr) {
        if (arr == null || arr.length == 0)
            return ;
        int max = max(arr);
        int[] count = new int[max + 1];
        Arrays.fill(count, 0);
        for (int i = 0; i < arr.length; i++) {
            count[arr[i]] ++;
        }
        int k = 0;
        for (int i = 0; i <= max; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[k++] = i;
            }
        }
    }
    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ele : arr) {
            if (ele > max)
                max = ele;
        }
        return max;
    }
}

Bucket Sort

Bucket sort distributes elements into a number of buckets based on a mapping function, sorts each bucket (often with quick sort), and concatenates the buckets. It can achieve near‑linear time when the data are uniformly distributed.

Implementation:

public class BucketSort {
    public static void bucketSort(int[] arr) {
        if (arr == null && arr.length == 0)
            return ;
        int bucketNums = 10; // default for numbers in [0,100)
        List<List<Integer>> buckets = new ArrayList<List<Integer>>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<Integer>());
        }
        // distribute
        for (int i = 0; i < arr.length; i++) {
            buckets.get(f(arr[i])).add(arr[i]);
        }
        // sort each bucket
        for (int i = 0; i < buckets.size(); i++) {
            if (!buckets.get(i).isEmpty()) {
                Collections.sort(buckets.get(i)); // quick sort inside bucket
            }
        }
        // concatenate
        int k = 0;
        for (List<Integer> bucket : buckets) {
            for (int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }
    public static int f(int x) {
        return x / 10;
    }
}

Radix Sort

Radix sort sorts integers by processing individual digits from least significant to most significant, using a stable sub‑sorting method (often counting sort) at each digit position. Its time complexity is O(d·n), where d is the number of digits.

Implementation:

public class RadixSort {
    public static void radixSort(int[] arr) {
        if (arr == null && arr.length == 0)
            return ;
        int maxBit = getMaxBit(arr);
        for (int i = 1; i <= maxBit; i++) {
            List<List<Integer>> buf = distribute(arr, i); // distribute
            collecte(arr, buf); // collect
        }
    }
    public static List<List<Integer>> distribute(int[] arr, int iBit) {
        List<List<Integer>> buf = new ArrayList<List<Integer>>();
        for (int j = 0; j < 10; j++) {
            buf.add(new LinkedList<Integer>());
        }
        for (int i = 0; i < arr.length; i++) {
            buf.get(getNBit(arr[i], iBit)).add(arr[i]);
        }
        return buf;
    }
    public static void collecte(int[] arr, List<List<Integer>> buf) {
        int k = 0;
        for (List<Integer> bucket : buf) {
            for (int ele : bucket) {
                arr[k++] = ele;
            }
        }
    }
    public static int getMaxBit(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ele : arr) {
            int len = (ele + "").length();
            if (len > max)
                max = len;
        }
        return max;
    }
    public static int getNBit(int x, int n) {
        String sx = x + "";
        if (sx.length() < n)
            return 0;
        else
            return sx.charAt(sx.length() - n) - '0';
    }
}

Summary and Comparison

From an average‑case perspective, quick sort is usually the fastest, but its worst‑case performance can be worse than heap sort or merge sort. Merge sort offers stable sorting with O(n·log n) time at the cost of extra space. Simple sorts (bubble, insertion, selection) are useful for tiny or nearly sorted datasets and can be combined with more advanced algorithms. Linear‑time sorts (counting, bucket, radix) excel when the key range is limited or when the data size is huge; bucket sort is stable, while radix sort is also stable. Choosing the right algorithm depends on data size, key distribution, stability requirements, and memory constraints—there is no universally best sort, only the most suitable one for a given scenario.

Author: Pickle (source: cnblogs.com/wxisme/p/5243631.html)