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]);
}
}
}
}
网友评论