问题：遇到排序问题，使用下面的语句对pandas的某列进行排序时,发现根本没排序成功。

bada_air.sort_value(by='time',ascending=False)

解决方案：这里牵扯到很重要的参数inplace,默认的inplace设置是False,并没有对本体进行覆盖，所以解决方法有两个：

1.设置本体覆盖，令inplace=True

bada_air.sort_value(by='time',ascending=False,inplace=True)

2.设置传值覆盖

bada_air=bada_air.sort_value(by='time',ascending=False)

 

以前写过一次排序的程序，最近又讲了一次，瞬间无比的懂，所以写一个博客记录
快速排序的目的就是每一次都将比基准数大的所有数都放在基准数的右边，比基准数小的所有数都放在基准数的左边，然后递归左右，直到左右集合只有一个数或者没有数。
这里基准数取最左边的数.

首先模拟快速排序的过程：
4 6 7 1 2
第一步记录基准数key=4，同时i=0,j=4,这时可以认为4这里有一个坑（因为他的值已经被记住了）即 坑 6 7 1 2
第二步 从右开始向左找比key小的数（为什么是小，因为我们认为结果是从小到大，那么右边肯定是大的，如果你小了肯定不对），发现2比key小，所以将2填进坑
即 2 6 7 1 坑
第三步 从左边开始找比key大的数（左边应该是小的，如果大了你还是去右边吧）即 找到 6然后变成 2 坑 7 1 6 

第三步 从右边找比key小的数,变成2 1 7 坑 6
第四步 从左边找比key大的数变成 2 1 坑 7 6
此时左右相遇，所以退出循环，坑里面放key，此时21 4 7 6
经过上面的操作成功使key左边的数都比它小，右边的数都比它大
然后让（2 1）再次这样，（7 6）再次这样可以得到排序结果。
    这里要注意找的时候是不能含相等的，也就是只有找到比它小（或大）的数才填坑，因为如果相等就填坑会出现死循环！比如3 2 3 一开始  基准是3 从右边找找到小于等于3的，
变成 3 2 坑，然后从a[0]=3这个开始再找大于等于3的又找到3再交换 ，又变成 坑 2 3,死循环！
     接下来讲一下快速排序为什么快！（这里主要是和O（n^2)的冒泡和选择）
    我们可以想一个天平问题，有12个小球，有1个天平，称多少次可以称出那个较重（或轻）的小球，3次！
    不用构造解，我们可以这样想，12个小球，有重有轻一共24个状态，然后天平自身有3种状态，（轻，相等，重）即是求3 ^k>=24可以解得k=3，这是最少个数，如果不比这么多，总是会有小球无法判断状态。
    同理n个数进行全排列，一共有n!的情况，那么基于选择的排序每一次都是比较左右两边，有两种情况（大或者小，如果相等可以归结于大或者小中位置不变的那个），
所以2^k>=n!即得k>=log  n! 这是基于选择的排序的下限，而这个结果接近于快速排序的O（nlog n)
  我们可以这么想，我们10个数猜数字，一定是用折半的方法，这样次数最少，因为左右两边等可能，所以虽然数学证明很复杂，但我们能直观地感到左右两边等可能时效率最高，而 1，2，3，4这样找下去效率最低，而这不就是10个数排序的冒泡吗，每一次找出最小的数，次小的....而对于快速排序如果左右两边等量比如（2 1 ）3 （5 4）那么效率最高，如果左边少一点，效率低一点，最低就是一边为空，比如3（5 4）那最低不就是冒泡吗，每一次找出最小的数~~可以得出快速排序确实是快
   下面贴代码：

#include <stdio.h>
void quicksort(int a[],int left,int right);
 int main()
 {

     int i,j,n;
     int b;
     int a[100];
     printf("请输入数组长度\n");
     scanf("%d",&n);
     printf("请输入数组元素\n");
     for (i=0;i<n;i++)
     scanf("%d",&a[i]);
     quicksort(a,0,n-1);
     for (i=0;i<n;i++)
     printf("%d ",a[i]);
     printf("\n");
}
void quicksort(int a[],int left,int right)
{

    int i,j,key,low,high;//key是基准
    low=left;
    high=right;
    key=a[left];//以最左边的数为基准
    if (left<right)//如果传递进来的还有元素
    {
       while (low<high)
       {

           while ((low<high)&&(a[high]>=key))//找到小于基准的数(为什么右边先动，如果第一次左边先动找到了大于key的位置，那它应该放在右边的哪里呢，显然不知道，而右边先动，一旦找到小于key的就和基准换位置，反正最后还要将基准塞进一个新位置）
           {
               high--;
           }
          a[low]=a[high];//小于的那个数应该是属于基准数左边的（如果第一次循环就正好代替了基准数，这也是使用key保留的原因）
          while ((low<high)&&(a[low]<=key))//这里说明为什么要含等号，因为我们假设3，2，3.如果没有等号，第一次循坏跳过，第二次循环也跳过，然而low仍小于high，死循环！（而加了=,第一次就是2，此时2,2,3,第二次也是2,此时2，2，3，最后替换key，得2,3,3!
          {
              low++;//找到大于基准的数
          }
          a[high]=a[low];//他应该是属于右边的，还记得刚才high的值小于key被保存在左边了吗，现在正好把原来小的值覆盖掉换成大于基准的数
       }//以上就是将所有大于key的数放在右边，小于key的数放在左边
       a[low]=key;//最后一定是剩下key的值没有
          quicksort(a,left,low-1);
          quicksort(a,low+1,right);
    }
}


每一次都这样肯定比较烦，所以c++有sort函数可以直接用（c语言也有，太麻烦了），包含<iostream>和<algorithm>如果习惯c语言可再用<cstdio>

  用法是从小到大直接   sort(a,a+n);其中a是数组名（其实是首地址，你也可以从a+1,开始）,n是比较多少个数,
  如果从大到小需要     sort(a,a+n,cmp);同时写int cmp(int a,int b){return a>b;}
  如果是结构体 需要   sort(a,a+n,cmp2)写 int cmp(student a,student b){return a.score>b.score)假设student里根据成绩从大到小排序
poj3664
http://poj.org/problem?id=3664


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct node
{
    int a;
    int b;
    int index;
}node;
int  cmp(node x,node y)
{
    return x.a>y.a;
}
int  cmp2(node x,node y)
{
    return x.b>y.b;
}
  int main()
  {
    int n,k,i;
    node t[50005];
    while(scanf("%d%d",&n,&k)==2)
    {
        memset(t,0,sizeof(t));
        for (i=0;i<n;i++)
        {
        scanf("%d%d",&t[i].a,&t[i].b);
        t[i].index=i+1;
        }
        sort(t,t+n,cmp); //第一次是根据a来判断
        sort(t,t+k,cmp2);
        printf("%d\n",t[0].index);
    }
    return 0;

  }
Poj2388

http://poj.org/problem?id=2388


#include <stdio.h>
void quicksort(int a[],int left,int right);
 int main()
 {

     int i,j,n;
     int b;
     int a[10005];
     while(scanf("%d",&n)==1)
     {
     for (i=0;i<n;i++)
     scanf("%d",&a[i]);
     quicksort(a,0,n-1);
     printf("%d\n",a[n/2]);
     }
}
void quicksort(int a[],int left,int right)
{

    int i,j,key,low,high;//key是基准
    low=left;
    high=right;
    key=a[left];//以最左边的数为基准
    if (left<right)//如果传递进来的还有元素
    {
       while (low<high)
       {

           while ((low<high)&&(a[high]>=key))//找到小于基准的数(为什么右边先动，如果第一次左边先动找到了大于key的位置，那它应该放在右边的哪里呢，显然不知道，而右边先动，一旦找到小于key的就和基准换位置，反正最后还要将基准塞进一个新位置）
           {
               high--;
           }
          a[low]=a[high];//小于的那个数应该是属于基准数左边的（如果第一次循环就正好代替了基准数，这也是使用key保留的原因）
          while ((low<high)&&(a[low]<=key))//这里说明为什么要含等号，因为我们假设3，2，3.如果没有等号，第一次循坏跳过，第二次循环也跳过，然而low仍小于high，死循环！（而加了=,第一次就是2，此时2,2,3,第二次也是2,此时2，2，3，最后替换key，得2,3,3!
          {
              low++;//找到大于基准的数
          }
          a[high]=a[low];//他应该是属于右边的，还记得刚才high的值小于key被保存在左边了吗，现在正好把原来小的值覆盖掉换成大于基准的数
       }//以上就是将所有大于key的数放在右边，小于key的数放在左边
       a[low]=key;//最后一定是剩下key的值没有
          quicksort(a,left,low-1);
          quicksort(a,low+1,right);
    }
}



各拿sort和手打的快排验证了一下

二叉排序树是基于二分查找步骤生成的二叉树。

设二叉排序树的高度为h，共有n个结点

有如下性质：

1.前h-1层结点全部占满（即为满二叉树）

2.最后一层结点可以通过平移使得整个树转化成完全二叉树
思路：

首先求前h-1层的对比次数

之后求最后一层的对比次数
公式为：



下面给出证明过程：

一、简单选择排序。

1、介绍。

        在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按第一条记录最小，之后的记录从小到大顺序排列，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。

        简单选择排序是不稳定排序，不需要额外内存，空间复杂度O(1)。时间复杂度，最佳情况：O(n^2)  最差情况：O(n^2)  平均情况：O(n^2)。

2、步骤。

    (1)初始状态：无序区为R[1..n]，有序区为空；

    (2)第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

    (3)n-1趟结束，数组有序化了。

3、代码。

public static void main(String[] args) {
        System.out.println("------开始------");
        //生成生成两份一模一样的随机数组，其中一组用系统自带的方法进行排序，到时候进行验证。
        final int number = 100000;
        int[] sortArray = new int[number];
        int[] sortArrayCopy = new int[number];
        for (int i = 0; i < sortArray.length; i++) {
            sortArray[i] = (int) (Math.random() * number);
        }
        System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);//数组复制
        Arrays.sort(sortArrayCopy);

        //开始排序
        long startTime = System.currentTimeMillis();
        selectSort(sortArray);//简单选择排序
        System.out.println("花费时间：" + (System.currentTimeMillis() - startTime));

        //跟系统排序之后数组进行比较，查看是否排序成功。
        if (Arrays.equals(sortArray, sortArrayCopy)) {
            System.out.println("排序成功");
        } else {
            System.out.println("排序失败");
        }
        System.out.println("------结束------");
    }

//简单选择排序 最佳情况：T(n) = O(n2)  最差情况：T(n) = O(n2)  平均情况：T(n) = O(n2)
private static void selectSort(int[] array) {
    for (int i = 0; i < array.length-1; i++) {//n-1轮  最后一个无序排序
        int minIndex=i;
        for (int j=i+1;j<array.length;j++){
            if (array[j]<array[minIndex]){
                minIndex=j;
            }
        }
        //交换位置

        if (i != minIndex) {//感谢用户：EthanZzzz... 的提醒，加上这个判断
            int flag = array[minIndex];
            array[minIndex] = array[i];
            array[i] = flag;
        }
    }
}

4、结果。



二、堆排序

1、介绍。

        堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

       堆排序排序是不稳定排序，不需要额外内存，空间复杂度O(1)。时间复杂度，最佳情况：O(nlogn)  最差情况：O(nlogn)  平均情况：O(nlogn)。

2、步骤。

    (1)最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。

    (2)创建最大堆（Build Max Heap）：将堆中的所有数据重新排序。

    (3)堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

3、代码。

public static void main(String[] args) {
        System.out.println("------开始------");
        //生成生成两份一模一样的随机数组，其中一组用系统自带的方法进行排序，到时候进行验证。
        final int number = 15;//要满足条件：array.length==2^n-1
        int[] sortArray = new int[number];
        int[] sortArrayCopy = new int[number];
        for (int i = 0; i < sortArray.length; i++) {
            sortArray[i] = (int) (Math.random() * number);
        }
        System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);//数组复制
        Arrays.sort(sortArrayCopy);

        //开始排序
        long startTime = System.currentTimeMillis();
        heapSort(sortArray);//堆排序
        System.out.println("花费时间：" + (System.currentTimeMillis() - startTime));

        //跟系统排序之后数组进行比较，查看是否排序成功。
        if (Arrays.equals(sortArray, sortArrayCopy)) {
            System.out.println("排序成功");
        } else {
            System.out.println("排序失败");
        }
        System.out.println("------结束------");
    }

    //堆排序，要满足条件：array.length==2^n-1
    private static void heapSort(int[] array) {
        System.out.println("初始状态：");
        printHeap(array);
        //第一次初始化最大堆
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            heap(array, array.length, i);
        }
        System.out.println("第1次堆的调整：");
        printHeap(array);
        //循环将堆首位（最大值）与末位交换，然后在重新调整最大堆
        int len = array.length;
        while (len > 0) {
            len--;
            //将最后一个未排序的跟第一个进行交换
            int flag = array[0];
            array[0] = array[len];
            array[len] = flag;
            //
            System.out.println(String.format("第%d次堆的调整：", array.length - len + 1));
            printHeap(array);
            heap(array, len, 0);
        }
    }

    private static void heap(int[] array, int len, int i) {
        int maxIndex = i, left = i * 2 + 1, right = i * 2 + 2;
        //如果有左子树，且左子树大于父节点，则将最大指针指向左子树
        if (left < len && array[left] > array[maxIndex]) {
            maxIndex = left;
        }
        //如果有右子树，且右子树大于父节点或者大于左子树（左子树已经比父节点大的情况），则将最大指针指向右子树
        if (right < len && array[right] > array[maxIndex]) {
            maxIndex = right;
        }
        //如果父节点不是最大值
        if (maxIndex != i) {
            //交换array[maxIndex]和array[i],即将父节点与最大值交换
            int flag = array[maxIndex];
            array[maxIndex] = array[i];
            array[i] = flag;
            //递归调整与父节点交换的位置
            heap(array, len, maxIndex);
        }
    }

4、结果（直接给打印的日志）。

                ------开始------

                初始状态：

                               14               

                        5               6       

                   11       1       0       9   

                  3   7   0   2   0   2  13  10 

                第1次堆的调整：

                               14               

                       11              13       

                    7       2       2      10   

                  3   5   0   1   0   0   9   6 

                第2次堆的调整：

                                6               

                       11              13       

                    7       2       2      10   

                  3   5   0   1   0   0   9  14 

                第3次堆的调整：

                                6               

                       11              10       

                    7       2       2       9   

                  3   5   0   1   0   0  13  14 

                第4次堆的调整：

                                0               

                        7              10       

                    6       2       2       9   

                  3   5   0   1   0  11  13  14 

                第5次堆的调整：

                                0               

                        7               9       

                    6       2       2       0   

                  3   5   0   1  10  11  13  14 

                第6次堆的调整：

                                1               

                        7               2       

                    6       2       0       0   

                  3   5   0   9  10  11  13  14 

                第7次堆的调整：

                                0               

                        6               2       

                    5       2       0       0   

                  3   1   7   9  10  11  13  14 

                第8次堆的调整：

                                1               

                        5               2       

                    3       2       0       0   

                  0   6   7   9  10  11  13  14 

                第9次堆的调整：

                                0               

                        3               2       

                    1       2       0       0   

                  5   6   7   9  10  11  13  14 

                第10次堆的调整：

                                0               

                        2               2       

                    1       0       0       3   

                  5   6   7   9  10  11  13  14 

                第11次堆的调整：

                                0               

                        1               2       

                    0       0       2       3   

                  5   6   7   9  10  11  13  14 

                第12次堆的调整：

                                0               

                        1               0       

                    0       2       2       3   

                  5   6   7   9  10  11  13  14 

                第13次堆的调整：

                                0               

                        0               0       

                    1       2       2       3   

                  5   6   7   9  10  11  13  14 

                第14次堆的调整：

                                0               

                        0               0       

                    1       2       2       3   

                  5   6   7   9  10  11  13  14 

                第15次堆的调整：

                                0               

                        0               0       

                    1       2       2       3   

                  5   6   7   9  10  11  13  14 

                第16次堆的调整：

                                0               

                        0               0       

                    1       2       2       3   

                  5   6   7   9  10  11  13  14 

                花费时间：188

                排序成功

                ------结束------

5、结果。将main方法中的number改成131071，即2^17-1。并将多余的打印日志注释掉，因为打印太多日志会影响测试的结果。