首页 数据结构（C++）
  1. 顺序表存储
  2. 插入排序
    2.1 直接插入排序
    2.2 折半插入排序
    2.3 希尔排序
  3. 交换排序
    3.1 冒泡排序
    3.2 双向冒泡算法
    3.3 快速排序
  4. 选择排序
    4.1 直接选择排序
    4.2 锦标赛排序
    4.3 堆排序
  5. 归并排序
    5.1 二路归并
  6. 分配排序
    6.1 桶排序
    6.2 基数排序
  7. 总结

image-20251228091813587
image-20251228091823816
image-20251228091838757
image-20251228091857247
image-20251228091911068
image-20251228091943239

# 一、顺序表存储

const int defaultSize=100;
template<class T>
class SeqList
{
protected:
    T *data;// 存放数组
    int maxSize;// 最大可容纳表项的项数
    int last;// 数组中最后一个元素的下标
public:
    SeqList(int sz=defaultSize);// 构造函数
    int Size() const
    {
        return maxSize;// 求表最大容量
    }
    int Length() const
    {
        return last+1;// 计算表长度
    }
    int Search(T &x) const;// 搜索 x 在表中位置，函数返回表项序号
    //......
	void InsertSort();// 直接插入排序算法
    void Binary_InsertSort();// 折半插入排序算法
    void ShellSort();// 希尔排序算法
    void BubbleSort();// 冒泡排序算法
    void DoubleBubble();// 双向冒泡算法
    int QuickPass(int low,int high);// 一次快速排序
    void QuickSort(int low,int high);// 快速排序算法
    void SelectSort();// 直接排序算法
    void HeapSort();// 堆排序算法
};


# 二、插入排序
image-20251228092431136
# 1. 直接插入排序
image-20251228092457952
image-20251228092527979
最好情况下比较 (n−1)(n-1) 次，移动 00 次，复杂度 O(n)O(n)；
最坏情况下比较 n(n−1)2\frac{n(n-1)}{2} 次，移动(n+4)(n−1)2\frac{(n+4)(n-1)}{2} 次，复杂度 O(n2)O(n^2)
平均情况 O(n2)O(n^2)
稳定性：稳定

# 普通算法
template<class T>
void SeqList<T>::InsertSort()// 直接插入排序算法
{
    int i,j;
    T x;
    for(i=2;i<=last;++i)// 依次将 data [2],...data [last] 插入序列中
    {
        x=data[i];// 暂存元素到 x 中
        j=i-1;
        while(x<data[j] && j>0)// 查找 x (即原 data [i]) 的插入位置
        {
            // 将序列中排序码大于 x 的记录往后移
            data[j+1]=data[j--];//data[j+1]=data[j];    j--;
        }
        data[j+1]=x;// 填入 data [i]
    }
}

# 优化算法
// 优化算法
// 核心是把 data [0] 作为不存数据的岗哨和临时单元，从而省掉边界判断，提高效率。
template<class T>
void SeqList<T>::InsertSort()// 直接插入排序算法
{
    int i,j;
    for(i=2;i<=last;++i)// 依次将 data [2],...data [last] 插入序列中
    {
        data[0]=data[i];//data [0] 作为岗哨和暂存单元
        j=i-1;
        while(data[0]<data[j])// 查找原 data [i] 的插入位置
        {
            // 将序列中排序码大于 x 的记录往后移
            data[j+1]=data[j--];//data[j+1]=data[j];    j--;
        }
        data[j+1]=data[0];// 填入 data [i]
    }
}


# 2. 折半插入排序
image-20251228101457403
比较O(nlog⁡n)O(n \log n) 次，移动O(n2)O(n^2) 次，时间复杂度 O(n2)O(n^2)
平均情况 O(n2)O(n^2)
稳定性：稳定
template<class T>
void SeqList<T>::Binary_InsertSort()// 折半插入排序
{
    int i,j;
    for(i=2;i<=last;++i)// 依次将 data [2],...data [last] 插入序列中
    {
        data[0]=data[i];//data [0] 作为暂存单元
        int low=1;//low 作为折半查找的上界
        int high=i-1;//high 作为折半查找的下界
        while(low<=high)// 用折半方法查找 data [i] 的插入位置
        {
            int mid=(low+high)/2;// 下取整
            if(data[0]<data[mid])
            {
                high=mid-1;
            }
            else// 如果遇到两个数相同，则插在后面，可保证稳定性
            {
                low=mid+1;
            }
        }
        for(j=i-1;j>=low;j--)
        {
            data[j+1]=data[j];// 把序列中排序码大于 data [i] 的记录后移
        }
        //high 最终指向的是：「最后一个比插入元素大的元素的前一个位置」
		//low 最终指向的是：「第一个大于插入元素的位置」，这正是插入点应该在的位置。
        data[low]=data[0];// 把暂存在 data [0] 的 data [i] 填入相应的位置中
    }
}


# 3. 希尔排序
image-20251228120643397
image-20251228121401505
image-20251228121411089
平均情况 O(n1.3)O(n^{1.3})
稳定性：不稳定

template<class T>
void SeqList<T>::ShellSort()// 希尔排序算法
{
    int i,j,k;
    k=last/2;// 增量值
    while(k>=1)// 直到增量值为 1 为止
    {
        for(i=k+1,i<=last,++i)
        {
            data[0]=data[i];//data [0] 作为岗哨和暂存单元
            j=i-k;// 同一组的前一个位置
            while(data[0]<data[j] && j>0)
            {
                data[j+k]=data[j];
                j=j-k;
            }
            data[j+k]=data[0];
        }
        k=k/2;
    }
}


# 三、交换排序
image-20251228133756878
# 1. 冒泡排序
image-20251228133737948
image-20251228133831650
最好情况下比较 (n−1)(n-1) 次，移动 00 次，复杂度 O(n)O(n)；
最坏情况下比较 n(n−1)2\frac{n(n-1)}{2} 次，移动3n(n−1)2\frac{3n(n-1)}{2} 次，复杂度 O(n2)O(n^2)
平均情况 O(n2)O(n^2)
稳定性：稳定

# 普通算法
template<class T>
void SeqList<T>::BubbleSort()// 冒泡排序算法
{
    int i,j;
    for(i=1;i<last;++i)
    {
        for(j=1;j<last-i;++j)
        {
            if(data[j]>data[j+1])//data [j] 与 data [j+1] 不符合排序要求则交换
            {
                data[0]=data[j];// 进行交换，data [0] 作为记录交换的暂存单元
                data[j]=data[j+1];
                data[j+1]=data[0];
            }
        }
    }
}

# 改进算法
template<class T>
void SeqList<T>::BubbleSort()// 改进算法
{
    int i=0;
    int j;
    int flag=1;// 设置交换标志，0 表示无交换，1 表示有交换
    while(flag==1)
    {
        flag=0;
        i++;
        for(j=1;j<last-i;++j)
        {
            if(data[j]>data[j+1])//data [j] 与 data [j+1] 不符合排序要求则交换
            {
                flag=1;// 有交换存在
                data[0]=data[j];// 进行交换。data [0] 作为记录交换的暂存单元
                data[j]=data[j+1];
                data[j+1]=data[0];
            }
        }
    }
}

# 2. 双向冒泡算法
template<class T>
void SeqList<T>::DoubleBubble()
{
    int flag=1;// 需要继续排序时为 1，已排序好不需继续排序时为 0
    int i=0;
    int j;
    while(flag==1)
    {
        flag=0;
        for(j=i+1;j<last-i;++j)// 正向冒泡找最大值
        {
            if(data[j]>data[j+1])
            {
                flag=1;// 能交换时，说明未排好序，需继续
                data[0]=data[j];
                data[j]=data[j+1];
                data[j+1]=data[0];
            }
        }
        for(j=last-i-1;j>i+1;j--)// 反向冒泡找最小值
        {
            if(data[j]<data[j-1])
            {
                flag=1;// 能交换时，说明未排好序，需继续
                data[0]=data[j];
                data[j]=data[j-1];
                data[j-1]=data[0];
            }
        }
        i++;
    }
}

# 3. 快速排序
image-20251228145609039
image-20251228145624179
最好情况下时间复杂度 O(nlog⁡n)O(n \log n)，空间复杂度O(log⁡n)O(\log n)；
最坏情况下时间复杂度 O(n2)O(n^2)，空间复杂度O(n)O(n)；
平均情况下时间复杂度 O(nlog⁡n)O(n \log n)，空间复杂度O(log⁡n)O(\log n)
稳定性：不稳定

template<class T>
int SeqList<T>::QuickPass(int low,int high)// 一次快速排序
{
    // 对子序列 data [low] 到 data [high] 做一趟的快速排序
    int down=low;// 分别对位置指示器作初始化
    int up=high;
    data[0]=data[low];// 把基准记录暂存在 data [0]
    while(down<up)
    {
        while((down<up)&&(data[up]>=data[0]))// 从右向左扫描
        {
            up--;
        }
        if(down<up)// 在被腾出来的单元中填入 data [up]
        {
            data[down++]=data[up];
        }
        while((down<up)&&data[down]<=data[0])
        {
            down++;
        }
        if(down<up)// 在被腾出来的单元中填入 data [down]
        {
            data[up--]=data[down];
        }
    }
    data[down]=data[0];// 在正确位置上填入基准记录
    return down;// 返回当前填入基准记录的所在位置
}
template<class T>
void SeqList<T>::QuickSort(int low,int high)// 快速排序算法
{
    int mid;//mid 为一趟快速排序后，基准
    if(low<high)// 当序列中的记录个数为 1 个或无记录时无需排序
    {
        mid=QuickPass(low,high);// 对序列 data [low] 到 data [high] 做一趟快速排序
        QuickSort(low,mid-1);// 对左半部分递归处理
        QuickSort(mid+1,high);// 对右半部分递归处理
    }
}


# 四、选择排序
image-20251228195143529
最好情况下比较 n(n−1)2\frac{n(n-1)}{2} 次，移动 00 次，复杂度 O(n2)O(n^2)；
最坏情况下比较 n(n−1)2\frac{n(n-1)}{2} 次，移动3(n−1)3(n-1) 次，复杂度 O(n2)O(n^2)
平均情况 O(n2)O(n^2)
稳定性：不稳定

# 1. 直接选择排序
image-20251228201158498
# 普通算法
template<class T>
void SeqList<T>::SelectSort()// 直接选择排序普通算法
{
    int i,j,pos;
    for(i=1;i<last;++i)// 共做 n-1 趟选择排序
    {
        pos=i;// 记录当前排序码最小值的记录所在位置
        for(j=i+1;j<=last;++j)
        {
            if(data[j]<data[pos])
            {
                pos=j;
            }
        }
        data[0]=data[i];//data [0] 作为交换的暂存单元
        data[i]=data[pos];
        data[pos]=data[0];
    }
}

# 优化算法
template<class T>
void SeqList<T>::SelectSort()// 直接选择排序优化算法
{
    int i,j,pos;
    for(i=1;i<last;++i)// 共做 n-1 趟选择排序
    {
        pos=i;// 记录当前排序码最小值的记录所在位置
        for(j=i+1;j<=last;++j)
        {
            if(data[j]<data[pos])
            {
                pos=j;
            }
        }
        if(pos!=i)// 只有当最小值不在当前位置时才交换
        {
            data[0]=data[i];//data [0] 作为交换的暂存单元
            data[i]=data[pos];
            data[pos]=data[0];
        } 
    }
}


# 2. 锦标赛排序
image-20251228204952324
image-20251228205004717
image-20251228205025111
image-20251228205034039
image-20251228205047985
image-20251228205105810
image-20251228205116838
image-20251228205131093
image-20251228205142100
image-20251228205149758

# 3. 堆排序
image-20251228205308684
image-20251228205321845
最好最坏情况下均比较 O(nlog⁡n)O(n \log n) 次，移动 O(nlog⁡n)O(n \log n) 次，时间复杂度 O(nlog⁡n)O(n \log n)；
稳定性：不稳定
#define DefaultSize 10
template<class T>
class MinHeap// 最小堆的类定义
{
    T *heap;// 指向存放堆元素的数组
    int CurrentSize;// 当前堆中元素个数
    int MaxHeapSize;// 堆的最大容量
public:
    MinHeap(int sz=DefaultSize);// 构造函数初始化堆
    MinHeap(T arr[],int n);
    ~MinHeap()// 析构函数
    {
        delete []heap;
    }
    const MinHeap<T> &operator=(const MinHeap &R);
    bool Insert(const T &x);
    bool Remove(const T &x);
    bool IsFull() const
    {
        return CurrentSize==MaxHeapSize;
    }
private:
    void siftDown(int start,int m);// 向下调整
    void siftUp(int start);// 向上调整
};
template<class T>
void SeqList<T>::HeapSort()// 堆排序算法
{
    int i;
    T x;
    MinHeap<T> MyHeap;
    for(i=1;i<=last;++i)// 把待排序元素插入堆中
    {
        MyHeap.Insert(data[i]);
    }
    i=1;
    while(!MyHeap.IsEmpty())// 堆非空
    {
        MyHeap.Remove(x);// 从堆中删除根结点
        data[i]=x;
        i++;
    }
}


# 五、归并排序
# 1. 二路归并
image-20251228231553699
image-20251228231607518
空间复杂度 O(n)O(n)，时间复杂度 O(nlog⁡n)O(n \log n)；
稳定性：稳定


# 六、分配排序
image-20251228232955912
# 1. 桶排序
image-20251228233011039
void SeqList<T>::Bucket_Sort(LinkNode *B[])// 桶排序
{
    int i;
    for(i=1;i<=last;++i)
    {
        // 用尾插入的方法将待排序记录分别装入相应的桶中
        B[data[i]].InsertTail(data[i]);
    }
    for(i=1;i<key;++i)
    {
        // 将所有的桶首尾相连
        B[i].tail=B[i+1].head;
    }
}


# 2. 基数排序
image-20251229000937755
image-20251229000947013
image-20251229001647923
image-20251229001703868
image-20251229001715361
时间复杂度 O(n)O(n)
稳定性：稳定

# 七、总结
image-20251229001844662
image-20251229001856059
    
 更新于