标签：nlogn int 复杂度 low key 排序

排序

将一组杂乱无章的数据按一定规律顺次排列起来

如果参加数据的结点含有多个数据域，那么排序往往针对其中某个域

排序分类

按存储介质：
- 内部排序：数据量不大、数据在内存中，无需内外存交换数据
- 外部排序：数据量较大，数据在外存；数据分批掉入内存排序，中间结果还要及时放入外存
按比较器个数：
- 串行排序：同一时刻比较一对元素（单处理机）
- 并行排序：同一时刻比较多对元素（多处理机）
按主要操作：
- 比较排序：用比较的方法
- 基数排序：不比较元素大小，仅仅根据元素本身的取值确定其有序位置
按辅助空间：
- 原地排序：辅助空间用量为O(1)；所占辅助存储空间与参加排序的数据量大小无关
- 非原地排序：辅助空间用量超过O(1)
按稳定性：
- 稳定排序：能够使任何数值相等的元素，排序以后相对次序不变（只对结构类型数据排序有意义）
- 非稳定排序：不是稳定排序
按自然性：
- 自然排序：输入数据越有序，排序速度越快
- 非自然排序：不是自然排序

插入排序

将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到全部对象插入为止

直接插入排序

顺序法定位插入为止

#define MAXSIZE 20

typedef struct {    //定义每个记录的结构
    int key;
    //其他
}RecordType;

typedef struct {    //定义顺序表的结构
    RecordType r[MAXSIZE+1];
    int length;
}SqList;

void Insert_Sq(SqList *L){
    int i,j;
    for (i = 2; i <=L->length ; ++i) {
        if(L->r[i].key<L->r[i-1].key){
            L->r[0].key=L->r[i].key;
            for (j = i-1; L->r[0].key<L->r[j].key ; j--) {
                L->r[j+1].key=L->r[j].key;
            }
            L->r[j+1]=L->r[0];
        }
    }
}

最好时：比较n-1次；移动0次
最坏时：比较(n+2)(n-1)/2次；移动(n+4)(n-1)/2次

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定

二分插入排序

二分法定位插入位置

比直接插入排序快
比较次数与初始排列无关，仅与对象个数有关，在插入第i个对象时，需要经过⌊log2 i⌋ +1次比较
若初始排列接近有序时，直接插入排序比折半插入排序比较次数少
减少了比较次数，没有减少移动次数
时间复杂度O(n^2)
空间复杂度O(1)
是一种稳定的排序方法

void BInsert_Sq(SqList *L){
    int i,j,mid;
    for (i = 2; i <=L->length ; ++i) {
        int low=1,high=i-1;
        if(L->r[i].key<L->r[i-1].key){
            L->r[0]=L->r[i];
            while (low<=high){
                mid=(low+high)/2;
                if(L->r[0].key<L->r[mid].key){
                    high=mid-1;
                }
                else if(L->r[0].key>L->r[mid].key){
                    low=mid+1;
                }
            }//在high+1处插入
            for (j = i-1; j <=high+1 ;j--) {
                L->r[j+1]=L->r[j];
            }
            L->r[high+1]=L->r[0];
        }
    }
}

希尔排序

缩小增量、多遍插入排序

基本思想：先将整个待排序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序，再对全体进行一次直接插入排序

定义增量序列（必须递减、互质且最后是1）Dk : DM>DM-1>.….>D1=1；如：D3=5，D2=3，D1=1
对每个Dk进行“Dk-间隔”插入排序(k=M，M-1，....,1)

void ShellInsert(SqList *L,int dl){
    int i,j;
    for ( i = dl+1; i <L->length ; ++i) {
        if(L->r[i].key<L->r[i-dl].key){
            L->r[0]=L->r[i];
            for (j = i-dl; j >0&&(L->r[0].key<L->r[j].key) ; j=j-dl) {
                L->r[j+dl]=L->r[j];
            }
            L->r[j+dl]=L->r[0];
        }
    }
}

void ShellSort(SqList *L,int dlta[],int t){
    //dlta[0...t-1]为增量序列
    for (int i = 0; i <t ; ++i) {
        ShellInsert(L,dlta[i]);
    }
}

希尔排序的算法效率与增量序列有关；不宜在链式存储结构上实现

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
希尔排序	O(n)	O(n^2)	~O(n^1.3)	O(1)	不稳定

交换排序

两两比较，若逆序则交换，直到所有记录都排好序为止

冒泡排序

两两比较，按前小后大规则交换

每趟增加一个有序元素（越靠后气泡越大）

n个记录共需要n-1趟
第i趟需要比较n-i次
每趟结束最大值在最后，还能同时理顺其他元素

void Bubble_Sort(SqList *L,int n){
    int m,j;
    RecordType x;
    for (m= 1; m<=n-1 ; m++) {  //共需要n-1趟
        for (j = 1; j<=n-m ; j++) {     //一趟需要比较n-m次
            if(L->r[j].key>L->r[j+1].key){
                x=L->r[j];
                L->r[j]=L->r[j+1];
                L->r[j+1]=x;
            }
        }
    }
}

改进：若前面未发生交换则可直接跳出循环

void Bubble_Sort(SqList *L,int n){
    int m,j,flag=1;
    RecordType x;
    for (m= 1; m<=n-1 && flag==1; m++) {  //共需要n-1趟
        flag=0;
        for (j = 1; j<=n-m ; j++) {     //一趟需要比较n-m次
            if(L->r[j].key>L->r[j+1].key){
                flag=1;
                x=L->r[j];
                L->r[j]=L->r[j+1];
                L->r[j+1]=x;
            }
        }
    }
}

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定

快速排序

步骤：

任意一个元素（如第一个）为中心
所有比中心小的元素放在中心前，所有比中心大的元素放在中心后，形成左右两个子表
对各子表重新进行1、 2 步，直至每个子表仅剩一个元素

L->[0]=L->r[low] 此时L->r[low]位置为空，因此从后面找到一个比中心小的元素放入L->r[low]中，此时L->r[high]为空

在前面找一个比中心大的元素放入L->r[high]中，此时L->r[low]为空

当low==high时结束，将L->r[0]放入L->r[low]中，进行递归操作

int Partition(SqList *L, int low, int high){
    int pivotloc;
    L->r[0]=L->r[low];
    pivotloc=L->r[low].key;
    while (low<high){
        while (low<high && L->r[low].key<=L->r[pivotloc].key) low++;
        L->r[high]=L->r[low];
        while (low<high && L->r[high].key>=L->r[pivotloc].key) high--;
        L->r[low]=L->r[high];
    }
    L->r[low]=L->r[0];
    return low;
}//O(n)

void QSort(SqList *L,int low,int high){
    int pivotloc;
    if(low<high){
        pivotloc=Partition(L,low,high);
        QSort(L,low,pivotloc-1);
        QSort(L,pivotloc+1,high);
    }
}//O(log2 n)

int main()
{
    SqList *L;
    L=(SqList*)malloc(sizeof(int)*MAXSIZE);
    QSort(L,1,L->length);
}

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(nlogn)	不稳定

就平均复杂度O(nlog2 n)而言，快速排序是内排序中最好的
不是原地排序 （递归需要栈）
- 平均时需要O(logn）栈空间
- 最坏时需要O(n)栈空间
不是自然排序
不适合于对原本有序或基本有序的记录进行排序

选择排序

步骤：

通过n-1次关键字比较，从n个记表中找出关键字最小的记录，将它与第一个记录交换
再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换
重复上述操作，共进行n-1趟排序后，排序结束

void SelectSort(SqList *L){
    int min;
    int k=1;
    for (int j = 1; j <L->length ; ++j) {
        for (int i = k; i <=L->length ; ++i) {
            if(L->r[i].key<L->r[k].key){
                min=L->r[i].key;
                L->r[i].key=L->r[k].key;
                L->r[k].key=min;
            }
        }
        k++;
    }
}

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定

最好移动0次，最坏移动3(n-1)次
不稳定排序

堆排序

堆：

若n个元素的序列{a1 a2， ... an}满足ai ≤ a2i且ai ≤ a2i+1或ai ≥ a2i且ai ≥ a2i+1

则分别称该序列{a1 a2 ... an}为小根堆和大根堆

实质：完全二叉树 的根结点≤左右孩子（小根堆）；根结点≥左右孩子（大根堆)

例：

筛选：

输出堆顶元素
堆中最后一个元素代替根结点
新的根结点与其左右孩子比较选择其中最小（大）的进行交换
重复3直至最大元素到叶子结点

堆的建立：

在完全二叉树中，所有叶子结点为根的子树是堆，因此只要调整序号为n/2,n/2 -1,..., 1（非叶子结点）的结点即可

void HeapAdjust(int R[],int s,int m){   //调整为大根堆
    int rc=R[s];
    for (int j = 2*s; j <=m ; j*=2) {
        if(j<m&&R[j]<R[j+1]) j++;
        if(rc>=R[j]) break;
        R[s]=R[j];
        s=j;
    }
    R[s]=rc;	
}

void HeapSort(int R[],int n){
    int i,t;
    for (i =n/2; i >=1 ; i--) {     //建堆
        HeapAdjust(R,i,n);
    }
    for (i= n; i >1 ; i--) {   //排序
        t=R[i];
        R[i]=R[1];
        R[1]=t;
        HeapAdjust(R,1,i-1);
    }
}

最好最坏时间复杂度都是O(nlogn）；空间复杂度O(1)
不稳定排序
适用于n较大的排序

归并排序

将两个或两个以上子序列归并为一个有序序列

例：二路归并排序（共需要log2 n趟)

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

基数/桶/箱排序

分配+收集

按个位、十位、百位...进行分配并收集

例：

(614, 738,921，485，637，101，215，530，790，306)

结束，排序完成

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
基数排序	O(n+m)	O(k*(n+m))	O(k*(n+m))	O(n+m)	稳定

n为待排序的个数；m为桶的个数；k为待排元素的维数

排序比较

	时间	复杂	度	空间复杂度	稳定性
排序方法	最好	最坏	平均	辅助空间
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
希尔排序	O(n)	O(n^2)	~O(n^1.3)	O(1)	不稳定
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
快速排序	O(nlogn)	O(n^2)	O(nlogn)	O(nlogn)	不稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n^2)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
基数排序	O(n+m)	O(k*(n+m))	O(k*(n+m))	O(n+m)	稳定

标签：nlogn,int,复杂度,low,key,排序
From： https://www.cnblogs.com/yuanyu610/p/17110066.html

排序

排序