Sort

Three common and widely used sorting algorithm.

Heap sort

public class heapsort {

    public void heapsort(int[] arr){
        int len=arr.length;
        for(int i=(len-2)/2;i>=0;i--){
            heapify(arr.length, arr, i);
        }
        for(int i=len-1;i>0;i--){
            swap(arr, 0, i);
            heapify(i, arr, 0);
        }
    }

    public void heapify(int len,int[] arr, int i){
        int left=2*i+1;
        int right=2*i+2;
        int maxidx=i;
        if(left<len && arr[left]>arr[maxidx]) maxidx=left;
        if(right<len && arr[right]>arr[maxidx]) maxidx=right;
        if(maxidx!=i){
            swap(arr, maxidx, i);
            heapify(len, arr, maxidx);
        }
    }

    public void swap(int[] arr, int a, int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String[] args){
        Random rand=new Random();
        int[]arr=new int[20];
        for(int i=0;i<arr.length;i++) arr[i]=rand.nextInt(1000);
        System.out.println("Before sort:\n"+Arrays.toString(arr));
        heapsort test=new heapsort();
        test.sort(arr);
        System.out.println("After sort:\n"+Arrays.toString(arr));
    }
}

Quick sort

public class quicksort {
    public void sort(int[] arr,int a,int b){
        if(a<b){
            int i=partition(arr,a,b);
            sort(arr,a,i-1);
            sort(arr,i+1,b);
        }

    }
    public int partition(int[] arr,int low,int high){
    /* Version one:
        int point=arr[low];
        while(low<high){
            //Move the high pointer, find the array number smaller than middle pointer
            while(low<high && arr[high]>=point) high--;
            if(low<high) arr[low++]=arr[high];
            //Move the low pointer, find the array number greater than middle pointer
            while(low<high && arr[low]<point) low++;
            if(low<high) arr[high--]=arr[low];
        }
        arr[low]=point;
        return low;
    */
        int pivot=arr[low];
        int largerIndex=high;
        for(int i=high;i>low;i--){
            if(arr[i]>=pivot) swap(arr, i, largerIndex--);
        }
        swap(arr, low,largerIndex);
        return largerIndex;
    }

    public static void main(String[] args){
        Random rand=new Random();
        int[]arr=new int[15];
        for(int i=0;i<arr.length;i++) arr[i]=rand.nextInt(100);
        System.out.println("Before sort:\n"+Arrays.toString(arr));
        quicksort test=new quicksort();
        test.sort(arr,0,arr.length-1);
        System.out.println("After sort:\n"+Arrays.toString(arr));
    }
}

def quicksort(nums):
    quicksort_helper(nums, 0, len(nums)-1)

def quicksort_helper(nums, i, j):
    if i>=j:
        return
    pivot = nums[i]
    idx, idy = i+1, j
    while idx < idy:
        if nums[idx]<pivot:
            idx += 1
        else:
            nums[idx], nums[idy] = nums[idy], nums[idx]
            idy -= 1
    mid_idx = idx-1 if nums[idx] >= pivot else idx
    nums[i], nums[mid_idx] = nums[mid_idx], nums[i]
    quicksort_helper(nums, i, mid_idx-1)
    quicksort_helper(nums, mid_idx+1, j)

Merge sort (in place)

public class mergesort{
    public static void sort(int[] nums, int start, int end){
        if(end-start==0) return;
        int mid=start+(end-start)/2;
        sort(nums,start,mid);
        sort(nums,mid+1,end);
        int x=start, y=mid+1;
        while(x<=mid&&y<=end){
            if(nums[x]<=nums[y]) x++;
            else{
                int tmp=nums[y];
                for(int t=y;t>x;t--) nums[t]=nums[t-1];
                nums[x]=tmp;
                x++;
                y++;
                mid++;
            }
        }
    }

    public static void main(String[] args){
        Random rand=new Random();
        int[]arr=new int[15];
        for(int i=0;i<arr.length;i++) arr[i]=rand.nextInt(100);
        System.out.println("Before sort:\n"+Arrays.toString(arr));
        mergesort t=new mergesort();
        t.sort(arr,0,arr.length-1);
        System.out.println("After sort:\n"+Arrays.toString(arr));
    }
}