快速排序
提示：这里可以添加本文要记录的大概内容：
例如：随着人工智能的不断发展，机器学习这门技术也越来越重要，很多人都开启了学习机器学习，本文就介绍了机器学习的基础内容。
提示：以下是本篇文章正文内容，下面案例可供参考
一、基本思想
以降序为例。
基本思想：通过一趟快速排序，将待排序的序列分割成两段相互独立的序列，其中左边的序列都比右边序列大。再分别对这两部分序列进行排序，则可实现整体有序。
具体实现：选择一个中间数，把大于中间数的元素放在其左边，小于中间数的放在其右边。（这一步完成后，实际上就确定了中间数排序后应该在的位置），然后再分别还没有排序的左边序列和右边序列进行排序。
中间数的选择：可以第一个数，最后一个数，中间的数等等。
我们举个例子：
个人是这样理解的，每一次在找到比中间数大（小）的元素时，把找到的数放在蓝色的框里（想象它被扣掉了，需要填数字进去），放好后，这个被扣掉的地方，变成了刚刚所选的大（小）数的那个地方。然后，我们需要从另一边找比中间数小（大）数来填这个空。反复操作，直到左右两边都已经判断完毕，当前的这个空，即为中间数应在的位置。至此完成一趟快速排序。
以上操作的是一趟排序，结果是确定了中间数的位置。其左右两边的序列还需进行排序，而我们只需要以同样的方式分别对其左右两边进行快速排序即可，直到左右两边都只有一个元素时，整个序列即为有序序列。
一趟快速排序代码：
int FastSort(int* arr,int low,int high){
//选择一个中间数，如果大于中间数，则放在左边，如果小于中间数则放在右边
//中间数和high位置上的数进行比较，如果high位置上的数比中间数小，则high--，比较下一个。
//直到比到比中间数大的时候 ，将这个大的数移到low的位置上，接下来low++，low位置上的数与中间数比较
//如果low位置上的数比中间数大，则low++,比较下一个，直到比到比中间数小的时候，将这个小的数放到high的位置上，high--
//重复以上步骤，直到low>=high,此时，中间数的正确位置为low,将中间数放在low位置上，完成一趟快速排序
//接着分别对中间数两边的元素以同样的方式进行快速排序。直到最后只剩下一个元素，排序完成。
int t=arr[low];
int i=low,j=high;
while(i<j){
while(i<j&&t>=arr[j]) j--;
arr[i]=arr[j];
while(i<j&&t<=arr[i]) i++;
arr[j]=arr[i];
}
arr[i]=t;
return i;
}
完整的快速排序代码：
void Sort(int* arr,int l,int r){
if(l>=r) return;
int index=FastSort(arr,l,r);
Sort(arr,l,index-1);
Sort(arr,index+1,r);
}
var foo = 'bar';
二、求第K大的数
知道了快速排序的原理后，我们怎么利用快速排序来求第K大的数？我们知道，一趟快速排序，确定了中间数在最终有序序列的所在位置，所以，如果我们对序列进行升序排序，那么排在第K个位置的是不是就是第K大的数呢？答案是的。
所以，我们只需要在快速排序时做一个简单的判断：判断当前这趟快速排序所确定的中间数的位置是不是k,
- 如果是，则说明当前这个中间数就是第K大的数；
- 如果当前这趟排序所确定的位置大于K，说明第K大的是在左边，只需对左边进行快速排序寻找；
- 如果当前这趟排序所确定的位置小于K，说明第K大的数在右边，需要对右边进行快速排序寻找。
当找到第K大的数后，结束操作。剩余元素可能是无序的，如果我们只需要找到第K大的数，做到这里就可以了。
求第K大的数的代码
void FastSort(int* arr,int low,int high,int k){
//int FastSort(int* arr,int low,int high){
//选择一个中间数，如果大于中间数，则放在左边，如果小于中间数则放在右边
//中间数和high位置上的数进行比较，如果high位置上的数比中间数小，则high--，比较下一个。
//直到比到比中间数大的时候 ，将这个大的数移到low的位置上，接下来low++，low位置上的数与中间数比较
//如果low位置上的数比中间数大，则low++,比较下一个，直到比到比中间数小的时候，将这个小的数放到high的位置上，high--
//重复以上步骤，直到low>=high,此时，中间数的正确位置为low,将中间数放在low位置上，完成一趟快速排序
//接着分别对中间数两边的元素以同样的方式进行快速排序。直到最后只剩下一个元素，排序完成。
int t=arr[low];
int i=low,j=high;
while(i<j){
while(i<j&&t>=arr[j]) j--;
arr[i]=arr[j];
while(i<j&&t<=arr[i]) i++;
arr[j]=arr[i];
}
arr[i]=t;
//return i;
if(i==k) return;
if(i>k) FastSort(arr,low,i-1,k);
else FastSort(arr,i+1,high,k);
}
//找出第k小的数
int findKth(int* a, int aLen,int n,int K) {
FastSort(a,0,aLen-1,K-1);
return a[K-1];
}
总结
一开始的时候，我是对序列进行降序来求第K大的数，发现第K个位置上不是第K大的，如果是降序排的话，第K大的数应该在aLen-K的位置上。编程路上，砥砺前行~