整一下老早就听说过的，但是却没有深入了解过的排序算法。
首先，排序算法分为两大类：
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
给一张图，内容是十大经典排序算法的时间复杂度，空间复杂度以及稳定性。
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
image
快速排序的基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。
排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
具体解析参考如下代码（从小到大）：
public static void main() {
// 对0->len-1进行排序
qSS(arr,0,arr.length-1);
}
private void qSS(int[] arr,int left,int right) {
// 左边界需要小于右边届
if (left<right) {
// 获取排序完成的分界值所在的位置
int partitionIndex = qS(arr,left,right);
// 对分界值左边的内容进行排序
qSS(arr,0,partitionIndex-1);
// 对分界值右边的内容进行排序
qSS(arr,partitionIndex+1,right);
}
}
// 单次排序
private int qS(int[] arr,int left,int right) {
// 取left作为分界值，index为交换坐标，index初始化为left右边的第一个值
// ex: {6[left],5[index],4,9,8,7,3,2,1};
int index = left +1;
// 从i=index开始循环
for (int i=index;i<=right;i++) {
// 如果arr[i]小于arr[left]，将arr[i]与arr[index]交换
// 这样比left小的值将移动到left的右边
// 同时index向右移动一位，此时index左侧的内容都应该<=arr[left]
if (arr[i]<arr[left]) {
swap(arr,i,index);
index++;
}
}
// 以上全部交换完毕之后，将left与index-1交换
// 得到以index-1位置为分界的数组
// {6[left],5,4,3,2,1,9[index],8,7} ==>
// {1[left],5,4,3,2,6,9[index],8,7}
swap(arr, left,index-1);
return index-1;
}
private void swap(int[] arr,int x,int y) {
if (arr[x]==arr[y]) return;
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
写法二（从大到小）：
private void quickSort(int[] arr,int left,int right) {
if (left>right) {
return;
}
// 左边界
int i = left;
// 右边界
int j = right;
// 以左边界为届值
int cur = arr[left];
// 循环
while (i<j) {
// 从右边开始，找到一个大于cur的值停下来
while (cur<=arr[j] && i<j) {
j--;
}
// 从左边开始，找到一个小于cur的值停下来
while (cur>=arr[i] && i<j) {
i++;
}
// 满足条件则交换两值
if (i<j) {
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
// ex : {6[cur],5[i],4,9,8,7,3,2,1[j]} ==>
// ex : {6[cur],5[i],4,9,8,7[j],3,2,1} ==>
// ex : {6[cur],7[i],4,9,8,5[j],3,2,1}
}
// ex : {6[cur],7,8,9[i][j],4,5,3,2,1}
// 将arr[i]与arr[left]互换
arr[left] = arr[i];
// cur就是left的temp值
arr[i] = cur;
// 排序左半部分
quickSort(arr,left,j-1);
// 排序右半部分
quickSort(arr,j+1,right);
}
上面源码的细节都添加注释，接下来是快速排序的运用：
数组中的第K个最大元素，话不多说直接上源码。
public int findKthLargest(int[] nums, int k) {
// 左边界
int left = 0 ;
// 右边届
int right = nums.length-1;
// 总长度(n-k所在的位置即为第K大)
int n = nums.length;
while (true){
// pos依旧是基准位置，进行快排(使用方法二)
int pos = quickSort(nums,left,right);
// 如果pos的位置刚刚好是n-k，直接返回
if (pos==n-k) {
return nums[pos];
// 如果pos在k右侧，则右边届移动到pos-1
} else if (pos>n-k) {
r = pos-1;
// 如果 pos在k左侧，则左边界移动到pos+1
} else {
l = pos+1;
}
}
}
