排序

交换排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef int ElemType;
typedef struct {
    ElemType* elem;//存储元素的起始地址
    int TableLen;//元素个数
}SSTable;

void ST_Init(SSTable& ST, int len)
{
    ST.TableLen = len;
    ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    int i;
    srand(time(NULL));
    for (i = 0; i < ST.TableLen; i++)
    {
        ST.elem[i] = rand() % 100;
    }
}
void ST_print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; i++)
    {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}

void swap(ElemType& a, ElemType& b)
{
    ElemType tmp;
    tmp = a;
    a = b;
    b = tmp;
}
//冒泡排序
void BubbleSort(ElemType A[], int n) {
    //外层控制已经排序的个数
    int flag;
    for (int i = 0; i < n - 1; i++) {
        flag = 0;
        //内层负责比较
        for (int j = 0; j < n - i - 1; j++) {
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
                flag = 1;
            }
        }
        if (flag == 0) {
            break;
        }
    }
}
//快速排序递归
int Partition(ElemType arr[], int left, int right) {
    int i = left;
    int j = left;
    for (i; i < right ; i++) {
        if (arr[i] < arr[right]) {
            swap(arr[j], arr[i]);
            j++;
        }
    }
    swap(arr[j], arr[right]);
    return j;
}

//递归实现
//以分割的最后一个来比较
void QuickSort(ElemType A[], int low, int high)
{
    if (low < high)
    {
        int pivotpos = Partition(A, low, high);//分割点左边的元素都比分割点要小，右边的比分割点大
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}
int main() {
    SSTable ST;
    ElemType A[10] = { 64, 94, 95, 79, 69, 84, 18, 22, 12 ,78 };
    ST_Init(ST, 10);//初始化
    memcpy(ST.elem, A, sizeof(A));
    ST_print(ST);
    BubbleSort(ST.elem,10);
    ST_print(ST);
    QuickSort(ST.elem, 0, 9);
    ST_print(ST);
    return 0;
}
快速排序.png

插入排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct {
    ElemType* elem;//整型指针
    int TableLen;
}SSTable;

void ST_Init(SSTable& ST, int len)
{
    ST.TableLen = len + 1;//实际申请11个元素的空间
    ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    int i;
    srand(time(NULL));
    for (i = 0; i < ST.TableLen; i++)
    {
        ST.elem[i] = rand() % 100;//随机了11个数，但是第一个元素是没有用到的
    }
}
void ST_print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; i++)
    {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}
//插入排序，从小到大排序，升序
void InsertSort(ElemType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        //后面小于前面才需要排
        if (A[i] < A[i - 1]) {
            //哨兵赋值
            A[0] = A[i];
            //将大于它的值后移
            for (j = i - 1;A[0]<A[j]; j--) {
                A[j + 1] = A[j];
            }
            //此时的j是前面的位置
            A[j + 1] = A[0];
        }
    }
}
//折半排序
void MidInsertSort(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++)
    {
        A[0] = A[i];
        low = 1; high = i - 1;
        while (low <= high)//先通过二分查找找到待插入位置
        {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for (j = i - 1; j >= high + 1; --j)
            A[j + 1] = A[j];
        A[high + 1] = A[0];
    }
}


int main()
{
    SSTable ST;
    ST_Init(ST, 10);//实际申请了11个元素空间
    ST_print(ST);
    InsertSort(ST.elem, 10);
    //MidInsertSort(ST.elem,10);
    //ShellSort(ST.elem,10);
    ST_print(ST);
    system("pause");
    return 0;
}

选择排序和堆排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
typedef int ElemType;
typedef struct {
    ElemType* elem;
    int TableLen;
}SSTable;

void ST_Init(SSTable& ST, int len)//申请空间，并进行随机数生成
{
    ST.TableLen = len;
    ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
    int i;
    srand(time(NULL));
    for (i = 0; i < ST.TableLen; i++)
    {
        ST.elem[i] = rand() % 100;
    }
}
void ST_print(SSTable ST)
{
    for (int i = 0; i < ST.TableLen; i++)
    {
        printf("%3d", ST.elem[i]);
    }
    printf("\n");
}
void swap(ElemType& a, ElemType& b)
{
    ElemType tmp;
    tmp = a;
    a = b;
    b = tmp;
}
//简单选择排序
void SelectSort(ElemType A[], int n) {
    int i, j,min;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (A[min] > A[j]) {
                min = j;
            }
        }
        if (min != i) {
            swap(A[min], A[i]);
        }
    }
}
//k是父节点下标
//调整为最大堆
void AdjustDown(ElemType A[], int k, int len) {
    int dad = k;
    int son = 2 * dad + 1;
    while (son <= len) {
        if (son + 1 <= len && A[son + 1] > A[son]) {
            son++;
        }
        if (A[dad] < A[son]) {
            swap(A[dad], A[son]);
            //如何后续有孩子就需要排
            dad = son;
            son = 2 * dad + 1;
        }
        else {
            break;
        }
    }
}

//len相对于长度，更像下标
void HeapSort(ElemType A[], int len) {
    int i;
    //最后一个父节点的位置i，开始整为最大堆
    for (i = len / 2 ; i >= 0; i--) {
        AdjustDown(A, i, len);
    }

    for (i = len; i >= 0; i--)
    {
        //第一个和最后一个做交换
        swap(A[i], A[0]);
        //除去最后一个重新生成大根堆
        AdjustDown(A, 0, i-1);
    }
}
//选择排序与堆排序
int main()
{
    SSTable ST;
    ElemType A[10] = { 64, 68, 95, 79, 69, 84, 18, 22, 12 ,99 };
    ST_Init(ST, 10);//初始化
    memcpy(ST.elem, A, sizeof(A));
    ST_print(ST);
    //SelectSort(ST.elem,10);
    HeapSort(ST.elem, 9);
    ST_print(ST);
    system("pause");
    return 0;
}

归并排序

#include <stdio.h>
#include <stdlib.h>

#define N 7
typedef int ElemType;


void Merge(ElemType A[], int low, int mid, int high) {
    ElemType B[N];
    int i, j, k;
    for (k = low; k <= high; k++)//复制元素到B中
        B[k] = A[k];

    //合并两个有序数组
    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[k++] = B[i++];
    while (j <= high)
        A[k++] = B[j++];
}

void MergeSort(ElemType 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);
    }
}


void print(int* a)
{
    for (int i = 0; i < N; i++)
    {
        printf("%3d", a[i]);
    }
    printf("\n");
}
// 归并排序
int main()
{
    int A[7] = { 49,38,65,97,76,13,27 };//数组，7个元素
    MergeSort(A, 0, 6);
    print(A);
    system("pause");
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容