折半排序

本文章的代码使用jetbrains公司旗下的的Clion编写，操作系统位macOS Ventura(13.2.1). 代码没有在dev-c++测试过（dev-c++可能会有相关的空格问题）

//
// Created by 魏志杰 on 2023/7/25.
//

#include "stdio.h"
#define Max 100
#define before  printf("排序前")
#define after   printf("排序后")
#define newline printf("\n")
#define print   printf("%6d", R[i].key)
#define printA  printf("%6d",A[i])
#define Array int A[]={5,7,2,5,9,6,42,1,67,2,3};

typedef struct {
    int key;
    int data;
}SqType;


// 直接插入排序是将无序区的R[i]的（1-n-1）通过从后向前顺序比较插入到有效区R（0,i-1）中,实际上，利用有序区的有序性，我们可以
//  可以采取折半查找的方法，先在R[0,i-1]中找到插入位置，在进行移动元素进行插入，这样的插入排序称为折半插入
//书上的
void binInsert(SqType R[],int n){      //对R[0,n-1]开始按递增有序进行折半插入
    int i,j ,low,high,mid;
    SqType tmp;
    for (i = 1; i < n; i++) {
        if (R[i-1].key>R[i].key){
            tmp=R[i];                     //将R[i]保存在tmp中
            low=0;high=i-1;
            while (low<=high){           //在R[low high]中折半查找有序插入的位置
                mid=(low + high) / 2;    //寻找中间的位置
                if (tmp.key < R[mid].key)
                    high=mid-1;           //插入点在左半区
                else
                    low = mid +1;         //插入点在右半区
                }
            for (j=i-1;j>=high+1;j--)     //元素后移
                R[j+1]=R[j];
                R[high+1]=tmp;            //插入原来的R[j]
            }
     }

}

//将序列分成已排序区和未排序区。初始时已排序区只包含第一个元素，剩余元素构成未排序区。

//从未排序区选择第一个元素，利用二分查找在已排序区找到合适的位置插入该元素，并将已排序区中的元素向后移动。

//重复步骤2，直到未排序区中的所有元素都插入到已排序区.

// 自己写的折半插入排序
void binaryInsertSort(int A[], int n) {
    int i, j, low, high, mid,temp;

    for (i = 1; i < n; i++) {
        temp = A[i];
        low = 0;
        high = i - 1;

        // 二分查找找到插入位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > temp) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        // 将已排序区中的元素向后移动
        for (j = i - 1; j >= low; j--) {
            A[j + 1] = A[j];
        }

        // 插入元素到合适位置
        A[low] = temp;
    }
}



int  main(){
    SqType R[Max];
    Array;
    for (int i = 0; i < 10; i++)
        R[i].key = A[i];
    before;
    for (int i = 0; i < 10; i++)
        print;
    newline;
    binInsert(R,10);
    after;
    for (int i = 0; i < 10; i++)
        print;
    newline;
    binaryInsertSort(A,10);
    after;
    for (int i = 0; i < 10; i++)
        printA;

}

测试如下