Ten classical sorting algorithm ideas and Java code implementation

Sorting algorithm stability:

The algorithm is stable when two identical values are not swapped.
Otherwise, the algorithm is unstable.

Simple sorting

Bubble sort

Bubble sorting algorithm is a stable sorting algorithm.

Bubble sort ideas

Basic idea: bubble sort, similar to bubbling in water, the larger number sink, the smaller number slowly rise, assuming from small to large, that is, the larger number slowly move to the back row, the smaller number slowly forward row

Intuitive: On each iteration, move the largest number to the end of the sequence.

Algorithm description

First sorting: compare the first and second elements, and swap if the first is larger than the next. And then compare number two to number three. All the way to the second from the bottom and the last one. At this point, after the first run, the largest element is at the end of the sequence.
Second sorting: compare the first and second elements to the third to last and the second to last.
Keep repeating until you get to n minus 1.

The following is a GIF:

Code implementation

package com.xgc.sort.simplesort.bubblesort;

/** * bubble sort *@author xgc
 *
 */
public class BubbleSort {
	
	public static void sort(int[] arr) {
		if (arr==null || arr.length<2) {
			return;
		}
		for(int i=0; i<arr.length-1; i++) {
			for(int j=0; j<arr.length-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
}
Copy the code

test

package com.xgc.sort.simplesort.bubblesort;

public class BubbleSortTest {
	
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		BubbleSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(N2)

Space complexity: O(1)

Stability: stability

Insertion sort

Insertion sort idea

The basic idea is to insert a record into an already ordered table to form a new ordered table with +1 elements.

The following figure shows the sorting process of the insertion sort algorithm:

Code implementation

package com.xgc.sort.simplesort.insertionsort;

/** * insert sort *@author21952 * * /
public class InsertionSort {

	public static void sort(int[] arr) {
		for(int i=1; i<arr.length; i++) {
			// Get the element currently pointed to
			int temp = arr[i];
			// Records the index currently pointed to in the inner loop
			int j;
			// Determine if the current element is less than the previous element, if so, start comparing and inserting the current element
			// Compare from back to front
			for(j=i; j>0 && arr[j-1]>temp; j--) {
				// Move the element back
				arr[j] = arr[j-1];
			}
			// After the inner loop,j points to where the temp element is to be insertedarr[j] = temp; }}}Copy the code

test

package com.xgc.sort.simplesort.insertionsort;

public class InsertionSortTest {
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		InsertionSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(N2)

Space complexity: O(1)

Stability: stability

Selection sort

Selection sorting idea

First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence. Then find the smallest (large) element from the remaining unsorted sequence and place it at the end of the sorted sequence. Repeat until the unsorted elements are zero.

Code implementation

package com.xgc.sort.simplesort.selectionsort;

/** * select sort *@author xgc
 *
 */
public class SelectionSort {
	
	public static void sort(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			// Record the minimum subscript
			int min=i;
			for(int j=i+1; j<arr.length; j++) {
				if(arr[j] < arr[min]) { min = j; }}inttemp = arr[i]; arr[i] = arr[min]; arr[min] = temp; }}}Copy the code

test

package com.xgc.sort.simplesort.selectionsort;

public class SelectionSortTest {
	
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		SelectionSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(N2)

Space complexity: O(1)

Stability: unstable

Shell’s Sort

Hill sort is a kind of insertion sort, also called reduced increment sort, is a more efficient and improved version of the insertion sort algorithm.

Hill sort is an unstable algorithm.

Hill sort proposed an improved method based on the following two characteristics of direct insertion sort:

Insertion sort in almost ordered data operations, high efficiency, can achieve the efficiency of linear sort.
Insert sort is generally inefficient because it can only move data one bit at a time.

Hill sorting algorithm idea

Take d1, an integer less than n, as the first increment and group all the data. Put all the data with distance d1 in the same group. Direct insertion sort is first done within the group. Then take the second increment d2<d1 and repeat the grouping and sorting until the increment dt=1, i.e. all the data is placed in the same group for insertion sort.

The algorithm can improve efficiency for the following reasons:

A single swap of distant elements can span multiple elements, that is, a single swap can eliminate multiple inversions.

Code implementation

package com.xgc.sort.advancedsorting.shellsort;

/** * hill sort *@author xgc
 *
 */
public class ShellSort {
	
	public static void sort(int[] arr) {
		// Calculate the incremental step, which we also call the step size
		// Increments start at half the length, and keep dividing by 2 until step==1
		for(int step= arr.length/2; step>0; step/=2) {
			for(int i = step; i<arr.length; i++) {
				// Record the values to be compared
				int temp = arr[i];
				// Record the subscript to which the inner loop is currently pointing
				int j;
				for(j=i-step; j>=0&& arr[j]>temp; j-=step) { arr[j+step] = arr[j]; } arr[j+step] = temp; }}}}Copy the code

test

package com.xgc.sort.advancedsorting.shellsort;

public class ShellSortTest {
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		ShellSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

The execution result

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: This is not determined, depending on the choice of delta sequence will be different time complexity. The code implementation above uses a sequence of Hill increments.

Space complexity: O(1)

Stability: unstable

Heap Sort

Heap sort is a sort algorithm designed by using heap data structure.

The heap is a nearly complete binary tree structure.

Maximum heap: the value of each node greater than or equal to the value of its children, used in the heap sort algorithm for ascending sort
Minimum heap: The value of each node is less than or equal to the value of its children, used for descending sort in the heap sort algorithm

Heapsort idea

Constructs the maximum heap of a given unordered sequence, with the largest element at the head of the heap.
Swap the top and bottom of the heap, sinking the largest element to the end of the array
Reduce the size of the heap by 1 and then adjust it to the maximum heap.
Repeat until the heap size is 1

Heap sort: heap sort: heap sort: heap sort: heap sort

Diagram of heap sorting process

Code implementation

package com.xgc.sort.advancedsorting.heapsort;

/** * Heap sort (maximum heap, ascending sort) *@author xgc
 *
 */
public class HeapSort {
	
	public static void sort(int[] arr) {
		
		// To record the heap length
		int len = arr.length;
		
		// Build the maximum heap
		// Adjust from right to left, from bottom to top, starting from the last non-leaf
		for(int i=arr.length/2-1; i>=0; i--) {
			heapify(arr, i, len);
		}
		
		// Swap the head and tail of the heap, and reduce the heap length by one, adjust the remaining heap to the maximum heap
		for(int i = arr.length-1; i>0; i--) {
			swap(arr, 0, i);
			heapify(arr, 0, i); }}/** * adjusts to the maximum heap (only based on the maximum heap already established) *@paramArr The array to adjust *@paramI is guaranteed to be in the largest heap *@paramLen The length of the heap to adjust */
	private static void heapify(int[] arr, int i, int len) {
		// The index of the maximum value
		int largest = i;
		// the index of the left child of the I node
		int left = 2*i+1;
		// The subscript of the right child of the I node
		int right = 2*i+2;
		
		if (left<len && arr[left]>arr[largest]) {
			largest = left;
		}
		
		if (right<len && arr[right]>arr[largest]) {
			largest = right;
		}
		
		if (largest != i) {
			swap(arr, i, largest);
			heapify(arr, largest, len);
		}
	}
	
	/** * swap I with Max *@param arr
	 * @param i
	 * @param largest
	 */
	private static void swap(int[] arr, int i, int largest) {
		inttemp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; }}Copy the code

test

package com.xgc.sort.advancedsorting.heapsort;

public class HeapSortTest {
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		HeapSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

The result is as follows:

-3, -1.4.4.5.7.9.10.16.Copy the code

The complexity of the

Time complexity: O(nlogn)

Space complexity: O(1)

Stability: unstable

Merge Sort

Merge sort is an efficient sorting algorithm based on merge operation.

This algorithm is a typical application of Divide and Conquer.

The idea of merge sort

Apply for a space that is the sum of two sorted sequences and is used to store the combined sequence
Sets two Pointers to the start of two sorted sequences
Compare the elements to which the two Pointers point, select the smaller element in the merge space, and move the pointer to the next position
Repeat step 3 until one of the Pointers exceeds the end of the sequence, and assign all remaining elements of the other sequence directly to the end of the merged sequence

The illustration is as follows:

Code implementation

package com.xgc.sort.advancedsorting.mergesort;

public class MergeSort {
	
	public static void sort(int[] arr) {
		if (arr.length<2) {
			return;
		}
		
		// Merge sequence storage space
		int[] tmp = new int[arr.length];
		merge(arr, 0, arr.length-1, tmp);
	}
	
	/** * use divide-and-conquer to sort an array *@paramArr The array to sort by *@paramStart Specifies the initial index * of the array@paramEnd Indicates the end subscript */ of data
	private static void merge(int[] arr, int start, int end, int[] tmp) {
		
		// Check whether the number of elements passed between start and end is 1
		// If not, continue to divide
		if (end - start > 0) {
			int middle = (start+end)/2;
			// Sort the left half
			merge(arr, start, middle, tmp);
			// Sort the right half
			merge(arr, middle+1, end, tmp);
			
			// The left and right parts are sorted
			// Record the left half of the pointer
			int left = start;
			// Record the right part of the pointer
			int right = middle+1;
			// Record the index of the ordered sequence
			int index = start;
			
			// Assign the following two parts to the TMP array
			for(int i=start; i<=middle; i++) {
				tmp[i] = arr[i];
			}
			for(int i=middle+1; i<=end; i++) {
				tmp[i] = arr[i];
			}
			
			// Start comparing
			while(left<=middle && right<=end) {
				if (tmp[left]<tmp[right]) {
					arr[index++] = tmp[left++];
				} else{ arr[index++] = tmp[right++]; }}// Assign the rest
			while(left<=middle) {
				arr[index++] = tmp[left++];
			}
			while(right<=end) { arr[index++] = tmp[right++]; }}}}Copy the code

test

package com.xgc.sort.advancedsorting.mergesort;

public class MergeSortTest {
	
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		MergeSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(nlogn)

Space complexity: O(n)

Stability: stability

Quick Sort

Quicksort is an improvement on bubbling sort

Quicksort idea

Pick out an element from the data to be sorted, called a baseline.
Reorder the sequence so that those smaller than the base are placed in front of the base and those larger than the base are placed behind it.
Recursively sorts subsequences of elements less than the base value and subsequences of elements greater than the base value;

Code implementation

package com.xgc.sort.advancedsorting.quicksort;

public class QuickSort {
	
	public static void sort(int[] arr) {
		quicksort(arr, 0, arr.length-1);
	}

	/** * recursive quicksort *@paramArr The array to sort by *@paramLeft The starting subscript * of the part to be sorted@paramRight The end subscript of the part to be sorted */
	private static void quicksort(int[] arr, int left, int right) {
		if(left<right) {
			int partitionIndex = partition(arr, left, right);
			quicksort(arr, left, partitionIndex-1);
			quicksort(arr, partitionIndex+1, right); }}/** * places the number greater than the base value to the right and the number less than the base value to the left *@paramArr The array to sort by *@paramLeft The starting subscript * of the part to be sorted@paramRight The end subscript * of the part to be sorted@returnThe subscript of the base number */
	private static int partition(int[] arr, int left, int right) {
		// Record the subscript of the base value
		int pivot = left;
		
		while(left<right) {
			while (arr[pivot] <= arr[right] && left<right) {
				right--;
			}
			while (arr[pivot] >= arr[left] && left<right) {
				left++;
			}
			
			if (left<right) {
				inttmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; }}int tmp = arr[pivot];
		arr[pivot] = arr[left];
		arr[left] = tmp;
		returnleft; }}Copy the code

test

package com.xgc.sort.advancedsorting.quicksort;

public class QuickSortTest {
	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		QuickSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(nlogn)

Space complexity: O(1)

Stability: unstable

Counting Sort

Counting sort is a kind of sorting algorithm which is not based on comparison. Its advantage is that it is faster than any comparison sorting algorithm when sorting integers within a certain range. It’s a trade off of space for time.

Counting sort idea

Comparison of integers in the range [m,n] :

Open up a new array B with an integer length of n-m+1
Go through the array, count the number of each value is I, save the array B subscript i-m position
Reverse fill array: Assign the subscript I +m of the number in array B >0 to the target array and subtract the corresponding value by one

Code implementation

package com.xgc.sort.advancedsorting.countingsort;

/** * count sort *@author xgc
 *
 */
public class CountingSort {
	
	public static void sort(int[] arr) {
		int[] values = getValue(arr);
		int minValue = values[0];
		int maxValue = values[1];
		int[] newArr = new int[maxValue-minValue+1];
		// Go through the array and count the number of the same value, assign the value to the corresponding position of the new array
		for(int value: arr) {
			newArr[value-minValue]++;
		}
		
		// Reverse populates the target array
		int index = 0;
		for(int i=0; i<newArr.length; i++) {
			while (newArr[i] > 0) { arr[index++] = i+minValue; newArr[i]--; }}}/** * get the minimum and maximum array *@param arr
	 * @returnThe array length is 2, the first is the minimum and the second is the maximum */
	private static int[] getValue(int[] arr) {
		int maxValue = arr[0];
		int minValue = arr[0];
		for(int value: arr) {
			if (value>maxValue) {
				maxValue = value;
			} else if(value < minValue) { minValue = value; }}int[] value = {minValue, maxValue};
		returnvalue; }}Copy the code

test

package com.xgc.sort.advancedsorting.countingsort;

public class CountingSortTest {

	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		CountingSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(n + k), where K is an integer range

Space complexity: O(n+ K)

Stability: stability

Bucket Sort

Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. To make bucket sorting efficient, we need to do two things:

Increase the number of barrels as much as extra space is available
The mapping function used can evenly distribute the N input data into K buckets

At the same time, the comparison sorting algorithm is very important to the performance of bucket elements.

Bucket sorting idea

Divide the data to be sorted into a finite number of buckets.
Each bucket is sorted separately (you can use a different sort algorithm or recursively use bucket sort to sort)

Code implementation

Insert sort is used for each bucket, as shown in the simple Sort -> Insert Sort section above

package com.xgc.sort.advancedsorting.bucketsort;

import java.util.Arrays;

import com.xgc.sort.simplesort.insertionsort.InsertionSort;

public class BucketSort {
	
	/** * Sort buckets *@paramArr The array to sort by *@paramBucketSize Size of each bucket */
	public static void sort(int[] arr, int bucketSize) {
		if (arr.length==0) {
			return;
		}
		
		int minValue = arr[0];
		int maxValue = arr[0];
		for (int value : arr) {
			if (value < minValue) {
				minValue = value;
			} else if(value > maxValue) { maxValue = value; }}int bucketCount = (int)Math.floor((maxValue-minValue) / bucketSize) + 1; 
		int[][] buckets = new int[bucketCount][0];
		
		// Allocate data to buckets using mapping functions
		// Buckets with index I store more data than buckets with index I +1
		for (int i = 0; i < arr.length; i++) {
			int index = (int)Math.floor((arr[i]-minValue) / bucketSize);
			buckets[index] = arrAppend(buckets[index], arr[i]);
		}
		
		int arrIndex = 0;
		for(int[] bucket: buckets) {
			if (bucket.length<=0) {
				continue;
			}
			// Sort each bucket, using insert sort
			InsertionSort.sort(bucket);
			for (intvalue : bucket) { arr[arrIndex++] = value; }}}/** * Automatically expand buckets and save data *@paramArr barrels *@paramValue Specifies the array * to save@returnBuckets that have been expanded and saved data */
	private static int[] arrAppend(int[] arr, int value) {
		arr = Arrays.copyOf(arr, arr.length+1);
		arr[arr.length-1] = value;
		returnarr; }}Copy the code

test

package com.xgc.sort.advancedsorting.bucketsort;

public class BucketSortTest {

	public static void main(String[] args) {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		BucketSort.sort(arr, 3);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

The result is as follows:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(n + C), c = N*(logn-logm), where n is the number of data to be sorted and m is the number of buckets

Space complexity: O(n+m)

Stability: stability

Radix Sort

Radix sort is a non – comparison integer sort algorithm.

Radix sort idea

The idea of radix sort is to cut the integers into different numbers by the number of digits, and then compare them individually by the number of digits

The GIF is shown below:

Code implementation

package com.xgc.sort.advancedsorting.radixsort;

import java.util.Arrays;

/** * Base sort (including negative numbers) *@author xgc
 *
 */
public class RadixSort {
	
	
	public static void sort(int[] arr) {
		int maxDigit = getMaxDigit(arr);
		
		int mod = 10;
		int dev = 1;
		
		for(int i=0; i<maxDigit; i++, mod*=10, dev*=10) {
			// In the case of negative numbers, double the number of queues, where [0-9] corresponds to negative numbers and [10-19] corresponds to positive numbers (bucket + 10).
			// for each round counter expands 10 times, with the second round [0,99] corresponding to negative numbers and [100,199] corresponding to positive numbers
            int[][] counter = new int[mod * 2] [0];

            for (int j = 0; j < arr.length; j++) {
            	// bucket = arr[j]/dev
            	// This calculation takes into account the negative case
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (intvalue : bucket) { arr[pos++] = value; }}}}/** * Gets the maximum number of digits in the array *@param arr
	 * @returnMaximum number of digits */
	private static int getMaxDigit(int[] arr) {
		int maxValue = getMaxValue(arr);
		return getNumLength(maxValue);
	}

	/** * gets the maximum value in the array *@param arr 
	 * @returnThe maximum * /
	private static int getMaxValue(int[] arr) {
		int maxValue = arr[0];
		for (int value : arr) {
			if(value > maxValue) { maxValue = value; }}return maxValue;
	}
	
	/** * gets the number of digits of the specified value *@paramValue Specifies the value *@returnDigits * /
	private static int getNumLength(int value) {
		if (value==0) {
			return 1;
		}
		
		int length = 0;
		for(inttemp = value; temp! =0; temp/=10) {
			length++;
		}
		return length;
	}
	
	/** * Expand array and save data *@paramThe arR will expand and store the array of data *@paramValue Data to be saved *@returnExpand and save the data after the array */
	private static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        returnarr; }}Copy the code

test

package com.xgc.sort.advancedsorting.radixsort;

public class RadixSortTest {

	public static void main(String[] args) throws Exception {
		int[] arr = {4, -1.5.9.16.10.7.4, -3};
		RadixSort.sort(arr);
		for (int i : arr) {
			System.out.print(i+","); }}}Copy the code

Execution Result:

-3,-1,4,4,5,7,9,10,16,
Copy the code

The complexity of the

Time complexity: O(D (r+ N)), the maximum number of digits in the sequence is D, the cardinal number of digits is R, and the number of elements in the sequence is N

Space complexity: O(rd+ N)

Stability: stability

Ten classical sorting algorithm ideas and Java code implementation

Simple sorting

Bubble sort

Bubble sort ideas

Algorithm description

Code implementation

test

The complexity of the

Insertion sort

Insertion sort idea

Code implementation

test

The complexity of the

Selection sort

Selection sorting idea

Code implementation

test

The complexity of the

Shell’s Sort

Hill sorting algorithm idea

Code implementation

test

The complexity of the

Heap Sort

Heapsort idea

Code implementation

test

The complexity of the

Merge Sort

The idea of merge sort

Code implementation

test

The complexity of the

Quick Sort

Quicksort idea

Code implementation

test

The complexity of the

Counting Sort

Counting sort idea

Code implementation

test

The complexity of the

Bucket Sort

Bucket sorting idea

Code implementation

test

The complexity of the

Radix Sort

Radix sort idea

Code implementation

test

The complexity of the

Related Posts

Five minutes for quick access to the Airflow workflow

Prefix tree/dictionary tree introduction and simple application

Light work: Four times faster Python data processing scripts with three lines of code