Bubble sorting and optimization

SelectionSort

Heap sort (HeapSort)

Insertion sort and optimization

ascending

Heap sort can be thought of asSelection sortAn optimization of

Time order NlogN, unstable

core idea

  1. Heapify the sequence in place.

  1. Swap the first element with the last (big top heap, swap top and bottom heap elements).

  2. Subtract one from the heap.

  3. Perform a siftDown operation on the heap top

  1. Repeat 2 to 4 steps until there is only one element left in the heap.

Time complexity: steps 1 O (n) + 5 O (n – 1) * step 2 ~ 4 O (1 + 1 + logn) = O (n) + O (nlogn) = O (nlogn)

Code implementation

public class HeapSort extends Sort {

    private int heapSize;

    @Override
    protected void sort(a) {

        // Build the heap in place
        heapSize=array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        
        while (heapSize > 1) {
            // Swap the top and tail elements,heapSize--
            swap(0, --heapSize );

            // Restore heap properties for position 0 siftDown
            siftDown(0); }}private void siftDown(int index) {
        Integer element = array[index];

        int half = heapSize >> 1;
        while (index < half) { // Index must be a non-leaf node
            // The default is left to parent
            int childIndex = (index << 1) + 1;
            Integer child = array[childIndex];

            int rightIndex = childIndex + 1;
            // The right child is larger than the left child
            if (rightIndex < heapSize &&
                    cmp(array[rightIndex], child) > 0) {
                child = array[childIndex = rightIndex];
            }

            // Greater than or equal to the child node
            if (cmp(element, child) >= 0) break; array[index] = child; index = childIndex; } array[index] = element; }}Copy the code

I wrote a demo to test the efficiency of bubbling, selection, and heap sort. The output is as follows:

【HeapSort】0.001 s (1 ms) :1.69All exchange:999-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - the BubbleSort time-consuming 】 :0.007 s (7 ms) :21.52All exchange:13.87M -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - SelectionSort time-consuming 】 :0.007 s (7 ms) :49.95All exchange:999
------------------------------------------------------------------

Process finished with exit code 0
Copy the code

You can see that the selection sort and heapsort elements swap the same number of times.

Heap sort is unstable sort, because it’s built in place so it’s O(1)

Reference: The love of Data Structures issue 2