Sort without stability: select sort, quicksort, heap sort

Stable sorting: Bubble Sort, Insertion Sort, Merge Sort (nlogn)

Selection sort

Each traversal finds the index of the smallest element in the array, swapping in turn.

public int[] sortArray (int[] nums) {   
    for(int i=0; i<nums.length; i++) {
        int minIndex = i;
        for(int j=i+1; j<nums.length; j++) {
            minIndex = nums[j] < nums[minIndex] ? j : minIndex; 
        }
        swap(nums, i, minIndex);
    }
    return nums;
}

Quick sort

  • Quicksort is top to bottom, partitioning first and then dealing with subproblems.

Basic ideas:

  1. You start by looking for a base number in the array
  2. Move other elements larger than it to one side of the array, and smaller elements to the other side. This breaks the array into two parts.
  3. Repeat the second part for the left and right intervals until each interval has only one number.

The low pointer finds the element greater than pivot, the hight pointer finds the element less than pivot, switches the positions of the two elements, and then brings the base number back to its original position.

  • Method of filling holes
public void quickSort (int[] nums, int low, int high) {
    if(low < high) {
        int index = partition(nums, low, high);
        quickSort(nums, low, index-1);
        quickSort(nums, index+1, high);
    }
}

public int partition(int[] nums, int low, int high) {

    int pivot = nums[low];

    while(low < high) {
        while(low<high && nums[high] >= pivot) {
            high--;
        }
        nums[low] = nums[high];
        while(low<high && nums[low] <= pivot) {
            low++;
        }
        nums[high] = nums[low];
    }
    nums[low] = pivot;
    return low;
}
  • Exchange method

So this is essentially a combination of the digging and filling process, where the low pointer finds something greater than pivot, the hight pointer finds something less than pivot, and then the two elements switch positions, and then the base number is put back in place.

public void quickSort (int[] nums, int low, int high) { if(low < high) { int index = partition(nums, low, high); quickSort(nums, low, index-1); quickSort(nums, index+1, high); } } public int partition(int[] nums, int low, int high) { int pivot = nums[low]; int start = low; // record the low pointer while(low < high) {while(low < high & nums[high] >= pivot) high--; while(low < high && nums[low] <= pivot) low++; if(low >= high) { break; } swap(nums, low, high); } // swap(nums, start, low); return low; } public void swap(int[] nums, int i, int j) { if(i == j) return; nums[i] = nums[i] ^ nums[j]; nums[j] = nums[i] ^ nums[j]; nums[i] = nums[i] ^ nums[j]; }

Bubble sort

Compare the keywords of adjacent records in pairs, swapping them if they are in reverse order until there is no reverse order.

public int[] sortArray(int[] nums) {
        
    for(int i=0; i<nums.length; i++) {
        for(int j=0; j<nums.length-i-1; j++) {
            if(nums[j] > nums[j+1]) {
                swap(nums, j, j+1);
            }
        }
    }
    return nums;
}


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

Bubble Sort can be improved with flag flags, if swapped, the bit changed, if no change, the sort is ready!

Insertion sort

It is constantly compared to the number before it, and if the number before it is larger, it switches places with the number before it.

public int[] sortArray(int[] nums) { for(int i=1; i<nums.length; i++) { int j = i; // while(j >= 1 &&nums [j] < nums[j-1]) {swap(nums, j, j-1); j--; }} return nums; } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

Merge sort

  • Merge sort uses the idea of divide and conquer.
  • The whole is just a simple recursion, sort the left hand side, sort the right hand side, and then sort the whole thing. So how do we get the whole thing organized? To prepare a secondary space, look at the left side of both sides of the order, and the one who is smaller will enter the secondary space first (outer sorting method).
  • Merge sort has the fewcomparisons of all sorts, and it starts with a constant partition. Comparisons only happen when you merge ordered subarrays.

public int[] sortArray (int[] nums) { int[] temp = new int[nums.length]; mergeSort(nums, 0, nums.length-1, temp); return nums; } public void mergeSort(int[] nums, int low, int high, int[] temp) { int mid = (low + high) / 2; If (low < high) {nums, low, mid, temp; mergeSort(nums, mid+1, high, temp); // merge merg(nums, low, high, mid, temp); } } public void merg(int[] nums, int low, int high, int mid, int[] temp) { int index = 0; int i = low; Int j = mid + 1; / / right sequence starting index while (I < = mid & j < = high) {if (nums [I] < = nums [j]) {/ / here it is better to < = \ [index++] = nums [i++]; } else { temp[index++] = nums[j++]; }} / / if the sequence and the left while remaining (I < = mid) {\ [index++] = nums [i++]; } / / if the right sequence and while remaining (j < = high) {\ [index++] = nums [j++]; } // Assign temp to nums for(int t=0; t<index; t++) { nums[low + t] = temp[t]; }}

The time is order NlogN.

The extra space complexity is O(N).

Heap sort

  • The binary heap must be a complete binary tree, and each node in the binary heap must be greater than or equal to the value of each node in its subtree.

  • Because the heap is a complete binary tree, we can store it in arrays. If the subscript of the root node is treated as 0, the complete binary tree has the following properties:

    • Its left child is subscript: 2i + 1
    • Its right child is subscript: 2i + 2
    • For a complete binary tree with n elements (n >2), the subscript of its last non-leaf node is n/ 2-1

Construction of large-top heap: The initial state of the whole sequence is regarded as a complete binary tree, and the structure of the tree is adjusted from the bottom up to meet the requirements of large-top heap.

The variable heapSize is used to keep track of how many numbers are left that have not been sorted. Each time a number at the top of the heap is swapped, heapSize decreases by 1. In the MaxHeapify method, heapSize is used to limit the remaining contestants from being beaten up in comparison to those already at the end of the array who have won.

  1. The initial large-top heap is built, and the heap starts from the last non-leaf node.
  2. Enter the loop, place the maximum value at the end of the array, and heap the resize position. Loop to the maximum number of indexes, sorted out.
Public int[] sortarRay (int[] nums) {buildMaxHeap(nums); for(int i=nums.length - 1; i >= 0; i--) { swap(nums, 0, i); // MaxHeapify (nums, 0, I); // MaxHeapify (nums, 0, I); } return nums;} return nums; } public void buildMaxHeap(int[] nums) {// Start with the last non-leaf; Int I = nums.length / 2-1 for(int I = nums.length / 2-1; int I = nums.length / 2-1; i>=0; i--) { maxHeapify(nums, i, nums.length); }} public void maxHeapify(int[] nums, int I, int heapSize) {int l = 2 * I + 1; // int r = l + 1; Int largest = I; If (l < heapSize && nums[l] > nums[l] > 1, 0, 0, 0, 0, 0, 0, 0) if(r < heapSize && nums[r] > nums[largest]) largest = r; // If any child is larger than the root, then swap and adjust the large top heap again by largest. if(largest ! = i) { swap(nums, i, largest); maxHeapify(nums, largest, heapSize); } } public void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }