归并排序和快速排序的相同点和不同点（JAVA）

首先我们贴出来快速排序的代码

public class QuickSort {
	public int QuickSort(int[] a, int left, int right) {
		int temp = a[left];
		while(left < right)
		{
			while(left < right && a[right] >= temp)
			{
				right--;
			}
			if(left < right && a[right] < temp)
			{
				a[left] = a[right];
			}
			while(left < right && a[left] <= temp)
			{
				left++;
			}
			if(left < right && a[left] > temp)
			{
				a[right] = a[left];
			}
		}
		a[left] = temp;
		
		return left;
	}
	public void partion(int a[], int left, int right) {
		int num;
		if(left < right)
		{
			num = QuickSort(a, left, right);
			partion(a, left, num-1);
			partion(a, num + 1, right);
		}
	}
	public static void main(String[] args) {
		int a[] = {7, 2, 3, 8, 9, 6, 5, 1, 4};
		QuickSort test = new QuickSort();
		test.partion(a, 0, 8);
		for(int i = 0; i < 9; i++)
		{
			System.out.print(a[i]);
		}

	}
	
}

其次我们贴出归并排序的代码 

public class MergeSort {
	public void merge(int[] a, int left, int right) {
		if(left + 1< right) {
			int mid = (left + right) / 2;
			merge(a, left, mid);
			merge(a, mid, right);
			mergesort(a, left, mid, right);
		}
	}
	public void mergesort(int[] a, int left, int mid, int right) {
		int testl[] = new int[10000];
		int testr[] = new int[10000];
		int n1 = mid - left;
		int n2 = right - mid;
		testl[n1] = Integer.MAX_VALUE;
		testr[n2] = Integer.MAX_VALUE;
		int num = right - left;
		for(int i = 0; i < n1; i++)	testl[i] = a[left + i];
		for(int i = 0; i < n2; i++)	testr[i] = a[mid + i];
		int i = 0;
		int j = 0;
		for(int k = left; k < right; k++)
		{
			if(testl[i] < testr[j])
			{
				a[k] = testl[i];
				i++;
			}
				
			else
			{
				a[k] = testr[j];
				j++;
			}		
		}
	}
	public static void main(String[] args) {
		int[] a = {7, 2, 3, 8, 9, 6, 5, 1, 4};
		MergeSort test = new MergeSort();
		test.merge(a, 0, 9);
		for(int i = 0; i < 9; i++)
			System.out.print(a[i]);
	}
}

阅读完这两个代码，我们可以发现这两种排序都存在递归，而差别则在于它们递归的顺序。

归并排序：是先递归在排序

快速排序：是先找到分割的标志来将数组进行大致的切割（标志的左边都是小于标志的值，右边都是大于标志的值），然后再进行递归

当然这两种排序的时间复杂度和空间复杂度也不相同

快速排序的时间复杂度为最快情况为O(nlogn),最坏情况为O(n*n),小计快速排序是冒泡排序的思想改进，快速排序是从整体到部分再到个体，而冒泡排序则是一个个个体去比较，所以快速排序更为高级，当然因为追求过快，而导致不稳定，最坏情况的出发条件则是一个有序的数组，且取得标志为数组的最大值或者最小值，这种情况也可能会导致栈递归过深，导致栈溢出，空间复杂度O(logn)；

归并排序的时间复杂度最好情况最坏情况都为O(nlogn)。空间复杂度O(n)。