排序算法核心内容

排序算法复习

前言

首先复习效率，其次复习常见的三种面试代码，最后粘贴一下之前做了好久的效率分析图，（话说当初那个文档做了20个小时，都怪自己反应有些慢呢）。 

效率分析

三种核心算法（一般写代码）

快速排序 

public static void quickSort(int[] array) {
		quickSortInternal(array,0,array.length-1);
	}
	private static void quickSortInternal(int[] array, int left, int right) {
		// TODO 自动生成的方法存根
		if(left>=right) return;
		int i=left,j=right;
		int pivot=partition(array,left,right);
		quickSortInternal(array,left,pivot-1);
		quickSortInternal(array,pivot+1,right);
	}
	private static int partition(int[] array, int left, int right) {
		// TODO 自动生成的方法存根
		int i=left,j=right;
		int pivot=left;
		while(i<j) {
			while(i<j&&array[j]>=array[pivot]) {
				j--;
			}
			while(i<j&&array[i]<=array[pivot]) {
				i++;
			}
			swap(array,i,j);
		}
		swap(array,i,left);
		return i;
	}

堆排序

        public  void heapSort(int[] array) {
		createHeap(array);
		for(int i=0;i<array.length-1;i++) {
			swap(array,array.length-1-i,0);
			shiftDown(array,array.length-1-i,0);
		}
	}
	private static void createHeap(int[] array) {
		for (int i = (array.length - 1) / 2; i >= 0; i--) {
			shiftDown(array, array.length, i);
		}
	}
	public static void shiftDown(int[] array, int size, int index) {
		int left=2*index+1;
		while(left<size) {
			int right=left+1;
			int max=left;
			//存在条件下
			if(right<=size-1)
				max=array[left]>=array[right]?left:right;
			if(array[index]>=array[max]) {
				return;
			}
			//需要调整
			swap(array,index,max);
			index=max;
			left=2*index+1;
		}
	}

 归并排序

public static void mergeSort(int[] array) {
		mergeSortInternal(array,0,array.length);
	}
	private static void mergeSortInternal(int[] array, int low, int high) {
		// TODO 自动生成的方法存根
		if(low>=high-1) return;
		int mid=(low+high)/2;
		mergeSortInternal(array,low,mid);
		mergeSortInternal(array,mid,high);
		merge(array,low,mid,high);
	}
	private static void merge(int[] array, int low, int mid, int high) {
		// TODO 自动生成的方法存根
		int[] extra=new int[high-low];
		int i=low,j=mid;
		int k=0;
		//核心代码
		while(i<mid&&j<high) {
			extra[k++]=array[i]<=array[j]?array[i++]:array[j++];
		}
		//剩余元素归位
		while(i<mid) {
			extra[k++]=array[i++];
		}
		while(j<high) {
			extra[k++]=array[j++];
		}
		//搬回原位置
		System.arraycopy(extra, 0, array, low, extra.length);
	}

实验检验

结论：排序混乱（不要求稳定性）的时候，快速排序和堆排序排名第一档次，数据量小的时候插入排序还是不错的哦，果然冒泡算法还是很弟弟啊，被誉为只能出现在“教科书上的代码”。数据量特别大的时候，外部排序中使用归并排序的较多，其核心思想就是排序两个有序的数组。

老师有话说

学校上实验课的时候，老师就强调面试的时候，听到排序算法，一定要回答分为内部排序和外部排序，内部排序常见的7中算法中，数据量大时，……，数据量小时，……，……算法比较稳定，时间复杂度分别是那么，特别强调了要说外部排序，基于败者树的64路归并啦什么的都可以说，嗯~ o(*￣▽￣*)o，听起来还听高大上的，当时好佩服啊老师说了一串一串的，所以加油吧。

SP：特别要注意的是组织语言别紧张哦