Summary

1.Array memory space complexity:

Quick sort :O(1)

Merge sort: O(n)

Heap sort: O(n)

2.Quick Sort VS Merge Sort

Quick sort:先全局有序再局部有序

Merge sort: 先局部有序再全局有序

1>都是Divided conquer算法

2> Space complexity: O(1) VS O(n)

3>Quick sort是不稳定排序，merge sort 是稳定排序

4> Quick sort 平均时间为O(nlogn), Merge sort最好最坏为O(nlogn)

Quick Sort:

/* This function takes mid element as pivot, places the pivot element at its
       correct position in sorted array, and places all smaller (smaller than pivot)
       to left of pivot and all greater elements to right of pivot */
    public static int partition(int[] arr,int left,int right)
    {
        int i=left;
        int j=right;
        int temp;
        int pivot= arr[(left+right)/2];


        while(i<=j)
        {
            while(arr[i]<pivot)
                i++;
            while(arr[j]>pivot)
                j--;

            if(i<=j)
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                i++;
                j--;
            }
        }

        return i;

    }

    public static void quickSort(int[] arr,int left,int right)
    {
        int index=partition(arr,left,right);

        if(left<index-1)
        {
            quickSort(arr,left,index-1);
        }
        if(right>index)
        {
            quickSort(arr,index,right);
        }
    }

partition 函数模板：

int partition(int[] nums, int lo, int hi) {
    if (lo == hi) return lo;
    // 将 nums[lo] 作为默认分界点 pivot
    int pivot = nums[lo];
    // j = hi + 1 因为 while 中会先执行 --
    int i = lo, j = hi + 1;
    while (true) {
        // 保证 nums[lo..i] 都小于 pivot
        while (nums[++i] < pivot) {
            if (i == hi) break;
        }
        // 保证 nums[j..hi] 都大于 pivot
        while (nums[--j] > pivot) {
            if (j == lo) break;
        }
        if (i >= j) break;
        // 如果走到这里，一定有：
        // nums[i] > pivot && nums[j] < pivot
        // 所以需要交换 nums[i] 和 nums[j]，
        // 保证 nums[lo..i] < pivot < nums[j..hi]
        swap(nums, i, j);
    }
    // 将 pivot 值交换到正确的位置
    swap(nums, j, lo);
    // 现在 nums[lo..j-1] < nums[j] < nums[j+1..hi]
    return j;
}

// 交换数组中的两个元素
void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

Merge Sort:

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
    static void merge(int[] arr,int l,int m,int r)
    {
        int i,j,k;
        int n1=m-l+1;
        int n2=r-m;


        /* create temp arrays */
        int[] L=new int[n1];
        int[] R=new int[n2];


        /* Copy data to temp arrays L[] and R[] */
        for(i=0;i<n1;i++)
        {
            L[i]=arr[l+i];
        }
        for(j=0;j<n2;j++)
        {
            R[j]=arr[m+1+j];
        }


        /* Merge the temp arrays back into arr[l..r]*/
        i=0;
        j=0;
        k=l;



        while(i<n1 && j<n2)
        {
            if(L[i]<=R[j])
            {
                arr[k]=L[i];
                i++;
            }
            else
            {
                arr[k]=R[j];
                j++;
            }
            k++;
        }
        /* Copy the remaining elements of L[], if there are any */
        while(i<n1)
        {
            arr[k]=L[i];
            i++;
            k++;
        }
        /* Copy the remaining elements of R[], if there are any */
        while(j<n2)
        {
            arr[k]=R[j];
            j++;
            k++;
        }


    }



    /* l is for left index and r is right index of the sub-array
      of arr to be sorted */
    static void mergesort(int[] arr,int l,int r)
    {
        if(l<r)
        {
            int m=(l+r)/2;
            mergesort(arr,l,m);
            mergesort(arr,m+1,r);
            merge(arr,l,m,r);
        }
    }