目录

8638 直接插入排序

8639 折半插入排序

8640 希尔(shell)排序

8642 快速排序

8644 堆排序

8645 归并排序（非递归算法）

8638 直接插入排序

8639 折半插入排序

8640 希尔(shell)排序

#include 

using namespace std;
int a[1000];
int n;


void print()
{
    for(int i=1 ; i<=n ; i++)
    {
        cout0&&a[0]=1)
//    {
//        ShellInsert(d);
//        d/=2;
//    }
//
    ShellInsert(1); //直接插入排序
}

int main()
{
    cin>>n;
    for(int i=1 ; i<=n ; i++)
        cin>>a[i];
    ShellSort(n);
    return 0;
}

8642 快速排序

#include 
#include 
using namespace std;
int a[1000];
int n;
void print()
{
    for(int i=1 ; i<=n ; i++)
    {
        cout<=a[0]) high--;
        a[low]=a[high];
        while(low>n;
    for(int i=1 ; i<=n ; i++)
        cin>>a[i];
    QSort(a,1,n);
    return 0;
}

8644 堆排序

#include 
#include 
using namespace std;
int a[100];
int n;

void print()
{
    for(int i=1 ; i<=n ; i++)
    {
        cout<=a[i])          //这里是a[0]而不是a[k]，a[k]可能会指向比a[0]更大的元素，最后要找的是能放a[0]的位置，进行这步的前提是：下方已经没有比最先记录的小元素(上文记录的根)更小的了，也就是说，下方本来就已经是堆-->所以最开始建立大顶堆时要自下而上全部调整
            break;
        else  //开始自上而下 ，小元素在多次该循环中持续下坠
        {
            a[k]=a[i];          //把大孩子拉上来
            k=i;   //聚焦到大孩子走后空缺的位置：为了后续的循环-->继续向下看该树
        }
    }
    a[k]=a[0];   //小元素(上文记录的根)放入最终位置
}


void BuildMaxHeap(int a[],int len)
{
    for(int i=len/2 ; i>0 ; i--)   //自下而上，每个非叶子节点必须都要遍历到
        HeadAdjust(a,i,len);
}




void HeapSort(int a[],int len)
{
    BuildMaxHeap(a,len);
    print();
    for(int i=len ; i>1 ; i--) //0号位用作temp暂存数据，1号位才是顶部 
                               
    {
        swap(a[i],a[1]);     //找到了堆顶元素（最大值），堆顶堆底互换位置
        HeadAdjust(a,1,i-1); //剩余元素重新调整为堆，末尾元素已完成排序，len-1
                             //除堆顶的树外，其余的树都已是堆，不用再次自下而上调整，而是直接自上而下
        print();
    }
}


int main()
{
    cin>>n;
    for(int i=1 ; i<=n ; i++)
    {
        cin>>a[i];
    }
    HeapSort(a,n);
    return 0;
}

8645 归并排序（非递归算法）

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
using namespace std;
//归并两个部分  bg为第一部分的起点   mid为第二部分的起点   end为第二部分边界的下一位
void Merge(int num[], int bg, int mid, int end)
{
    //建立临时数组存两个部分的合并后的数组
    int* tmp = new int[end - bg];
    int i = bg, j = mid;
    int k = 0;
    //比较两部分   当i=mid 或j=end 退出
    while (i < mid && j < end)
    {
        //由大小依次排序放到临时数组里   直到一个部分排完退出
        if (num[i] > num[j])
        {
            tmp[k++] = num[j++];
        }
        else
        {
            tmp[k++] = num[i++];
        }
    }
    //如果前半部分没存完  依次存进去
    while (i < mid)
    {
        tmp[k++] = num[i++];
    }
    //如果后半部分没存完  依次存进去
    while (j < end)
    {
        tmp[k++] = num[j++];
    }
    //把排好的临时数组存到num数组对应下标里 别忘了这一步，否则将重复print原数组！！！！
    for (int i = 0; i < k; i++)
    {
        num[bg++] = tmp[i];
    }
}

int main(void)
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    int* num = new int[n + 1];
    for (int i = 1; i <= n; i++) cin >> num[i];

    //width为一部分的长度    依次为1 2 4 8  外层判断条件不能写width<=n  取等可能会重复输出一次
    for (int width = 1; width < n; width *= 2)
    {
        // 第一部分起点bg为1  下一次为  bg+两个长度
        for (int bg = 1; bg <= n; bg += width * 2)
        {
            //mid为第二部分的起点
            int mid = bg + width;
            //为了防止访问错误  如果mid边界大于 n则最大为 n+1
            if (mid > n)mid = n + 1;
            //end为第二部分边界的下一位
            int end = bg + width * 2;
            //同理  最大只能为 n+1
            if (end > n)end = n + 1;
            //合并两部分
            Merge(num, bg, mid, end);
        }
        //检查
        for (int i = 1; i <= n; i++) cout << num[i] << ' ';
        cout << endl;
    }
    return 0;
}