排序 | SyEic

插入排序

直接插入排序
折半插入排序
链表插入排序
希尔排序

直接插入排序

插入第 $i$ 个对象时，前面的 $i-1$ 个已经排好序，按顺序从前到后比较，找到插入位置插入，原来位置上的对象向后顺移

template <class Type> void dataList <Type> :: InsertSort ( ) {
    //按排序码 Key 非递减顺序对表进行排序
    Element<Type> temp; int i, j;
    for ( i = 1; i < CurrentSize; i++ ) {
        if ( Vector[i] < Vector[i-1] {
            temp = Vector[i];
            for ( j = i; j > 0; j-- ){ //从后向前顺序比较
                if ( temp < Vector[j-1] ){
                    Vector[j] = Vector[j-1];
                }
                else {
                    break;
                }
            }
            Vector[j] = temp;
        }
    }
}

时间复杂度： $O(n^2)$
有稳定性

折半插入排序

在插入时用折半搜索寻找插入位置

template <class Type> void dataList<Type> :: BineryInsSort ( ) {
    Element<Type> temp; int Left, Right;
    for ( int i = 1; i < CurrentSize; i++) {
        Left = 0; Right = i-1; temp = Vector[i];
        while ( Left <= Right ) {
            int middle = ( Left + Right )/2;
            if ( temp < Vector[middle] ){
                Right = middle - 1;
            }
            else{
                Left = middle + 1;
        	}
        }
        for ( int k = i-1; k >= Left; k-- ){
            Vector[k+1] = Vector[k];
        }
        Vector[Left] = temp;
    }
}

比直接插入排序快
比较次数与初始序列无关，仅依赖于对象个数
有稳定性
$O(nlogn)$

链表插入排序

数据存储在链表中

希尔排序（Shell Sort）

先分成若干组，在每一个组内用直接排序，然后再对整个序列进行直接插入排序

采用间隔分组方法分组

template <class Type> void dataList<Type> :: ShellSort ( ) {
    Element<Type> temp;
    int gap = CurrentSize / 2; //gap是子序列间隔
    while ( gap != 0 ) { //循环,直到gap为零
        for ( int i = gap; i < CurrentSize; i++) {
            temp = Vector[i]; //直接插入排序
            for ( int j = i; j >= gap; j -= gap ){
                if ( temp < Vector[j-gap] ){
                    Vector[j] = Vector[j-gap];
                }
                else {
                    break;
                }
            }
            Vector[j] = temp;           
        }
        gap = ( int ) ( gap / 2 );
    }
}

不稳定
最坏情况： $O(n^2)$

交换排序

两两比较，如果逆序则交换

冒泡排序

有稳定性
$O(n^2)$

快速排序

任取序列中的某个对象，作为基准，左侧放小的，右侧放大的，对两个子序列重复施行

template <class Type> int dataList<Type> :: Partition (const int low, const int high){
    int pivotpos = low; //基准位置
    Element<Type> pivot = Vector[low];
    for ( int i = low+1; i <= high; i++ ){
        if ( Vector[i] < pivot ) {
            pivotpos++;
            if ( pivotpos != i ){
                Swap ( Vector[pivotpos], Vector[i] );
            }
        }
    } //小于基准对象的交换到区间的左侧去
    Swap ( Vector[low], Vector[pivotpos] );
    return pivotpos;
}

平均情况： $O(nlogn)$
空间复杂度： $O(logn)$
不稳定

选择排序

直接选择
锦标赛
堆排序

直接选择排序

在一组对象 $v[i] - v[n-1]$ 中选择最小的对象
若它不是第一个，则与第一个交换
从这组对象中剔除这个最小的对象，在剩下的 $v[i+1] - v[n-1]$ 中重复执行上述步骤
不稳定

锦标赛

两两比较，选优胜者，循环往复，得到最小的对象，同时记录比较过程

每个节点DataNode：data | index | active

template <class Type> class DataNode{
    public:
    Type data;	//数据
    int index;	//节点在满二叉树的顺序号
    int active;	//参选标志：1参选、0不参选
}

时间复杂度： $O(nlogn)$
空间复杂度：
- 至少： $2n-1$
- 最多： $2*2^k-1$
稳定

堆排序

最大堆
堆顶和最后一个交换
对前 $n-1$ 个对象，filterDown
重复执行
时间复杂度： $O(nlogn)$
空间复杂度： $O(1)$
不稳定

归并排序

两个或两个以上的有序表合并成一个新的有序表

两路归并

n个对象，两两归并，得到 $\lceil \frac{n}{2} \rceil$ 个长度为2的归并项
两两归并，重复得到有序
时间复杂度： $O(nlogn)$
空间复杂度： $O(n)$
稳定

排序