一.排序算法介绍

1.1 快速排序

1. 核心思想：选择一个pivot，使得pivot左边的值都小于等于pivot，pivot右边的值都大于pivot，然后再对被划分的这两个区间再各自选择pivot进行类似的排序。直到划分下来的区间只剩下一个数为止。
2. pivot的选择可以是当前区间的第一个数或者最后一个数或者中间数。
3. 快速排序的实现是基于递归QuickSort(left, right);，递归结束条件是当前区间的left>=right（也即此时只剩下一个数或者没有数），进行返回；否则，对该区间进行分割排序，分割函数pivot=Partition(left, right); 然后递归QuickSort(left, pivot-1); QuickSot(pivot+1, right);
4. 对于Partition( left, right)函数的实现，这里的pivot可以是left，也可以是right，不过在函数内部要存储num[pivot]的值(要不然会被覆盖掉)，以pivot选择left为例，此次num[left]是先空出来的，因此，先从右往左找一个不比num[pivot]大的，放到num[left]中，此时num[right]的位置空出来，再从左往右找一个比num[pivot]大的数，放到num[right]的位置，依次类推。

5. 时间复杂度O(nlogn)

   int Parition(vector<int>& arr, int left, int right) {
    int tmp=arr[left];
    while(left<right) {
        while(left<right&&arr[right]>tmp)
            right--;
        arr[left]=arr[right];
        while(left<right&&arr[left]<=tmp)
            left++;
        arr[right]=arr[left];
    }
    arr[left]=tmp;
    return left;
   }
   void QuickSort(vector<int>& arr, int left, int right) {
    if (left>=right)
        return;
    int pivot=Parition(arr,left,right);
    QuickSort(arr,left,pivot-1);
    QuickSort(arr,pivot+1,right);
    return;
   }

6. 随机的pivot的实现：加上一个randomPartition，利用rand()函数随机选取该区间的pivot（int i=rand()%(right-left+1)+left），然后将其交换到该区间的开头或者结尾的位置，剩下的操作就是调用Partition()函数。

1.2 归并排序

https://www.cnblogs.com/chengxiao/p/6194356.html
利用归并的思想实现的排序方法

1.3 插入排序

基本思路：每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
具体实现上，当发现待排序的数据num需要插入到已经排好序的序列s的中间时，可以将num从s的最后序列往前比较，把num的值保存成tmp，空出num的位置，只要tmp比序列的后面的值大，则将序列后的值往后移一位，直到找到比tmp小的第一个数，则tmp插入到其的后面。

1.4 冒泡排序

原理：比较两个相邻的元素，将值大的元素交换到右边。
二重循环，外循环控制冒泡排序的次数，内层循环则实现每次遍历时的冒泡交换，依次比较两个相邻的元素，将较大的交换到右边，一次循环冒泡后，会把当前未排序的数列中最大的沉到最右边（也即已经排好序的数据的最左边），然后下次循环则是上一次未排序数列数-1的序列进行再一次冒泡。

1.5 选择排序

二重循环，外层循环是界限已排序和未排序的数据，内存循环则是去未排序的数据中寻找最小的数，也即每次内层循环都从待排序的数据中选择最小的数，与已排序元素的末尾的下一个数据进行交换。

1.6 堆排序

二.相关题目

215.数组中的第K个最大元素

题目链接

1. 暴力求解：冒泡排序（注意在len/2<k）时，可以反过来求第(n-k+1)小的元素
2. 基于快速排序的查找
3.