Quick sort and heap sort

Fast sorting idea: in partition, the rightmost value is used as partition value x, and the interval less than x, the interval equal to x, and the three intervals greater than X are maintained respectively. Finally, the left and right boundaries of partition value are returned. The time complexity is O(nlogn)

public class QuickSort {
    public static void quickSort(int[] arr) {
        if(arr == null || arr.length < 2)
            return ;
        sortProgress(arr, 0 , arr.length - 1);
    }
    public static void sortProgress(int[] arr, int L, int R) {
        if(L < R) {
            //Randomly take a number from L to R and exchange it with R
            swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
            //The size of p array is 2,p[0] represents the left boundary of partition value, p[1] represents the right boundary of partition value
            int[] p = partition(arr, L, R);
            sortProgress(arr, L, p[0] - 1);
            sortProgress(arr, p[1] + 1, R);
        }
    }
    public static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R;
        while(L < more) {
            if(arr[L] < arr[R]) {
                swap(arr, ++less, L++);
            }else if(arr[L] > arr[R]) {
                swap(arr, --more, L);
            }else {
                L++;
            }
        }
        swap(arr, more, R);
        //Returns the left and right boundaries of the partition value
        return new int[] {less + 1, more};
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    } 
    public static void main(String[] args) {
        int[] arr = new int[]{123,45,767,343,654,2,66,88};
        System.out.print("Primitive array:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length - 1)
                System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
        quickSort(arr);
        System.out.print("After quick sort:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length)
                System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
    }   
}

Operation result:

Heap sorting idea: in the process of building the largest heap, each time you adjust it up, you only need to compare it with the parent node. The time complexity of building the heap is O(n). In the process of heap sorting, you can exchange the top elements with the last one, then adjust the top elements down, maintain the largest heap, and finally finish the sorting. The time complexity is O(nlogn)

public class HeapSort {
public static void heapSort(int[] arr) {
    if(arr == null || arr.length < 2)
        return ;
    for(int i = 0; i < arr.length; i++)
    heapInsert(arr, i);
    int size = arr.length;
    swap(arr, 0, --size);
    while(size > 0) {
        heapify(arr, 0, size);
        swap(arr, 0, --size);
    }

}
public static void heapInsert(int[] arr, int index){
    while(arr[index] > arr[(index - 1)/2]) {
        swap(arr, index, (index - 1)/2);
        index = (index - 1) / 2;
    }
}
public static void heapify(int[] arr, int index, int size){
    int left = 2 * index + 1;
    while(left < size){
        int largest = left + 1 < size && arr[left + 1] > arr[left]? left + 1: left;
        largest = arr[index] > arr[largest] ? index: largest;
        if(largest == index) {
            break;
        }
        swap(arr, index, largest);
        index = largest;
        left = 2 * index + 1;
    }
}
public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
    public static void main(String[] args) {
        int[] arr = new int[] {3,66,65,43,213,76,66,23};
        System.out.print("Primitive array:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length - 1)
            System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
        heapSort(arr);
        System.out.print("After heap sorting:");
        for(int i = 0; i < arr.length; i++)
            if(i != arr.length - 1)
                System.out.print(arr[i] + " ");
            else
                System.out.println(arr[i]);
    }
}

Operation result:

summary
Fast sorting is not stable. Algorithm time complexity O(nlogn)
Heap ordering is not stable. Algorithm time complexity O(nlogn).

Tags: Java less

Posted on Fri, 20 Mar 2020 11:44:02 -0700 by ShiloVir