Implementation of Common Sorting Algorithms (Java Version)

Common sorting algorithms

1, Select Sort

Selective sorting is a simple and intuitive sorting algorithm

  • 1. First, find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence.
  • 2. Then continue to find the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.
  • 3. Repeat the second step until all elements are sorted.

Animated Demo

code implementation

/**
 * @author java Xiaohao
 * @date 2022/6/1
 */
public class Code003SelectionSort {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void selectSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        } 
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int minValueIndex = i;
            for (int j = i + 1; j < len; j++) {
                minValueIndex = nums[j] < nums[minValueIndex] ? j : minValueIndex;
            }
            swap(nums, i, minValueIndex);
        }
    }

    public static void bubbleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        for (int end = len - 1; end >=0; end--) {
            for (int second = 1; second <= end; second++){
                if (nums[second - 1] > nums[second]) {
                    swap(nums, second - 1, second);
                }
            }
        }
    }



    public static void main(String[] args) {
        int[] arr = {6, 5, 8, 9, 7, 3, 1, 2, 4};
        print(arr);
        selectSort(arr);
        print(arr);
        bubbleSort(arr);
        print(arr);
    }
}
  • nature:
    • 1. Time complexity: O(n2)
    • 2. Spatial complexity: O(1)
    • 3. Unstable sort
    • 4. Sort in place

2, Bubble sort

Bubble Sort is also a simple and intuitive sort algorithm.

  • 1. Compares adjacent elements. If the first one is bigger than the second one, exchange them.
  • 2. Do the same for each pair of adjacent elements, from the first pair to the last pair at the end. After this step is completed, the final number of elements will be the maximum.
  • 3. Repeat the above steps for all elements except the last one.
  • 4. Continue to repeat the above steps for fewer and fewer elements each time until there is no pair of numbers to compare.

Animated Demo

code implementation

/**
 * @author java Xiaohao
 * @date 2022/6/1
 */
public class Code004BubbleSort {

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void bubbleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        for (int end = len - 1; end >=0; end--) {
            for (int second = 1; second <= end; second++){
                if (nums[second - 1] > nums[second]) {
                    swap(nums, second - 1, second);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 8, 9, 7, 3, 1, 2, 4};
        print(arr);
        bubbleSort(arr);
        print(arr);
    }
}
  • nature:
    1. Time complexity: O(n2)
    2. Spatial complexity: O(1)
    3. Stable sort
    4. Sort in place

3, Insert Sort

When we sort an unordered array, we need to make room to insert elements, and move all other elements one bit to the right before inserting. This algorithm is called insertion sorting.

  • 1. The first element of the first to be sorted sequence is regarded as an ordered sequence, and the second element to the last element is regarded as an unsorted sequence.
  • 2. Scan the unordered sequence from beginning to end, and insert each element scanned into the appropriate position of the ordered sequence. (If the element to be inserted is equal to an element in an ordered sequence, insert the element to be inserted after the equal element.)
    Animated Demo

    code implementation
/**
 * @author java Xiaohao
 * @date 2022/6/1
 */
public class Code005InsertSort {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void print(int[] nums) {
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void insertSort1(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        for (int end = 1; end < len; end++) {
            int curNumIndex = end;
            while (curNumIndex - 1 >= 0 && nums[curNumIndex - 1] > nums[curNumIndex]) {
                swap(nums, curNumIndex - 1, curNumIndex);
                curNumIndex--;
            }
        }
    }

    /**
     * Optimized insertion sort
     * @param nums array
     */
    public static void insertSort2(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int len = nums.length;
        for (int end = 1; end < len; end++) {
            for (int pre = end - 1; pre >= 0 && nums[pre] > nums[end]; pre--) {
                swap(nums, pre, pre + 1);
            }

        }
    }

    public static void main(String[] args) {
        int[] arr = {6, 5, 8, 9, 7, 3, 1, 2, 4};
        print(arr);
        insertSort1(arr);
        print(arr);
        insertSort2(arr);
        print(arr);
    }
}

4, Quick sort

Quicksort uses a Divide and conquer strategy to divide a list into two sub lists.
Quicksort is also a typical application of divide and conquer in sorting algorithm. In essence, quick sort should be a recursive divide and conquer method based on bubble sort.

  1. Select an element from the sequence, which is called "pivot";
  2. Reorder the number sequence. All elements smaller than the reference value are placed in front of the reference, and all elements larger than the reference value are placed behind the reference (the same number can go to either side). After the partition is exited, the benchmark is in the middle of the series. This is called partition operation;
  3. Recursively sort the subsequences less than the reference value element and the subsequences greater than the reference value element;

Animated Demo

code implementation

public static int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            //Get the position of the axis element
            int mid = partition(arr, left, right);
            //Split
            arr = quickSort(arr, left, mid - 1);
            arr = quickSort(arr, mid + 1, right);
        }
        return arr;
    }

    private static int partition(int[] arr, int left, int right) {
        //Select axis element
        int pivot = arr[left];
        int i = left + 1;
        int j = right;
        while (true) {
            // Find the position of the first element greater than or equal to pivot to the right
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            // Find the position of the first element less than or equal to pivot to the left
            while(i <= j && arr[j] >= pivot ) {
                j--;
            }
            if(i >= j) {
                break;
            }
            //Swap the positions of the two elements so that the left element is not greater than pivot and the right element is not less than pivot
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        arr[left] = arr[j];
        // Keep the axis elements in an orderly position
        arr[j] = pivot;
        return j;
}

nature:

  1. Time complexity: O(nlogn)
  2. Spatial complexity: O (log n)
  3. Unstable sort
  4. in-place sort

5, Hill sort

Hill sort, also known as decreasing incremental sort algorithm, is a more efficient and improved version of insert sort. But Hill sort is an unstable sort algorithm.
First, the whole record sequence to be sorted is divided into several sub sequences for direct insertion sorting. Specific algorithm description:

  1. Select an incremental sequence t1, t2,..., tk, where ti>tj, tk=1;
  2. The sequence is sorted k times according to the number of incremental sequences k;
  3. For each sorting, the sequence to be sorted is divided into several subsequences with length m according to the corresponding increment ti, and each sub table is inserted and sorted directly. When the increment factor is only 1, the entire sequence is treated as a table, and the table length is the length of the entire sequence.

Animated Demo

code implementation

public class ShellSort {
    public static int[] shellSort(int arr[]) {
        if (arr == null || arr.length < 2) return arr;
        int n = arr.length;
        // Sort the groups with interval h of each group. At first, h=n/2;
        for (int h = n / 2; h > 0; h /= 2) {
            //Insert and sort each office section group
            for (int i = h; i < n; i++) {
                // Insert arr[i] in the correct position of the group
                insertI(arr, h, i);
            }
     }
     return arr;
    }

    /**
     * Insert arr[i] in the correct position of the group
     * arr[i]] The group is... arr[i-2*h],arr[i-h], arr[i+h]
     */
    private static void insertI(int[] arr, int h, int i) {
        int temp = arr[i];
        int k;
        for (k = i - h; k >= 0 && temp < arr[k]; k -= h) {
            arr[k + h] = arr[k];
        }
        arr[k + h] = temp;
    }
}

6, Merge sort

Merge sort is an effective sort algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer.

  1. The application space is the sum of two sorted sequences, which is used to store the merged sequences;
  2. Set two pointers. The initial position is the starting position of the two sorted sequences;
  3. Compare the elements pointed by the two pointers, select the relatively small elements and put them into the merge space, and move the pointer to the next position;
  4. Repeat step 3 until a pointer reaches the end of the sequence;
  5. Copy all the remaining elements of another sequence directly to the end of the merged sequence.

Animated Demo

code implementation

public class Code007MergeSort {
    // Merge sort
    public static int[] mergeSort(int[] arr, int left, int right) {
        // If left==right, it means that there is only one element in the array, so recursive sorting is not required
        if (left < right) {
            // Divide a large array into two arrays
            int mid = left + (right - left) / 2;
            // Sort the left half
            arr = mergeSort(arr, left, mid);
            // Sort the right half
            arr = mergeSort(arr, mid + 1, right);
            //Merge
            merge(arr, left, mid, right);
        }
        return arr;
    }

    // Merge function to merge two ordered arrays
    // arr[left..mif] represents an array, and arr [mid+1.. Right] represents an array
    private static void merge(int[] arr, int left, int mid, int right) {
        //First, use a temporary array to combine them
        int[] a = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                a[k++] = arr[i++];
            } else {
                a[k++] = arr[j++];
            }
        }
        while(i <= mid) a[k++] = arr[i++];
        while(j <= right) a[k++] = arr[j++];
        // Copy the temporary array to the original array
        for (i = 0; i < k; i++) {
            arr[left++] = a[i];
        }
    }
}

Non recursive:

public class Code008MergeSort {
    // Non recursive merging sort
    public static int[] mergeSort(int[] arr) {
        int n = arr.length;
        // The sizes of sub arrays are 1, 2, 4, 8
        // The initial merged array size is 1, followed by 2, followed by 4
        for (int i = 1; i < n; i += i) {
            //Divide the array
            int left = 0;
            int mid = left + i - 1;
            int right = mid + i;
            //Merge, and merge the arrays with array size i in pairs
            while (right < n) {
                // Merge functions are the same as recursive merge functions
                merge(arr, left, mid, right);
                left = right + 1;
                mid = left + i - 1;
                right = mid + i;
            }
            // There are still some missing arrays that haven't been merged. Don't forget
            // Because it is impossible for each word group to be exactly the size of i
            if (left < n && mid < n) {
                merge(arr, left, mid, n - 1);
            }
        }
        return arr;
    }
}

nature:

  • 1. Time complexity: O(nlogn)
  • 2. Spatial complexity: O(n)
  • 3. Stable sort
  • 4. Non in-situ sorting

Tags: Java Algorithm

Posted by Clukey on Sat, 24 Sep 2022 21:46:56 +0300