内部排序

#include <stdio.h>

typedef int elementType; // 将需要操作的数据元素定义别名，方便修改
#define MAX_SIZE 100 // 初始化操作数组的最大容量

// 交换两个元素的值
void swap(elementType *a, elementType *b)
{
    elementType temp = *a;
    *a = *b;
    *b = temp;
}

// 1.直接插入排序(将每个待排序的关键字插入前面已经有序的序列中)
void insetSort(elementType A[], int len)
{
    elementType temp;
    int i,j;
    for (i = 1; i < len; i++) // 依次检查A[1]~A[n-1]
    {
        if(A[i] < A[i-1]) // 若A[i]小于前驱则需要移动
        {
            temp = A[i]; // 暂存当前元素
            for (j = i-1; temp < A[j] && j >= 0; --j)
                A[j+1] = A[j]; // 不断向前遍历、移动，直到不小于左侧元素
            A[j+1] = temp; // 复制到插入位置
        }
    }
}

// 1.2折半插入排序(直接插入排序是边比较边移动元素，而折半插入是把比较和移动分离，
// 即先用折半查找确定元素的待插入位置，然后统一移动待插入位置后的所有元素)
void binaryInsertSort(elementType A[],int len)
{
    elementType temp; // 定义临时变量暂存待插入元素
    int low,high,mid; // 定义折半查找定位指针
    for (int i = 1; i < len; i++) // 依次将A[1]~A[n-1]插入到前面的有序序列
    {
        temp = A[i]; // 暂存待插入元素
        low = 0,high = i-1; // 设置折半查找的范围
        while (low <= high)
        {
            mid = (low+high)/2;
            if(A[mid] < temp)
                low = mid + 1; // 查找右子表
            else
                high = mid -1; // 查找左子表
        }
        for (int j = i-1; j > high; j--)
            A[j+1] = A[j]; // 统一后移元素，空出插入位置
        A[high+1] = temp; // 插入到指定位置
    }
}

// 2.希尔排序(把待排序序列中相隔某个”增量“的元素组成一个子表，对各个子表直接插入排序，
// 当整个表已经基本有序时，再对全体记录进行一次直接插入排序。)
void shellSort(elementType A[], int len)
{
    elementType temp; // 临时变量暂存待插入元素
    int d,i,j; // d为步长
    for (d = len/2; d >= 1 ; d /=2)
    {
        for (i = d; i <= len; i++)
        {
            if(A[i] < A[i-d])
            {
                temp = A[i];
                for (j = i-d; j >=0 && temp < A[j]; j -= d)
                    A[j+d] = A[j]; // 记录后移，更新插入位置
                A[j+d] = temp; // 插入待插入元素
            }
        }
    }
}

// 3.冒泡排序(从前往后或从后往前两两比较相邻元素的值，若为逆序，则交换它们，直到比较结束)
void bubbleSort(elementType A[], int len)
{
    int flag; // 标记某趟冒泡是否进行了交换
    for (int i = 0; i < len-1 ; i++)
    {
        flag = 0; // 每趟冒泡前把flag置为false
        for (int j = len-1; j > i; j--) // 一趟冒泡
        {
            if(A[j] < A[j-1]) //是否存在逆序
            {
                swap(&A[j],&A[j-1]);
                flag = 1; // 发生交换动作后把flag置为true
            }
        }
        if(!flag) break; // 若某趟未进行交换操作，则排序结束
    }
}

// 快排划分
int partition(int A[], int low, int high)
{
    int pivot = A[low]; //第一个元素作为基准
    while (low < high)
    {
        while (low < high && A[high] >= pivot)
            --high;
        A[low] = A[high]; // 比基准小的移动到左端
        while (low < high && A[low] <= pivot)
            ++low;
        A[high] = A[low]; // 比基准大的移动到右端
    }
    A[low] = pivot;
    return low; // 返回存放基准的最终位置
}

// 4.快速排序(快速排序是基于分治法的，在待排序表中任取一个元素作为枢纽或基准，
// 通过一趟排序划分为两部分，小于基准的元素放到基准左边，大于的放到右边，
// 这样就确定了一个元素的位置，不断划分，不断移动，递归上述过程直到有序。)
void quickSort(int A[], int low, int high)
{
    if (low < high)
    {
        int pivotPos = partition(A, low, high); // 划分
        quickSort(A, low, pivotPos - 1); // 划分左子表
        quickSort(A, pivotPos + 1, high); // 划分右子表
    }
}

// 5.简单选择排序(每趟在后面n-i+1个待排序元素中选出最小的元素，
// 作为有序子序列的第i个元素，直到n-1趟做完只剩1个，就不必再选了。)
void selectSort(elementType A[], int len)
{
    int i, j,min;
    for (i = 0;i < len-1;i++) // 最后剩一个不用处理，所以是i < n-1
    {
        min = i;
        for ( j = i+1; j < len; j++)
        {
            if (A[j] < A[min])
                min = j;
        }
        if (min != i)
            swap(&A[i],&A[min]);
    }
}

// 调整堆
void adjustHeap(elementType A[],int i,int len)
{
    A[0] = A[i]; // 暂存根节点(若A[0]元素有实际意义，也可用临时变量)
    for (int k = 2*i; k <= len; k *=2) // k *=2表示沿着较大的子结点向下筛选
    {
        if(k < len && A[k] < A[k+1])
            k++; // 记录下最大的孩子结点的索引值
        if(A[0] >= A[k])
            break; // 如果满足大根堆(根节点不小于最大的孩子)则退出循环无需继续调整
        A[i] = A[k]; // 将最大的元素调节到双亲节点上
        i = k; // 修改索引，继续筛选
    }
    A[i] = A[0]; // 将被筛选的结点放入最终位置
}

// 建立大根堆
void buildMaxHeap(elementType A[],int len)
{
    for (int i = len/2; i > 0; i--)
        adjustHeap(A,i,len);
}

// 6.堆排序(大根堆：二叉树根节点大于左右孩子，小根堆则小于；将数组视为顺序存储的树，
// 利用堆这一特性，创建堆，调整堆，每调整一轮都从中选出了最大值，不断将堆顶元素放入堆底。)
void heapSort(elementType A[],int len)
{
    // 1.初始化大根堆
    buildMaxHeap(A,len);
    // 2.不断的调整堆，并且把堆顶元素和堆底元素交换，堆不断缩小
    for (int i = len; i > 1; i--)
    {
        swap(&A[1],&A[i]); //将大根堆堆顶元素放入堆底
        adjustHeap(A,1,i-1); // 不断的调整缩小的堆，直到最大的元素依次在堆底
    }
}

elementType B[MAX_SIZE]; // 定义一个辅助数组，用于归并排序的归并操作
// 归并操作
void merge(elementType A[],int low,int mid,int high)
{
    int i,j,k;
    for (k = low;k <= high;k++)
        B[k] = A[k]; // 将A中的元素复制到B中
    for (i = low,j = mid+1,k = i; i <= mid && j <= high; k++)
    {
        if(B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while (i<=mid) // 若左表剩余，复制回A表尾部
        A[k++] = B[i++];
    while (j<=high) // 若右表剩余，复制回A表尾部
        A[k++] = B[j++];
}

// 7.二路归并排序(归并排序是基于归并操作实现的，每次归并将相邻的两个有序序列归并成一个)
void mergeSort(elementType A[],int low,int high)
{
    if(low < high)
    {
        int mid = (low+high)/2; // 从中间划分为两个子序列
        mergeSort(A,low,mid); // 对左侧子序列递归排序
        mergeSort(A,mid+1,high); // 对右侧子序列递归排序
        merge(A,low,mid,high); // 合并相邻的两个有序的序列
    }
}

// 打印数组元素，从index下标开始打印len个长度
void printArray(elementType A[],int index,int len)
{
    // 判断数组是否越界
    if(index < 0 || index + len > MAX_SIZE)
    {
        printf("Array Index OutOf Bounds Exception!");
        return;
    }
    for (int i = index; i < index + len; ++i)
    {
        printf("%d",A[i]);
        if(i < index + len - 1)
            printf(",");
    }
    printf("\n");
}

int main()
{
    // 1.直接插入排序
    elementType A[MAX_SIZE] = {49,38,65,97,76,13,27,49};
    insetSort(A,8);
    printArray(A,0,8);

    // 1.1折半插入排序
    elementType A1[MAX_SIZE] = {49,38,65,97,76,13,27,49};
    binaryInsertSort(A1,8);
    printArray(A1,0,8);

    // 2.希尔排序
    elementType B[MAX_SIZE] = {0,49,38,65,97,76,13,27,49};
    shellSort(B,8);
    printArray(B,1,8);

    // 3.冒泡排序
    elementType C[MAX_SIZE] = {49,38,65,97,76,13,27,49};
    bubbleSort(C,8);
    printArray(C,0,8);

    // 4.快速排序
    elementType D[MAX_SIZE] = {49,38,65,97,76,13,27,49};
    quickSort(D,0,7);
    printArray(D,0,8);

    // 5.简单选择排序
    elementType E[MAX_SIZE] = {49,38,65,97,76,13,27,49};
    selectSort(E,8);
    printArray(E,0,8);

    // 6.堆排序
    elementType F[MAX_SIZE] = {0,49,38,65,97,76,13,27,49};
    heapSort(F,8);
    printArray(F,1,8);

    // 7.归并排序
    elementType G[MAX_SIZE] = {49,38,65,97,76,13,27,49};
    mergeSort(G,0,7);
    printArray(G,0,8);

    return 0;
}