排序

1 快速排序

以a[r]为枢纽，i指针遍历数组，j指针之后的元素都是比a[r]小的元素。

void qsort(int A[],int l,int r){
    int i,j; 
    if(l<r){  //边界检查
        for(i=l,j=l;i<=r;i++) {
            if(A[i]<=A[r]) // i指针找比枢纽小的
                swap(A[i],A[j++]); //找到一对就交换
         }
        j--; //最后会交换到A[r],j++，所以需要j--
        qsort(A,l,j-1);
        qsort(A,j+1,r);
    }
}

或者

void qsort(int A[],int l,int r){
    int i,j;
    if(l<r){  //枢纽为最后一个元素
        for(i=l,j=l;i<r;i++) {
            if(A[i]<=A[r]) // i指针找比枢纽小的
                swap(A[i],A[j++]); //找到一对就交换
         }
        swap(A[r],A[j]); //最后交换A[r]和A[j]
        qsort(A,l,j-1);
        qsort(A,j+1,r);
    }
}

应用：找数组第k小元素 /前k小元素（循环）

    int kElement(int k, int nums[]) {
        int l=0,r=nums.size()-1;
        if(r<0 || k<=0 || k>r+1) return -1;

        int i,j;
        while(l<=r){
                for(i=l,j=l;i<r;i++){
                    if(nums[i]<=nums[r])
                        swap(nums[i],nums[j++]);
                }
                swap(nums[j],nums[r]);

                if(j==k-1)
                    return j;
                else if(j>k-1)
                    r=j-1;
                else
                    l=j+1;
        }
    }

2 归并排序

递归，前半部分排序，后半部分排序，归并一起。

void mergesort(int a[],int l,int r){
    if(l<r){
        int m=(l+r)/2;     //分成两段
        mergesort(a,l,m);  //前半段排序
        mergesort(a,m+1,r);//后半段排序
        merge(a,l,m,r);    //两段归并
    }
}

void merge(int a[],int l,int m,int r){
    vector<int> temp;
    int i=l,j=m+1;

    while(i<=m && j<=r){
        if(a[i]<a[j])
            temp.push_back(a[i++]);
        else
            temp.push_back(a[j++]);
    }

    while(i<=m)         //两个while，只有一个会执行
        temp.push_back(a[i++]);
    while(j<=r)
        temp.push_back(a[j++]);

    for(i=l;i<=r;i++)
        a[i]=temp[i-l]; //复制回去，注意数组下标
}

3 堆排序

3.1 堆的存储

因为堆是一个完全二叉树，所以用数组来存储。
a[i]的左右子节点分别为：a[2i+1]，a[2i+2]。
a[i]的父节点为：a[(i-1)/2]。
所以最后一个有子节点的节点为a[n/2-1]。
从小到大排，需要大根堆，不断把堆顶放在数组后边。

3.2 堆顶的调整

如果一个堆的堆顶被另一个元素替换，该元素需要不断向下调整。

3.3 堆排序

1.初始化堆: 从下 (最后一个有子节点的节点a[n/2-1]) 往上 (a[0])，对每一个节点调整，得到一个大根堆。
2.维护堆：输出堆顶，用最后一个元素替换堆顶（其实是堆顶和最后一个元素交换）；堆长度-1，调整堆顶；重复此步骤。

void fixdown(int a[],int n,int i){
    int j=2*i+1;
    while(j<n){ //从上往下调整，结束的条件:无孩子||该节点比孩子节点大
        if(j+1<n && a[j+1]>a[j])
            j+=1;
        if(a[i]<a[j]){
            swap(a[i],a[j]);
            i=j;
            j=2*i+1;
        }
        else
            break;
    }
}

void Heapsort(int a[],int n){
    for(int i=n/2-1;i>=0;i--){ //初始化对，从下往上
        fixdown(a,n,i);
    }
    for(int i=n-1;i>=1;i--){  //当前最大值(堆顶)放最后，调整堆顶
        swap(a[0],a[i]); //代表要放的位置，也代表交换后数组长度
        fixdown(a,i,0);
    }
}

3.4 插入

在堆的最后插入一个元素，并调整堆。
将该元素不断向上调整。

void InsertHeapUp(int a[],int value,int n){ 
    int i=n;
    a[i]=value; //把value插在最后  
    int j=(i-1)/2; //a[i]父节点

    while(j>=0){  //终止条件：a[i]没有父节点 || a[i]<父节点
        if(a[i]<a[j]) //a[i]<父节点，终止
            break;
        else{
            swap(a[i],a[j]);//否则，与父节点交换，继续向上调整
            i=j;
            j=(i-1)/2;
        }
    }
}

4 冒泡排序

4.1 普通冒泡排序

第一趟，j=[0,...n-2]，把最大值放在a[n-1];
第二趟，j=[0,...n-3]，把次大值放在a[n-2]; ...

void bubbleSort(vector<int>& a, int n) {
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n - 1 - i; j++) {
            if (a[j]>a[j + 1])
                swap(a[j], a[j + 1]);
        }
    }
}

4.2 优化冒泡排序

1，某一趟若未进行过任何交换，则排序结束

void bubbleSort2(vector<int>& a, int n) {

    for (int i = 0; i<n; i++) {
        bool flag = false;
        for (int j = 0; j<n - 1 - i; j++) {
            if (a[j]>a[j + 1]) {
                swap(a[j], a[j + 1]);
                flag = true; //表示交换过
            }
        }
        if (flag == false) break; //这一趟未交换过
    }
}

2，记录上一趟最后交换的位置t，t后面的数未进行交换，即有序，这一趟只需对t前面的数排序。

void bubbleSort3(vector<int>& a, int n) {
    int lastSwap, lastSwapTemp = n - 1;
    //lastSwap代表数组尾部，lastSwapTemp代表最后一次交换的位置
    for (int i = 0; i<n; i++) { 
        lastSwap = lastSwapTemp;
        for (int j = 0; j<lastSwap; j++) { //从0到上一次最后交换的位置
            if (a[j]>a[j + 1]) {
                swap(a[j], a[j + 1]);
                lastSwapTemp = j; 
            }
        }
        if (lastSwap == lastSwapTemp) break; //这一趟未交换过
    }
}

5 插入排序

void insertsort(vector<int>& a,int n){
    for(int i=1;i<n;i++)
        for(int j=i;j-1>=0 && a[j-1]>a[j];j--)
            swap(a[j],a[j-1]);
}