Comprehensive Summary of Sorting Algorithms with Java Implementations

0. Sorting Algorithm Overview

Sorting arranges a sequence of objects according to a key; the article defines key terms such as stability, internal/external sorting, time complexity and space complexity, and distinguishes between comparison‑based and non‑comparison‑based algorithms.

0.1 Definition

Sorting is the process of ordering a sequence of objects based on a specific key.

0.2 Terminology

Stable : equal elements retain their original relative order after sorting.

Unstable : equal elements may change order after sorting.

Internal sorting : all operations are performed in memory.

External sorting : data are too large for memory and require disk I/O.

Time complexity : the amount of time an algorithm consumes.

Space complexity : the amount of extra memory an algorithm requires.

0.3 Classification

Comparison sorts (e.g., quick sort, merge sort, heap sort, bubble sort) determine element order by pairwise comparisons, typically achieving O(n log n) average performance. Non‑comparison sorts (counting sort, radix sort, bucket sort) place elements based on value ranges, often achieving linear time O(n) under suitable conditions.

1. Bubble Sort

A simple algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order, causing larger elements to "bubble" to the end of the list.

1.1 Description

Compare adjacent elements; swap if the first is larger.

Repeat the pass for all pairs, moving the largest element to the end.

Perform the passes for all elements except the last sorted one.

Continue until a complete pass makes no swaps.

1.2 Animation

1.3 Java Implementation

/**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        if (array.length == 0)
            return array;
        for (int i = 0; i < array.length; i++)
            for (int j = 0; j < array.length - 1 - i; j++)
                if (array[j + 1] < array[j]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
        return array;
    }

1.4 Analysis

Best case: O(n) Worst case: O(n²) Average case: O(n²)

2. Selection Sort

A stable, in‑place algorithm that repeatedly selects the minimum (or maximum) element from the unsorted portion and swaps it with the first unsorted element.

2.1 Description

Initially the unsorted region is R[1..n]; the sorted region is empty.

For each pass i, find the smallest element R[k] in the unsorted region and swap it with R[i].

After n‑1 passes the array is sorted.

2.2 Animation

2.3 Java Implementation

/**
     * 选择排序
     * @param array
     * @return
     */
    public static int[] selectionSort(int[] array) {
        if (array.length == 0)
            return array;
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                if (array[j] < array[minIndex]) //找到最小的数
                    minIndex = j; //将最小数的索引保存
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }

2.4 Analysis

Best, worst, average: O(n²)

3. Insertion Sort

An in‑place algorithm that builds a sorted portion of the array one element at a time by shifting larger elements to make room for the new element.

3.1 Description

Assume the first element is sorted.

Take the next element and scan backward through the sorted part to find its correct position.

Shift larger elements one position to the right and insert the element.

Repeat until all elements are processed.

3.2 Animation

3.3 Java Implementation

/**
     * 插入排序
     * @param array
     * @return
     */
    public static int[] insertionSort(int[] array) {
        if (array.length == 0)
            return array;
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            current = array[i + 1];
            int preIndex = i;
            while (preIndex >= 0 && current < array[preIndex]) {
                array[preIndex + 1] = array[preIndex];
                preIndex--;
            }
            array[preIndex + 1] = current;
        }
        return array;
    }

3.4 Analysis

Best case: O(n) Worst case: O(n²) Average case: O(n²)

4. Shell Sort

An improved insertion sort that sorts elements at a specific gap, progressively reducing the gap until it becomes 1, thereby diminishing the overall number of movements.

4.1 Description

Using a gap sequence (e.g., n/2, n/4, …, 1), the array is divided into sub‑lists that are individually insertion‑sorted.

4.2 Animation

4.3 Java Implementation

/**
     * 希尔排序
     *
     * @param array
     * @return
     */
    public static int[] ShellSort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return array;
    }

4.4 Analysis

Best, worst, average: O(n log² n)

5. Merge Sort

A stable, divide‑and‑conquer algorithm that recursively splits the array into halves, sorts each half, and merges the sorted halves.

5.1 Description

Split the array into two sub‑arrays of size n/2.

Recursively sort each sub‑array.

Merge the two sorted sub‑arrays into a single sorted array.

5.2 Animation

5.3 Java Implementation

/**
     * 归并排序
     *
     * @param array
     * @return
     */
    public static int[] MergeSort(int[] array) {
        if (array.length < 2) return array;
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        return merge(MergeSort(left), MergeSort(right));
    }
    /**
     * 归并排序——将两段排序好的数组结合成一个排序数组
     *
     * @param left
     * @param right
     * @return
     */
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++) {
            if (i >= left.length)
                result[index] = right[j++];
            else if (j >= right.length)
                result[index] = left[i++];
            else if (left[i] > right[j])
                result[index] = right[j++];
            else
                result[index] = left[i++];
        }
        return result;
    }

5.4 Analysis

Best, worst, average: O(n log n)

6. Quick Sort

A fast, in‑place, divide‑and‑conquer algorithm that selects a pivot, partitions the array around the pivot, and recursively sorts the partitions.

6.1 Description

Choose a pivot element.

Reorder the array so that elements less than the pivot precede it and elements greater follow it.

Recursively apply the same process to the sub‑arrays on each side of the pivot.

6.2 Animation

6.3 Java Implementation

/**
     * 快速排序方法
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] QuickSort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start)
            QuickSort(array, start, smallIndex - 1);
        if (smallIndex < end)
            QuickSort(array, smallIndex + 1, end);
        return array;
    }
    /**
     * 快速排序算法——partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++)
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex)
                    swap(array, i, smallIndex);
            }
        return smallIndex;
    }
    /**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

6.4 Analysis

Best case: O(n log n) Worst case: O(n²) Average case: O(n log n)

7. Heap Sort

An in‑place algorithm that first builds a max‑heap from the array and then repeatedly extracts the maximum element to produce a sorted sequence.

7.1 Description

Build a max‑heap from the unsorted array.

Swap the heap root (largest) with the last element, shrink the heap size, and re‑heapify.

Repeat until the heap size is reduced to one.

7.2 Animation

7.3 Java Implementation

//声明全局变量，用于记录数组array的长度；
static int len;
/**
     * 堆排序算法
     *
     * @param array
     * @return
     */
    public static int[] HeapSort(int[] array) {
        len = array.length;
        if (len < 1) return array;
        //1.构建一个最大堆
        buildMaxHeap(array);
        //2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        while (len > 0) {
            swap(array, 0, len - 1);
            len--;
            adjustHeap(array, 0);
        }
        return array;
    }
/**
     * 建立最大堆
     *
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
        //从最后一个非叶子节点开始向上构造最大堆
        for (int i = (len - 1) / 2; i >= 0; i--) {
            adjustHeap(array, i);
        }
    }
/**
     * 调整使之成为最大堆
     *
     * @param array
     * @param i
     */
    public static void adjustHeap(int[] array, int i) {
        int maxIndex = i;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (i * 2 < len && array[i * 2] > array[maxIndex])
            maxIndex = i * 2;
        //如果有右子树，且右子树大于父节点，则将最大指针指向右子树
        if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex])
            maxIndex = i * 2 + 1;
        //如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
        if (maxIndex != i) {
            swap(array, maxIndex, i);
            adjustHeap(array, maxIndex);
        }
    }
/**
     * 交换数组内两个元素
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

7.4 Analysis

Best, worst, average: O(n log n)

8. Counting Sort

A linear‑time, stable algorithm for sorting integers within a known range by counting occurrences of each value.

8.1 Description

Find the minimum and maximum values.

Allocate a counting array (bucket) of size max‑min+1.

Count the occurrences of each value.

Accumulate counts to obtain positions.

Place each element into its final position by traversing the original array backwards.

8.2 Animation

8.3 Java Implementation

/**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] CountingSort(int[] array) {
        if (array.length == 0) return array;
        int bias, min = array[0], max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) max = array[i];
            if (array[i] < min) min = array[i];
        }
        bias = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else i++;
        }
        return array;
    }

8.4 Analysis

Best, worst, average: O(n + k) where k is the range of input values.

9. Bucket Sort

An extension of counting sort that distributes elements into a number of buckets, sorts each bucket (often recursively), and concatenates the results.

9.1 Description

Choose a bucket size (range of values per bucket).

Distribute each element into its appropriate bucket.

Sort each non‑empty bucket (using another algorithm or recursion).

Concatenate the buckets to obtain the final sorted array.

9.2 Animation

9.3 Java Implementation

/**
     * 桶排序
     *
     * @param array
     * @param bucketSize
     * @return
     */
    public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
        if (array == null || array.size() < 2)
            return array;
        int max = array.get(0), min = array.get(0);
        // 找到最大值最小值
        for (int i = 0; i < array.size(); i++) {
            if (array.get(i) > max) max = array.get(i);
            if (array.get(i) < min) min = array.get(i);
        }
        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < array.size(); i++) {
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        for (int i = 0; i < bucketCount; i++) {
            if (bucketCount == 1)
                bucketSize--;
            ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
            for (int j = 0; j < temp.size(); j++)
                resultArr.add(temp.get(j));
        }
        return resultArr;
    }

9.4 Analysis

Best case: O(n + k) Worst case: O(n + k) Average case: O(n²) (when bucket distribution is poor).

10. Radix Sort

A stable, non‑comparison sort that processes integer keys digit by digit, typically from least significant digit (LSD) to most significant digit.

10.1 Description

Find the maximum number to determine the number of digits.

For each digit position, distribute elements into 10 buckets (0‑9) based on that digit.

Collect the buckets back into the array and repeat for the next digit.

10.2 Animation

10.3 Java Implementation

/**
     * 基数排序
     * @param array
     * @return
     */
    public static int[] RadixSort(int[] array) {
        if (array == null || array.length < 2)
            return array;
        // 1.先算出最大数的位数；
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max, array[i]);
        }
        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }
        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < 10; i++)
            bucketList.add(new ArrayList<Integer>());
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    array[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
        }
        return array;
    }

10.4 Analysis

Best, worst, average: O(n · k) where k is the number of digits of the maximum value.

Original source: cnblogs.com/guoyaohua/p/8600214.html