[LintCode] Sort Integers II [Merge-sort, Quick-sort, Heap-sort]

Problem

Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Example

Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].

Note

考察对Heap Sort, Quick Sort, Merge Sort的掌握。

Solution

Merge Sort

public class Solution {    public void sortIntegers2(int[] A) {        if (A.length = end) return;        int mid = start + (end - start) / 2;        sort(A, start, mid, B);        sort(A, mid+1, end, B);        merge(A, start, mid, end, B);    }    public void merge(int[] A, int start, int mid, int end, int[] B) {        int i = start, j = mid+1, index = start;        while (i 0;i--){            exchange(0, i);            n=n-1;            maxheap(a, 0);        }    }    public static void buildheap(int []a){        n=a.length-1;        for(int i=n/2;i>=0;i--){            maxheap(a,i);        }    }    public static void maxheap(int[] a, int i){         left=2*i;        right=2*i+1;        if(left  a[i]){            largest=left;        }        else{            largest=i;        }        if(right  a[largest]){            largest=right;        }        if(largest!=i){            exchange(i,largest);            maxheap(a, largest);        }    }    public static void exchange(int i, int j){        int t=a[i];        a[i]=a[j];        a[j]=t;     }}

Quick Sort

public class Solution {    public void sortIntegers2(int[] A) {        if (A.length = end) return;        int mid = start+(end-start)/2;        int pivot = A[mid], i = start, j = end;        while (i  pivot) j--;            if (i <= j) {                int temp = A[i];                A[i] = A[j];                A[j] = temp;                i++;                j--;            }        }        quicksort(A, start, j);        quicksort(A, i, end);    }}

关键字：heap, sort, quicksort, java

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！