This is the 8th day of my participation in Gwen Challenge

  • Merge Sort

    The divide-and-conquer idea, you can do it recursively, and you end up merging two arrays.

    Pseudo code

    / / A array, Merge_sort (A,n){merge_sort_internal(A,0,n-1)} merge_sort_internal(A,p,r){if(p >= r) then Q = p + ((r-p) >> 2) merge_sort_internal(p,q) Will be A [p]... q and A [r] q + 1... into A [r] p... the merge (A, p, q, r) / / merge (A/p, q, A/q + 1, r)}Copy the code

    The code is as follows, especially when combining two arrays, which array still contains a value.

    callpublic static void main(String[] args) {
        int[] a = {9.9.10.11.12.1.3.5.6.8};
        mergeSortA(a,a.length);
        System.out.println(Arrays.toString(a));
    }

public static void mergeSortA(int[] a,int length){
        mergeInternal(a,0,length - 1);
    }

    private static void mergeInternal(int[] a,int p,int r){
        if (p >= r){
            return;
        }

        int q = p + ((r - p) >> 2);
        mergeInternal(a,p,q);
        mergeInternal(a,q+1,r);

        mergeArray(a,p,q,r);
    }

    private static void mergeArray(int[] a,int p,int q,int r){

        int i = p;
        int j = q+1;
        int k = 0; // Use the temp array
        int[] temp = new int[r-p+1];
        while (i <= q && j <= r){
            if (a[i] <= a[j]){
                temp[k++] = a[i++];
            } else{ temp[k++] = a[j++]; }}int start = i;
        int end = q;
        if (j <= r){ Temp [k++] = a[j++]; temp[k++] = a[j++]; temp[k++] = a[j++]; temp[k++] = a[j++]; J will always be greater than r
            start = j;
            end = r;
        }

        while (start <= end){
            temp[k++] = a[start++];
        }

        for (int m = 0; m <= r-p; m++){ a[p+m] = temp[m]; }Copy the code

    Merge sort is not an in-place sort algorithm because it involves merging arrays, consuming extra space (the Achilles heel) and is a stable sort algorithm.

  • Quick Sort

    From the set of data subscript p to R in the sorted array, choose any data subscript P to R as pivot (partition point Q), less than pivot in front, greater than pivot in back. Divide-and-conquer, recursively, until p, q minus 1, q plus 1, r are reduced to 1, and they’re ordered.

    The core idea of quicksort is divide and conquer and partition.

    Pseudo code:

    Quick_sort (A,n){//n is the array size quick_sort_internal(A,0,n-1)} quick_sort_internal(A,p,r){if(p >= r) return // Terminating condition q = Quick_sort_internal (A,p,q-1) quick_sort_internal(A,q+1,r)} // Partition (A,p,r){return Partition point}Copy the code

    If you want quicksort to be an in-place sort algorithm, the space complexity is O(1){O(1)}O(1), and no extra space is required. Quicksort is not a stable sorting algorithm (involving exchange of values).

    The specific code is as follows:

        private static void quickSortA(int[] a,int length){
        quickSortInternal(a,0,length - 1);
    }


    private static void quickSortInternal(int[] a,int left,int right){
        if (left >= right) return;
        int q = division(a,left,right);
        quickSortInternal(a,left,q-1);
        quickSortInternal(a,q+1,right);

    }

    private static int division(int[] a,int left,int right){
        int base = a[left];   // Use the left as the reference point

        while (left < right) {
            // Start at the right end of the sequence and work left to find a value less than base
            while (left < right && a[right] >= base) {
                right--;
            }
            a[left] = a[right];

            // Start at the left end of the sequence and work right to find a value greater than base
            while (left < right && a[left] <= base){
                left++;
            }
            a[right] = a[left];
        }
        a[left] = base;
        return left;
    }
Copy the code

    Quicksort versus merge sort, which is bottom up, dealing with subproblems first, and then merging, whereas quicksort is top down, partitioning first, and then dealing with subproblems.

  • Heap Sort

    Heap sort can be broken down into two big steps, build heap and sort. The time to build the heap is O(n), and we organize the heap according to the characteristics of the big top heap. The heap can be inserted from top to bottom or from bottom to top. Sorting is a bit like deleting the top element of the heap. First swap the positions of 0 and N, then heap 0 k-1, then swap the positions of 0 and n-1, heap 0 k-2, and so on.

    Heapsort is an in-place sorting algorithm with time complexity O(nlogn), which is not a stable sorting algorithm. Because in the sorting process, there exists the operation that the last node changes the heap point, so it is possible to change the original relative order of the data with the same value.

    public static void heapSort(int[] a, int length) {
    / / build the heap
    buildHead(a, length);
    / / sorting
    int k = length - 1;
    while (k > 0) {
        swap(a, 0, k);
        --k;
        heapify(a, k, 0); }}private static void heapify(int[] a, int n, int i) {
    while (true) {
        int maxPos = i;
        if (i * 2 + 1 <= n && a[i] < a[i * 2 + 1]) {
            maxPos = i * 2 + 1;
        }
        if (i * 2 + 2 <= n && a[maxPos] < a[i * 2 + 2]) {
            maxPos = i * 2 + 2;
        }
        if (maxPos == i) {
            break; } swap(a, i, maxPos); i = maxPos; }}private static void buildHead(int[] a, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapifyA(a, length - 1, i); }}Copy the code

Why is quicksort better than heap sort?

  • Heapsort data access is not as friendly as quicksort. Data may be accessed with subscripts of 1,2,4,8 when heaped, rather than locally sequential access like quicksort, so it is not cpu-cache friendly.
  • For the same data, the heapsort algorithm exchanges more data than quicksort during sorting.

Why is insert sort more popular than bubble sort?

Because bubble sort, no matter how optimized it is, the number of elements swapped is a fixed value, which is the degree of reverse order of the original data. Insert sort is the same, no matter how optimized it is, the number of element moves is equal to the degree of reverse order of the original data. The data exchange for bubble sort is more complex than the data movement for insert sort, which requires three assignment operations compared to one for insert sort.

Data exchange operations in bubble sort:if (a[j] > a[j+1]) { / / exchange
   int tmp = a[j];
   a[j] = a[j+1];
   a[j+1] = tmp;
   flag = true; } insert sort data move operation:if (a[j] > value) {
  a[j+1] = a[j];  // Data movement
} else {
  break;
}
Copy the code