时间复杂度为O(nlogn)的两种排序算法

1.归并排序

归并排序的核心思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大的问题也就解决了。

public class MergeSort {public static void main(String[] args) {int[] arr = new int[] {7,4,2,8,9,5};mergeSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}/*** 归并排序* 原地排序：否 * 稳定排序：是* 空间复杂度：O(n)* 时间复杂度：最好O(nlogn)——最坏O(nlogn)——平均O(nlogn)* @param arr 要排序数组* @param start 数组起始位* @param last 数组结束位* @return*/public static int[] mergeSort(int[] arr,int start,int last) {//也可以是（start+last）/2,这样写是为了防止数组长度很大造成两个相加大于int范围，导致溢出int mid = (last-start)/2+start;if(start<last) {mergeSort(arr,start,mid);//左数组排序mergeSort(arr,mid+1,last);//右数组排序merge(arr,start,mid,last);//合并两数组}return arr;}//合并数组public static int[] merge(int arr[],int start,int mid,int last) {int i=start;//左边数组下标int j=mid+1;//右边数组下标int[] tempArr = new int[last-start+1];//定义临时数组int k=0;while(i<=mid && j<=last) {if(arr[i]<arr[j]) {tempArr[k++] = arr[i++];}else {tempArr[k++] = arr[j++];}}while(i<=mid) {//将左边剩余元素移入到临时数组中tempArr[k++]=arr[i++];}while(j<=last) {//将右边剩余元素移入到临时数组中tempArr[k++]=arr[j++];}//把临时数组中的数据合并到新数组中for(int z=0;z<tempArr.length;z++) {arr[start+z] = tempArr[z];}return arr;}
}

2.快速排序

假设被排序的无序区间为[A[i],…,A[j]]

一、基准元素选取：选择其中的一个记录的关键字 v 作为基准元素（控制关键字）;
二、划分：通过基准元素 v 把无序区间 A[I]…A[j] 划分为左右两部分，使得左边的各记录的关键字都小于 v；右边的各记录的关键字都大于等于 v；（如何划分？）
三、递归求解：重复上面的一、二步骤，分别对左边和右边两部分递归进行快速排序。
四、组合：左、右两部分均有序，那么整个序列都有序。上面的第 三、四步不用多说，主要是第一步怎么选取关键字，从而实现第二步的划分？

划分的过程涉及到三个关键字：“基准元素”、“左游标”、“右游标”

基准元素：它是将数组划分为两个子数组的过程中，用于界定大小的值，以它为判断标准，将小于它的数组元素“划分”到一个“小数值的数组”中，而将大于它的数组元素“划分”到一个“大数值的数组”中，这样，我们就将数组分割为两个子数组，而其中一个子数组的元素恒小于另一个子数组里的元素。

左游标：它一开始指向待分割数组最左侧的数组元素，在排序的过程中，它将向右移动。找大于基准值的数。

右游标：它一开始指向待分割数组最右侧的数组元素，在排序的过程中，它将向左移动。找小于基准值的数。

**注意：**上面描述的基准元素/右游标/左游标都是针对单趟排序过程的， 也就是说，在整体排序过程的多趟排序中，各趟排序取得的基准元素/右游标/左游标一般都是不同的。对于基准元素的选取，原则上是任意的。但是一般我们选取数组中第一个元素为基准元素（假设数组是随机分布的）

/*** 快速排序* 原地排序：是* 稳定排序：否* 空间复杂度：O(1)* 时间复杂度：最好O(nlogn)——最坏O(n^2)——平均O(nlogn)*/
public class QuickSort {public static void main(String[] args) {int[] arr = new int[] {6,1,2,7,9,3,4,5,10,8};reQuickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}public static void swap(int[] arr,int i,int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void reQuickSort(int[] arr,int left,int right) {if(right<=left) {return;//终止递归}else {int partition = partitionIt(arr,left,right);reQuickSort(arr,left,partition-1);//基准元素左边元素进行排序reQuickSort(arr,partition+1,right);//基准元素右边元素进行排序}}public static int partitionIt(int[] arr,int left,int right) {//为什么 j加一个1，而i没有加1,是因为下面的循环判断是从‐‐j和++i开始的.//而基准元素选的array[left],即第一个元素，所以左游标从第二个元素开始比较int i=left;int j=right+1;int pivot = arr[left];// pivot 为选取的基准元素（头元素）while(true) {while(j>left&&arr[--j]>pivot) {}while(i<right&&arr[++i]<pivot) {}if(i>=j) {break;//左右游标相遇时候停止， 所以跳出外部while循环}else {swap(arr,i,j);//左右游标未相遇时停止, 交换各自所指元素，循环继续}}swap(arr,left,j);//基准元素和游标相遇时所指元素交换，为最后一次交换return j;//一趟排序完成， 返回基准元素位置(注意这里基准元素已经交换位置了)}
}