Common Sorting Algorithms: Concepts, Implementations, and Complexity Analysis

Bubble Sort

Key Points

Bubble sort is a swapping sort that repeatedly traverses the list, compares adjacent elements, and swaps them when they are out of order, causing smaller elements to "float" to the front of the sequence.

Algorithm Idea

The algorithm repeatedly walks through the array, comparing two neighboring elements each time; if they are in the wrong order they are exchanged. After each pass the next smallest element is placed at its correct position.

Core Code

public void bubbleSort(int[] list) {
    int temp = 0; // temporary variable for swapping
    for (int i = 0; i < list.length - 1; i++) {
        // compare from right to left, moving the i‑th smallest element to position i
        for (int j = list.length - 1; j > i; j--) {
            if (list[j - 1] > list[j]) {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }
        System.out.format("第 %d 趟：\t", i);
        printAll(list);
    }
}

Analysis

Best case (already sorted) runs in O(N) comparisons with zero swaps; worst and average cases are O(N²). The algorithm is stable because equal elements never change relative order.

Quick Sort

Key Points

Quick sort is also a swapping sort, originally proposed by C. A. R. Hoare in 1962.

Algorithm Idea

The list is partitioned around a pivot (the leftmost element by default). Elements smaller than the pivot are moved to its left, larger ones to its right, and the process recurses on the two sub‑lists.

Core Code

public int division(int[] list, int left, int right) {
    int base = list[left];
    while (left < right) {
        while (left < right && list[right] >= base) right--;
        list[left] = list[right];
        while (left < right && list[left] <= base) left++;
        list[right] = list[left];
    }
    list[left] = base;
    return left;
}

private void quickSort(int[] list, int left, int right) {
    if (left < right) {
        int base = division(list, left, right);
        System.out.format("base = %d:\t", list[base]);
        printPart(list, left, right);
        quickSort(list, left, base - 1);
        quickSort(list, base + 1, right);
    }
}

Analysis

Average time complexity is O(N log N); worst case (already sorted or reverse sorted) degrades to O(N²). Space complexity is O(log N) due to recursion. The algorithm is unstable because equal elements may be reordered during partitioning.

Insertion Sort

Key Points

Insertion sort builds a sorted sub‑array one element at a time, inserting each new element into its proper position.

Core Code

public void insertSort(int[] list) {
    System.out.format("i = %d:\t", 0);
    printPart(list, 0, 0);
    for (int i = 1; i < list.length; i++) {
        int j = 0;
        int temp = list[i]; // element to insert
        for (j = i - 1; j >= 0 && temp < list[j]; j--) {
            list[j + 1] = list[j];
        }
        list[j + 1] = temp;
        System.out.format("i = %d:\t", i);
        printPart(list, 0, i);
    }
}

Analysis

Best case (already sorted) runs in O(N); worst and average cases are O(N²). It uses O(1) extra space and is stable because equal keys retain their original order.

Shell Sort

Key Points

Shell sort is a generalized insertion sort that sorts elements spaced by a decreasing gap sequence.

Core Code

public void shellSort(int[] list) {
    int gap = list.length / 2;
    while (1 <= gap) {
        for (int i = gap; i < list.length; i++) {
            int j = 0;
            int temp = list[i];
            for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
                list[j + gap] = list[j];
            }
            list[j + gap] = temp;
        }
        System.out.format("gap = %d:\t", gap);
        printAll(list);
        gap = gap / 2;
    }
}

Analysis

Time complexity depends on the gap sequence; with the original N/2, N/4, … gaps it is between O(N¹·⁵) and O(N²). Space is O(1). The algorithm is unstable because elements may be moved across gaps.

Selection Sort

Key Points

Selection sort repeatedly selects the smallest remaining element and swaps it into its final position.

Core Code

public void selectionSort(int[] list) {
    for (int i = 0; i < list.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[minIndex]) {
                minIndex = j;
            }
        }
        int temp = list[i];
        list[i] = list[minIndex];
        list[minIndex] = temp;
        System.out.format("第 %d 趟: \t", i);
        printPart(list, 0, i);
    }
}

Analysis

Always performs N(N‑1)/2 comparisons, regardless of input order; swaps are at most N‑1. Time complexity is O(N²), space O(1). It is unstable because equal elements can be swapped.

Heap Sort

Key Points

Heap sort builds a binary heap (usually a max‑heap) and repeatedly extracts the maximum element to achieve a sorted array.

Core Code

public void HeapAdjust(int[] array, int parent, int length) {
    int temp = array[parent]; // store parent
    int child = 2 * parent + 1; // left child
    while (child < length) {
        if (child + 1 < length && array[child] < array[child + 1]) {
            child++; // use right child if larger
        }
        if (temp >= array[child]) break;
        array[parent] = array[child];
        parent = child;
        child = 2 * child + 1;
    }
    array[parent] = temp;
}

public void heapSort(int[] list) {
    // build initial heap
    for (int i = list.length / 2; i >= 0; i--) {
        HeapAdjust(list, i, list.length);
    }
    // extract elements one by one
    for (int i = list.length - 1; i > 0; i--) {
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;
        HeapAdjust(list, 0, i);
        System.out.format("第 %d 趟: \t", list.length - i);
        printPart(list, 0, list.length - 1);
    }
}

Analysis

Both building the heap and each extraction take O(N log N) time; overall time complexity is O(N log N). Space complexity is O(1). The algorithm is unstable because the heap operations may reorder equal keys.

Merge Sort

Key Points

Merge sort is a classic divide‑and‑conquer algorithm that recursively splits the array and merges sorted sub‑arrays.

Core Code

public void Merge(int[] array, int low, int mid, int high) {
    int i = low;          // index for first half
    int j = mid + 1;      // index for second half
    int k = 0;            // index for temporary array
    int[] array2 = new int[high - low + 1];
    while (i <= mid && j <= high) {
        if (array[i] <= array[j]) {
            array2[k++] = array[i++];
        } else {
            array2[k++] = array[j++];
        }
    }
    while (i <= mid) array2[k++] = array[i++];
    while (j <= high) array2[k++] = array[j++];
    for (k = 0, i = low; i <= high; i++, k++) {
        array[i] = array2[k];
    }
}

public void MergePass(int[] array, int gap, int length) {
    int i = 0;
    for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
        Merge(array, i, i + gap - 1, i + 2 * gap - 1);
    }
    if (i + gap - 1 < length) {
        Merge(array, i, i + gap - 1, length - 1);
    }
}

public int[] sort(int[] list) {
    for (int gap = 1; gap < list.length; gap = 2 * gap) {
        MergePass(list, gap, list.length);
        System.out.print("gap = " + gap + ":\t");
        this.printAll(list);
    }
    return list;
}

Analysis

Time complexity is O(N log N) and requires O(N) auxiliary space for the temporary array. Merge sort is stable because equal elements retain their original order.

Radix Sort

Key Points

Radix sort sorts integers by processing individual digits from least‑significant to most‑significant using bucket (counting) sort, without comparing keys directly.

Core Idea

For each digit position, numbers are placed into ten buckets (0‑9) according to that digit, then collected in order; the process repeats for the next more significant digit.

Analysis

With d digit positions and radix r = 10, time complexity is O(d·(n + r)). Space complexity is O(n + r). The algorithm is stable because the relative order of equal keys is preserved during each digit pass.

Conclusion

The article concludes the series on sorting algorithms, summarizing each method’s strengths, weaknesses, stability, and typical use‑cases, and provides Java reference implementations and sample test data.