This post was originally posted on my blog

preface

This series includes ten classic sorting algorithms.

  • The language used is Java
  • The structure is: define abstract classesSortIt implements swap, size comparison and so on. For example, if you swap two values, just pass in the subscript. All other concretely sorted classes inherit from abstract classesSort. So we can focus on the algorithm itself.
/* * Return value is 0, indicating array[i1] == array[i2] * return value is less than 0, indicating array[i1] < array[i2] * return value is greater than 0, indicating array[i1] < array[i2] * return value is greater than 0. Array [i1] > array[i2] */ protected int CMP (int i1, int i2) {return array[i1].compareTo(array[i2]);
	}
	
	protected int cmp(T v1, T v2) {
		return v1.compareTo(v2);
	}
	
	protected void swap(int i1, int i2) {
		T tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}

Copy the code

  • Bubble, select, insert, merge, hill, and heap sort are all comparison based sorts

    • Minimum average time complexity O(nlogn)

  • Counting sort, bucket sort, and radix sort are not comparison – based sorts

    • Using space for time, sometimes the average time complexity can be less than order nlogn.

What is bucket sort

  • Bucket sort, or box sort, is a sorting algorithm that works by sorting an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or to continue sorting using bucket sort recursively). Bucket sort is a kind of induction result of pigeon nest sort. Bucket sorting uses linear time (O (n)) when the values in the array to be sorted are evenly distributed. But bucket sort is not comparison sort, and it is not affected by the O(n log n) lower bound.

Bucket sort can be seen as an upgraded version of counting sort

  • The data to be sorted into multiple ordered buckets, the data in each bucket is sorted separately, and then the data in each bucket is taken out in turn to complete sorting

Algorithm stability

  • Bucket sorting is a stable sorting algorithm.

Is it in place

  • What is the in situ algorithm?
    • Not dependent on additional resources or on a few additional resources, relying only on the output to override the input
    • The spatial complexity of 𝑂(1) can be considered as in situ algorithm
  • The non-in-situ algorithm is called not-in-place or out-of-place
  • Bucket sorting is not in-place

Space-time complexity

  • Time complexity: O(n+k), where K is n*logn-n*logm

  • Space complexity: O(n+m), where M is the number of buckets

code

  • Bucket sort internal implementation can use the idea of counting sort

  • Code to create a quarter of the array length of a bucket, the specific number according to their own needs, can be adjusted

package YZ.Sort;

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort extends Sort<Integer>{

	@Override
	protected void sort() {// TODO auto-generated method Stub // Max/Min int Max = array[0]; int min = array[0]; int length = array.length/4;for(int i=1; i<array.length; i++) {
	        if(array[i] > max) {
	            max = array[i];
	        } else if(array[i] < min) { min = array[i]; Int diff = max-min; ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();for(int i = 0; i < length; i++){ bucketList.add(new ArrayList<>()); } // The storage range for each bucketfloat section = (float) diff / (float) (length - 1) ; // Add data to bucketfor(int i = 0; i < array.length; i++){
	        //当前数除以区间得出存放桶的位置 减1后得出桶的下标
	        int num = (int) (array[i] / section) - 1;
	        if(num < 0){ num = 0; } bucketList.get(num).add(array[i]); } // Bucket sortfor(int i = 0; i < bucketList.size(); I ++){// The collections.sort (bucketlist.get (I)); } // write the original array int index = 0;for(ArrayList<Integer> arrayList : bucketList){
	        for(int value : arrayList){ array[index] = value; index++; }}}}Copy the code

The results of

Data sources:

Generate 20000 data randomly from 1 to 80,000 to test

Integer[] array = Integers.random(20000, 1, 80000);

The results are as follows

[CountingSort] Stability: true Time: 0.005s(5ms) Comparison count: 0 Exchange count: 0

[QuickSort] Stability: false Time: 0.009s(9ms) Comparison count: 332,700 Exchange count: 13,200

[MergeSort] Stability: true Time: 0.01s(10ms) Comparison times: 261,000 exchange times: 0

【RadixSort】 Stability: true Time: 0.014s(14ms) Comparison times: 0 exchange times: 0

[ShellSort] Stability: false Time: 0.016s(16ms) Comparison times: 433,400 exchange times: 0

【HeapSort】 Stability: false Time: 0.023s(23ms) Comparison number: 510,900 exchange number: 20000

【BucketSort】 Stability: true Time: 0.024s(24ms) Comparison count: 0 Swap count: 0

Stability: true Time: 0.514s(514ms) Comparison times: 200 million exchange times: 200 million

[InsertionSort1] Stability: true Time-consuming: 1.362s(1362ms) Comparison times: 99351,500 exchange times: 99331,500

[BubbleSort] Stability: True Time: 2.529s(2529ms) Compare times: 200 million swap times: 99331,500

Code Address:

  • The code in git is at github