排序算法总结

ref：http://blog.csdn.net/u014682691/article/details/50787366

时间复杂度总结 补充

稳定性：
若数组中有两个相等的值，排序前后这两个值的相对位置保持不变，称为排序算法的稳定性。
http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html
A：选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n - 1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。不稳定，例如 4 4 2。
B：希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
C：堆的结构是节点i的孩子为2 * i和2 * i + 1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列，堆排序的过程是从第n / 2开始和其子节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1， n / 2 - 2， ... 1这些个父节点选择元素时，就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了，而第n / 2 - 1个父节点把后面一个相同的元素没 有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
D：归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

BFPRT算法：从某n个元素的序列中选出第k大（第k小）的元素 O(n)线性复杂度

堆排序：海量元素中找出topK的元素。可以维护一个大小为k的堆，时间复杂度为O(nlogk)。

关于选择第k小的数有许多方法

• 将n个数排序(比如快速排序或归并排序)，选取排序后的第k个数，时间复杂度为O(nlogn)。
• 维护一个k个元素的最大堆，存储当前遇到的最小的k个数，时间复杂度为O(nlogk)。这种方法同样适用于海量数据的处理。
• 部分的快速排序（快速选择算法），每次划分之后判断第k个数在左右哪个部分，然后递归对应的部分，平均时间复杂度为O(n)。但最坏情况下复杂度为O(n^2)。
• BFPRT算法，修改快速选择算法的主元选取规则，使用中位数的中位数的作为主元，最坏情况下时间复杂度为O(n)。

代码实现：

堆排序
http://blog.csdn.net/clam_clam/article/details/6799763
堆heap是一种数据结构，是一棵完全二叉树且满足性质：所有非叶子结点的值均不大于或均不小于其左、右孩子结点的值。

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

void adjust(int arr[], int len, int index) //大顶堆
{
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;  // maxIdx是3个数中最大数的下标
    if(maxIdx != index)                 // 如果maxIdx的值有更新
    {
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx);       // 递归调整其他不满足堆性质的部分
    }

}
void heapSort(int arr[], int size)
{
    for(int i=size/2 - 1; i >= 0; i--)  // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始)
    {
        adjust(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--)
    {
        swap(arr[0], arr[i]);           // 将当前最大的放置到数组末尾
        adjust(arr, i, 0);              // 将未完成排序的部分继续进行堆排序
    }
}

int main()
{
    int array[8] = {8, 1, 14, 3, 21, 5, 7, 10};
    heapSort(array, 8);
    for(auto it: array)
    {
        cout<<it<<endl;
    }
    return 0;
}

快速排序

基准在最后，index=i 与 小于基准的交换

void quicksort (int arr[], int left, int right){
    if(left>=right) return;
    int i=left, j=right;
    int pivot=arr[left]; //选第一个数作为基准
    
    while (i<j) {
        while(i<j && arr[j]>=pivot) j--; //从后向前扫描，将比基准小的数填到左边
        arr[i]=arr[j];
        while(i<j && arr[i]<=pivot) i++;
        arr[j]=arr[i];
    }
    arr[i]=pivot;  // 将基准数填回
    
    quicksort(arr, left, i-1);  //以基准数为界左右分治
    quicksort(arr, j+1, right);
    
}

选择排序

void picksort(int arr[], int len){
    for(int i=0;i<len-1;i++){
        int minn=INT_MAX;
        int index=i;
        for(int j=i;j<len;j++){
            if(arr[j]<minn){
                minn=arr[j];
                index=j;
            }
        }
        swap(arr[i], arr[index]);
    }
}

插入排序
它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1[图片上传中...(屏幕快照 2018-03-05 下午8.35.12.png-22f77-1520253322803-0)]
)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序过程

void insertionsort(int arr[], int len){
    int i,j,temp;
    for(i=1;i<len;i++){
        temp=arr[i];
        for(j=i; j>0 && arr[j-1]>temp;j--){
            arr[j]=arr[j-1];
        }
        arr[j]=temp;
    }
}

冒泡排序
两两比较，大的后移，一趟后最后一个就是最大的。

void bubblesort(int arr[], int len){
    int i,j;
    for(i=0;i<len-1;i++){
        for(j=i;j<len-1-i;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j], arr[j+1]);
            }
        }
    }
}