国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Java - Sorting Algorithms

陳江龍 / 1940人閱讀

Complexity
Quicksort Mergesort Heapsort
Time Complexity O(nlogn) O(nlogn) O(nlogn)
Space Complexity O(1) O(n) Could be O(1)
Quicksort

Quicksort is similar to MergeSort in that the sort is accomplished by dividing the array into two partitions and then sorting each partition recursively.

In Quicksort, the array is partitioned by placing all items smaller than some pivot item before that item and all items larger than the pivot item after it.

There are many different versions of Quicksort that pick pivot in different ways.

Always pick first element as pivot.

Always pick last element as pivot.

Pick a random element as pivot.

Pick median as pivot.

Implement Quicksort in Java using Arrays (Takes the last element as pivot)

public class QuickSortArray {
    
    private int partition (int arr[], int low, int high) {
        
        int pivot = arr[high];
        int i = low - 1;
        for (int j=low; j

Implement Quicksort in Java using LinkedList (Takes the median as pivot)

public class QuickSortList {

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode mid = findMedian(head); // O(n)
        
        ListNode leftDummy = new ListNode(0), leftTail = leftDummy;
        ListNode rightDummy = new ListNode(0), rightTail = rightDummy;
        ListNode middleDummy = new ListNode(0), middleTail = middleDummy;
        while (head != null) {
            if (head.val < mid.val) {
                leftTail.next = head;
                leftTail = head;
            } else if (head.val > mid.val) {
                rightTail.next = head;
                rightTail = head;
            } else {
                middleTail.next = head;
                middleTail = head;
            }
            head = head.next;
        }
        
        leftTail.next = null;
        middleTail.next = null;
        rightTail.next = null;
        
        ListNode left = sortList(leftDummy.next);
        ListNode right = sortList(rightDummy.next);
        
        return concat(left, middleDummy.next, right);
    }
    
    private ListNode findMedian(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    private ListNode concat(ListNode left, ListNode middle, ListNode right) {
        ListNode dummy = new ListNode(0), tail = dummy;
        
        tail.next = left; tail = getTail(tail);
        tail.next = middle; tail = getTail(tail);
        tail.next = right; tail = getTail(tail);
        return dummy.next;
    }
    
    private ListNode getTail(ListNode head) {
        if (head == null) {
           return null;
        } 
       
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }
}
Mergesort

Mergesort is based on divide-and-conquer paradigm. It involves the following three steps:

Divide the array into two (or more) subarrays.

Sort each subarray (Conquer).

Merge them into one.

Implement Mergesort in Java using Arrays

public class MergeSortArray {

    public void sortArray (int[] arr, int left, int right) {
        
        if (left < right) {
            int mid = left + (right - left)/2;
            sortArray (arr, left, mid);
            sortArray (arr, mid+1, right);
            mergeArray (arr, left, mid, right);
        }
    }
    
    private void mergeArray (int[] arr, int left, int mid, int right) {
        
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        int[] L = new int[n1];
        int[] R = new int[n2];
        
        for (int i=0; i < n1; i++) {
            L[i] = arr[left + i];        
        }
        for (int j=0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }
        
        /* Merge the temp arrays */         
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarry array
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]){
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}

Implement Mergesort in Java using LinkedList

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 

public class MergeSortList {
    /**
     * @param head: The head of linked list.
     * @return: The head of the sorted linked list.
     */
    public ListNode sortList(ListNode head) {  
        
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode mid = findMid(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        
        return mergeList(left, right);
    }
    
    private ListNode findMid (ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
            
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
        
    private ListNode mergeList (ListNode left, ListNode right) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
            
        while (left != null && right != null) {
            if (left.val <= right.val) {
               tail.next = left;
               left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }
            tail = tail.next;
        }    
        
        if (left != null) {
            tail.next = left;
        } else {
            tail.next = right;
        }
            
        return dummy.next;
    }
}
Heapsort

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

Heap Sort Algorithm for sorting in increasing order:

Build a max heap from the input data.

At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.

Repeat above steps while size of heap is greater than 1.

Implement Heapsort in Java using Arrays

public class HeapSort {
    
    public void sort(int arr[]) {
    
        int n = arr.length;
 
        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
 
        // One by one extract an element from heap
        for (int i=n-1; i>=0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
 
            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }
 
    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int arr[], int n, int i) {
        int largest = i;  // Initialize largest as root
        int l = 2*i + 1;  // left = 2*i + 1
        int r = 2*i + 2;  // right = 2*i + 2
 
        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;
 
        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;
 
        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
 
            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }
}
References

Foundations of Algorithms, Richard E. Neapolitan, Chapter 2 Divide and Conquer

Sorting, CMU

Big-O Algorithm Complexity Cheat Sheet

Java sorting algorithms - Implementations

Merge Sort, GeeksforGeeks

Quick Sort, GeeksforGeeks

Heap Sort, GeeksforGeeks

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/67158.html

相關文章

  • JavaScript 排序算法圖解(JavaScript sorting algorithms

    摘要:基礎構造函數以下幾種排序算法做為方法放在構造函數里。代碼圖解選擇排序選擇排序算法是一種原址比較排序算法。它的性能通常比其他的復雜度為的排序算法要好。代碼劃分過程圖解排序沒有定義用哪個排序算法,所以瀏覽器廠商可以自行去實現算法。 基礎構造函數 以下幾種排序算法做為方法放在構造函數里。 function ArrayList () { var array = []; // 交換位置...

    h9911 評論0 收藏0
  • java-工具類Collections和Arrays的設計和區別

    摘要:排序的算法是歸并排序。舉個例子,的算法可以不是使用歸并排序,但是該算法一定要是穩定的。這個類是的一部分。官方這個類只包含操作或返回集合的靜態方法。具體來說是,第一步,先把集合轉換為數組,第二步,調用。和沒有什么區別,只是傳參有點不同。 Arrays 1.作用看類的名字,就知道是對數組(數據類型[])進行各種操作。例如,排序、查找、復制等。 排序的算法是歸并排序。查找的算法是二分查找。復...

    mj 評論0 收藏0
  • Algorithms, Princeton, Coursera課程整理與回顧

    摘要:除特別標注外,文章非原創插圖全部來自課程相關資源。劇透預警內容包含大作業的關鍵問題解法分析。為的返回值此方案下,判斷只需要對應,判斷使用結果準確,判斷檢測的對應是否為。更新此方法已確定違反的。 Princeton的算法課是目前為止我上過的最酣暢淋漓的一門課,得師如此夫復何求,在自己的記憶徹底模糊前,愿對這其中一些印象深刻的點做一次完整的整理和回顧,以表敬意。 注:這是一篇更關注個人努力...

    Luosunce 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<