交换类排序-快速排序

可以理解为划分交换排序几乎最快的排序方法。（分治的策略）

分治法的基本思想

将原有问题分解为若干个规模更小但结构与原问题相似的自问题，递归地解决这些子问题，然后
将这些子问题的解组合为原问题的解

算法步骤

  • 从一个待排序列中任意选择一个记录
  • 以该记录的关键字作为“枢纽”
  • 凡是关键字小于枢纽的记录均移动至该记录之前；反之，移动至该记录之后
  • 一趟排序后，分割成左右两个子序列，再对两个子序列中进行快排

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int QKpass(RecordList L,int low,int high){
    L.r[0] = L.r[low];
    while(low
        while(low=L.r[0].key){
            --high;
        }
        L.r[low] = L.r[high] ;
        while(low
            ++low;
        }
        L.r[high] = L.r[low] ;
    }
    L.r[low] = L.r[0];
    return low;
}


void QKSort(RecordList L,int low, int high){
    if(low>high){
        pos=QKpass(L,low,high);
        QKSort(L,low,pos-1);
        QKSort(l,POS+1,high);
    }
}

输出结果：无

性能分析

  • 快排的时间代价一般取决于枢纽的选择
  • 最简单的办法是选取第一个或最后一个元素作为枢纽，但也是最差的情况，因为总是一个序列是为空，时间复杂度为O（n^2）
  • 可以选取中间位置（low+high）/2作为记录关键字的枢纽值，可以有效平分，最好的情况每次都分为长度相同的子序列，其时间复杂度为O（nlog以二为底的n次方)
  • 快速排序每次移动记录跨度比较大，所以快排是不稳定的
时间复杂度 最好情况 最坏情况 平均复杂度 空间复杂度 稳定性
快速排序 O(nlog2n) O(n^2) O(nlog2n) O(nlog2n) 不稳定

选择类排序-堆排序

为了弥补树形选择排序占用较多辅助空间的问题，利用堆的特性进行排序的方法

堆的定义

堆是满足下列性质的数列：
将数列看成一颗完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：
其左、右子树分别是堆，并且当左右子树不空时，根节点的值小于（或大于）左右子树根节点的值。

算法步骤

  • 首先将待排序的无序序列建初始小顶堆：堆顶元素为最小值
  • 然后将堆顶记录和堆尾记录交换，并将最后一个记录的枝剪掉
  • 调整剩余的记录序列，利用筛选法重新调整为一个新堆，堆顶元素为次最小值，然后交换并剪枝
  • 进行n-1次操作后，直到所有元素输出的元素为一个有序序列

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//堆的筛选
void heapAdjust(RecordList L,int s,int m){
    //调整L.r[s]的关键字，使L.s[s..m]成为一个小顶堆
    t = L.r[s];
    for(j=2*s;j<=m;j*=2){< span>
        //沿key较小的孩子结点向下筛选
        if(jL.r[j+1].key){
            j++;
        }
        if(t.key<=l.r[j].key){< span>
            break;
        }
        //t应插入在位置s上
        L.r[s] = L.r[j];
        s= j;

    }
    L.r[s]=t;
}

//建初始堆
void CreatHeap(RecordList L){
    for(i=L.length/2;i>=1;i--){
        HeapAdjust(L,i,L.length);
    }
}
//堆排序
void HeapSort(RecordList L){
    CreatHeap(L);
    for(i=L.length;i>=2;i--){
        L.r[0] = L.r[1];
        L.r[1] = L.r[i];
        L.r[i] = L.r[0];
        HeapAdjust(L,1,i-1);
    }
}

输出结果：无

性能分析

  • 堆排序主要花费在建初始堆和调整建新堆反复的筛选上
  • 对于深度为k的堆，筛选中关键字的比较次数最多为2(k-1)次。堆排序的时间复杂度为O（nlog2n）
  • 只需要一个辅助空间，故空间复杂度为O（1）
  • 堆排序仍然是大跨度调整了元素位置，为不稳定的排序
时间复杂度 最好情况 最坏情况 平均复杂度 空间复杂度 稳定性
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定

归并类排序-二路归并排序

分配类排序-链式基数排序

外部排序-置换选择排序