最糟糕的情况就是待排序列为需要排序方向的逆序。每次划分只得到一个比上一次划分少一个记录的子序列。这时快排退化为冒泡排序。时间复杂度为O(n^2)。
快排的平均复杂度为O(nlogn)，证明过程较长，直接贴个链接吧。
空间复杂度
被快速排序所使用的空间，根据上面我们实现的代码来看，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生 o(logn)嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(logn)次的嵌套递归调用，所以它需要O(logn)的空间。最坏情况下需要 O(n)次嵌套递归调用，因此需要O(n)的空间。
归并排序
归并是指将两个及以上的有序序列合并成一个有序序列。
归并排序步骤：
1.申请一个和待排序列长度相同的空间空间该空间用来存放合并后的序列
2.设定两个数为对数组中位置的指向，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择小的元素放入到合并空间，并移动被选择的数的指针到下一位置
4.重复步骤3直到某一指针到达指定的序列尾部
5.将另一序列剩下的所有元素直接复制到合并序列尾
代码
public static void mergeSort(int[] nums, int[] temp, int left, int right){
if(left<right){
int mid = (left+right)/2;
mergeSort(nums, temp,left,mid);
mergeSort(nums, temp,mid+1,right);
merge(nums,temp, mid, left, right);
}
}
public static void merge(int[] nums, int[] temp, int mid, int left, int right){
int i=left,j=mid+1,k=0;
while(i<=mid&&j<=right){
if(nums[i]<nums[j]){
temp[k++] = nums[i++];
}else {
temp[k++] = nums[j++];
}
}
while(i<=mid){
temp[k++] = nums[i++];
}
while(j<=right){
temp[k++] = nums[j++];
}
//将temp中的元素全部拷贝到原数组中
//这里必须将原来排好序的数组值复制回去
//否则后续的对比前面排序长的数组排序时会出错
//比如4 1 2 3 讲过排序后分为1 4 和2 3两组
//如果没有将值复制回去那么合并后将是2 3 4 1
k=0;
while(left<=right){
nums[left++] = temp[k++];
}
}
复杂度
归并排序是一种效率高且稳定的算法。但是却需要额外的空间。
归并排序的比较是分层次来归并的。第一次将序列分为两部分，第二次将第一次得到的两部分各自分为两部分。最后分割合并就类似一课二叉树。其平均时间复杂度为O(nlogn)。空间复杂度因为其需要额外长度为n的辅助空间，其空间复杂度为O(n)。
大数据量排序