可以看到即使我们的数据上升到了十万级这个量级仍然二十几毫秒就排好序了，反而数据越有序排的越快，将我们的缺点变成了优点。

设置阈值

我们知道当我们的快速排序进行到后期的时候我们的待排序列已经基本上趋于有序了，我们还知道我们的插入排序是越有序，排的就越快，所以现在我们有一个想法，那就是设置一个阈值，当我们快速排序的待排序列低于这个阈值的时候，我们就采用我们的插入排序，这样也能进一步的减少时间。

代码

    public static void quick(int[] array,int left,int right) {if (left>right) {return;}//当我们的待排序个数小于1000的时候我们改为使用插入排序if (left+right+1<1000) {insertSort2(array, left, right);}//找到我们的中间基准int midIndex = findMidIndex(array,left,right);swap(array,left,midIndex);int pivot = partition(array,left,right);quick(array,left,pivot-1);quick(array,pivot+1,right);}//针对快速排序而制定的插入排序public static void insertSort2(int[] array,int left,int right) {for (int i = left+1; i <= right ; i++) {int temp = array[i];int j = i-1;for (; j >= left ; j--) {if (array[j] > temp) {array[j+1] = array[j];} else {break;}}array[j+1] = temp;}}

非递归法

其思想是先将我们的right和left放入栈中，

 接着出栈，分别将left和right赋值，然后进行排序返回我们的基准值的下标，然后分别将right和pivot+1还有pivot-1和left给压栈，接着重复当前的过程知道栈为空或者left>=right，当然在这期间也可以加入我们的优化。

代码

    //快速排序非递归public static void quickSort1(int[] array) {Stack stack = new Stack<>();int left = 0;int right = array.length-1;//先将最右和最左放入栈中stack.push(right);stack.push(left);while (!stack.empty()) {//弹出我们的左右两个位置的下标left = stack.pop();right = stack.pop();//当我们的左下标大于等于右下标的时候则跳过当前的排序if (left>=right) {continue;}int midIndex = findMidIndex(array,left,right);swap(array,left,midIndex);int pivot = partition(array,left,right);stack.push(right);stack.push(pivot+1);stack.push(pivot-1);stack.push(left);}}

性能

归并排序

原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

简单的来说就是将我们待排序的序列一次分成两份，然后将两份再分成四份···，最后分成一份只有一个元素，然后再合并合并的时候因为要合并的两个已经是有序了，所以就转换成合并两个有序数组的问题了。

代码

递归法

递归法写起来比较容易理解，就是将我们原数组分成两部分，我们取一个中间值，先递归左边的部分再递归右边的部分，最后写好我们的额合并方法就行了。

    //归并排序(递归)public static void mergeSort(int[] array) {mergeSortInternal(array,0, array.length-1);}private static void mergeSortInternal(int[] array,int low,int high) {if (low>=high) {return;}int mid = low + (high-low) / 2;mergeSortInternal(array,low,mid);mergeSortInternal(array,mid+1,high);//合并merge(array,low,mid,high);}//合并两个有序的数组private static void merge(int[] array,int low,int mid,int high) {int newLength = high - low + 1;int[] newArray = new int[newLength];int newArrayIndex = 0;//新数组的下标int start1 = low;//数组1的开始int end1 = mid;//数组1的结尾int start2 = mid+1;//数组2的开始int end2 = high;//数组2的结尾//循环直到其中一个数组遍历完while (start1<=end1 && start2<=end2) {if (array[start1]

    //归并排序(非递归)public static void mergeSort1(int[] array) {int gap = 1;//每组的元素个数while (gap< array.length) {for (int i = 0; i < array.length; i += gap*2) {int left = i;int mid = i + gap - 1;if (mid >= array.length) {mid = array.length-1;}int right = mid + gap;if (right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap *= 2;}}