[数据结构与算法] 数据结构排序算法

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构排序算法 -> 正文阅读

[数据结构与算法]数据结构排序算法

顺序结构实现排序算法

排序实现代码段：

直接插入排序

顺序表实现

struct ARRAY_LIST{
    int index;
    int data[MAX_LEN];
};

void InsertSort(struct ARRAY_LIST *arr){

    int i,j;

    for(i = 2; i < arr->index; i++){
        if(arr->data[i] < arr->data[i-1]){
            //此时需要将其插入有序表
            //1、首先复制哨兵
            arr->data[0] = arr->data[i];
            
            for(j = i-1; arr->data[0] < arr->data[j]; j--){
                //２、后移，找到哨兵插入的正确位置
                arr->data[j+1] = arr->data[j];
            }

            //３、插入哨兵
            arr->data[j+1] = arr->data[0];
        }
    }
    
}

链表实现

typedef struct LINKNODE
{
    int value;
    struct LINKNODE *next;
} *NODE;

//直接插入排序
void InsertSort(NODE head){

    NODE p,pre,h;

    //1、将原链表断裂成两个链表，一个为有序链表，另一个为待排序的链表，其中将原链表的第一个节点视为有序的链表
    h = head->next->next;
    head->next->next = NULL;

    //2、从待排序的链表中每次取一个节点插入到有序链表中
    while(h != NULL){
        p = h->next;
        pre = head;
        while(pre->next != NULL && pre->next->value < h->value){
            pre = pre->next;
        }
        h->next = pre->next;
        pre->next = h;
        h = p;
    }
}

希尔排序

struct ARRAY_LIST{
    int index;
    int data[MAX_LEN];
};

struct SHELL_DL{
    int dl[MAX_LEN];
    int len;
};

//希尔插入排序，dl为每次的步长
void ShellInsert(struct ARRAY_LIST *arr,int dl){

    int i,j;

    for(i = dl+1 ; i < arr->index; i++){
        if(arr->data[i] < arr->data[i-dl]){
            //此时需要将其插入有序表
            //1、首先复制哨兵
            arr->data[0] = arr->data[i];
            
            for(j = i-dl; arr->data[0] < arr->data[j]; j=j-dl){
                //２、后移，找到哨兵插入的正确位置
                arr->data[j+dl] = arr->data[j];
            }

            //３、插入哨兵
            arr->data[j+dl] = arr->data[0];
        }
    }
}

//希尔排序，就是直接插入加了个步长
void ShellSort(struct ARRAY_LIST *arr,struct SHELL_DL *dl){

    int i;

    for(i = 0; i < dl->len; i++){
        ShellInsert(arr,dl->dl[i]);
    }

}

冒泡排序

struct ARRAY_LIST{
    int index;
    int data[MAX_LEN];
};

//冒泡排序
void BubbleSort(struct ARRAY_LIST *arr){
    
    int i,j;
    int temp;
    printf("元素个数：%d\n",arr->index);

    for(i = 0; i < arr->index; i++){
        for(j = 0; j < arr->index-1-i; j++){
            if(arr->data[j] < arr->data[j+1]){
                temp = arr->data[j];
                arr->data[j] = arr->data[j+1];
                arr->data[j+1] = temp;
            }
        }
    }

}

快速排序

struct ARRAY_LIST{
    int index;
    int data[MAX_LEN];
};

//快速排序的一趟排序
int GetCenter(struct ARRAY_LIST *arr,int low,int high){

    int i;

    printf("low: %d\nhigh:%d\n",low,high);
    arr->data[0] = arr->data[low];

    while(low < high){
        while(low < high && arr->data[0] >= arr->data[high])
            high--;
        arr->data[low] = arr->data[high];
        while(low < high && arr->data[0] <= arr->data[low])
            low++;
        arr->data[high] = arr->data[low];
    }

    arr->data[low] = arr->data[0];
    printf("GetCenter　Finish\n");
    return low;
}

//快速排序
void QuickSort(struct ARRAY_LIST *arr,int low,int high){

    int center;

    center = GetCenter(arr, low, high);
    printf("center: %d\nlow:%d\nhigh:%d\n",center,low,high);

    if(low < high){

        QuickSort(arr, center+1, high);
        QuickSort(arr, low, center-1);
    
    }

}

简单选择排序

顺序实现

//交换排序　简单选择排序
void SelectSort(struct ARRAY_LIST *arr){

    int i,j,k;
    int temp;

    for(i = 0; i < arr->index; i++){
        k = i;
        for( j = i; j < arr->index; j++){
            if(arr->data[k] < arr->data[j])
                k = j;
        }
        if(k != i){
            temp = arr->data[i];
            arr->data[i] = arr->data[k];
            arr->data[k] = temp;
        }
    }

}

链表实现

typedef struct LINKNODE
{
    int value;
    struct LINKNODE *next;
} *NODE;

//获取最小节点
NODE GetMin(NODE h){

    NODE min;

    min = h;
    while(h){
        if(min->value > h->value){
            min = h;
        }
        h = h->next;
    }

    return min;
}
//简单选择排序
void SelectSort(NODE head){

    NODE p;
    NODE min;
    int temp;
    //1、遍历链表每次取最值与当前节点交换
    p = head->next;
    while(p != NULL){
    
        min = GetMin(p);
		//交换位置
        temp = p->value;
        p->value = min->value;
        min->value = temp;
    
        p = p->next;
    }

}

测试代码汇总

顺序

其中需要用哨兵的算法使用init2()初始化顺序表，包括：直接插入、希尔、快速

/**
 * @file        testsqlist.c
 * @brief       顺序表实现排序
 *              
 * @author      UncleBb
 * @version     0.0.0.1
 * @date        2021/12/10
 */

#include <stdio.h>
#define MAX_LEN 20

struct ARRAY_LIST{
    int index;
    int data[MAX_LEN];
};

struct SHELL_DL{
    int dl[MAX_LEN];
    int len;
};

void init(struct ARRAY_LIST *arr){

    if(NULL == arr){
        return;
    }
    arr->index = 0;

}

//用于直接插入排序的初始化，带哨兵
void init2(struct ARRAY_LIST *arr){

    if(NULL == arr){
        return;
    }
    arr->index = 1;
    arr->data[0] = 0;

}

void InitBl(struct SHELL_DL *dl){
    dl->len = 3;
    dl->dl[0] = 3;
    dl->dl[1] = 2;
    dl->dl[2] = 1;
}

void add(struct ARRAY_LIST *arr,int value){

    if(arr->index == MAX_LEN){
        printf("顺序表已满，无法插入!\n");
        return;
    }
    arr->data[arr->index] = value;
    arr->index ++;

}

void out(struct ARRAY_LIST *arr){

    int i;
    i = 0;
    while (i < arr->index)
    {
        printf("%d ",arr->data[i]);
        i++;
    }
    printf("\n");

}

//冒泡排序
void BubbleSort(struct ARRAY_LIST *arr){
    
    int i,j;
    int temp;
    printf("元素个数：%d\n",arr->index);

    for(i = 0; i < arr->index; i++){
        for(j = 0; j < arr->index-1-i; j++){
            if(arr->data[j] < arr->data[j+1]){
                temp = arr->data[j];
                arr->data[j] = arr->data[j+1];
                arr->data[j+1] = temp;
            }
        }
    }

}

//直接插入排序，使用哨兵
void InsertSort(struct ARRAY_LIST *arr){

    int i,j;

    for(i = 2; i < arr->index; i++){
        if(arr->data[i] < arr->data[i-1]){
            //此时需要将其插入有序表
            //1、首先复制哨兵
            arr->data[0] = arr->data[i];
            
            for(j = i-1; arr->data[0] < arr->data[j]; j--){
                //２、后移，找到哨兵插入的正确位置
                arr->data[j+1] = arr->data[j];
            }

            //３、插入哨兵
            arr->data[j+1] = arr->data[0];
        }
    }
    
}

//希尔插入排序，dl为每次的步长
void ShellInsert(struct ARRAY_LIST *arr,int dl){

    int i,j;

    for(i = dl+1 ; i < arr->index; i++){
        if(arr->data[i] < arr->data[i-dl]){
            //此时需要将其插入有序表
            //1、首先复制哨兵
            arr->data[0] = arr->data[i];
            
            for(j = i-dl; arr->data[0] < arr->data[j]; j=j-dl){
                //２、后移，找到哨兵插入的正确位置
                arr->data[j+dl] = arr->data[j];
            }

            //３、插入哨兵
            arr->data[j+dl] = arr->data[0];
        }
    }
}

//希尔排序，就是直接插入加了个步长
void ShellSort(struct ARRAY_LIST *arr,struct SHELL_DL *dl){

    int i;

    for(i = 0; i < dl->len; i++){
        ShellInsert(arr,dl->dl[i]);
    }

}

//快速排序的一趟排序
int GetCenter(struct ARRAY_LIST *arr,int low,int high){

    int i;

    printf("low: %d\nhigh:%d\n",low,high);
    arr->data[0] = arr->data[low];

    while(low < high){
        while(low < high && arr->data[0] >= arr->data[high])
            high--;
        arr->data[low] = arr->data[high];
        while(low < high && arr->data[0] <= arr->data[low])
            low++;
        arr->data[high] = arr->data[low];
    }

    arr->data[low] = arr->data[0];
    printf("GetCenter　Finish\n");
    return low;
}

//快速排序
void QuickSort(struct ARRAY_LIST *arr,int low,int high){

    int center;

    center = GetCenter(arr, low, high);
    printf("center: %d\nlow:%d\nhigh:%d\n",center,low,high);

    if(low < high){

        QuickSort(arr, center+1, high);
        QuickSort(arr, low, center-1);
    
    }

}

//交换排序　简单选择排序
void SelectSort(struct ARRAY_LIST *arr){

    int i,j,k;
    int temp;

    for(i = 0; i < arr->index; i++){
        k = i;
        for( j = i; j < arr->index; j++){
            if(arr->data[k] < arr->data[j])
                k = j;
        }
        if(k != i){
            temp = arr->data[i];
            arr->data[i] = arr->data[k];
            arr->data[k] = temp;
        }
    }

}

int main(){

    struct ARRAY_LIST arr;
    struct SHELL_DL dl;

    init(&arr);

    add(&arr,5);
    add(&arr,3);
    add(&arr,4);
    add(&arr,1);
    add(&arr,10);
    add(&arr,21);
    add(&arr,13);
    add(&arr,14);

    printf("排序前：");
    out(&arr);

    // InsertSort(&arr);
    // InitBl(&dl);

    BubbleSort(&arr);
    // ShellSort(&arr,&dl);
    // QuickSort(&arr,1,8);
    // SelectSort(&arr);

    printf("排序后：");
    out(&arr);
    
}

链表

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

typedef struct LINKNODE
{
    int value;
    struct LINKNODE *next;
} *NODE;

int headadd(struct LINKNODE *head,int value){

    struct LINKNODE *node;
    struct LINKNODE *p;

    p = head->next;
    node = malloc(sizeof(struct LINKNODE));
    node->value = value;
    head->next = node;
    node->next = p;

}

int out(struct LINKNODE *linklist){

    if(linklist == NULL){
        printf("链表为空");
        return 0;
    }

    struct LINKNODE *node;

    node = linklist->next;
    while (node != NULL)
    {
        printf("%d ",node->value);
        node = node->next;
    }

    printf("\n");
}

struct LINKNODE *init(struct LINKNODE *head){

    struct LINKNODE *p;

    p = malloc(sizeof(struct LINKNODE));
    if(p == NULL){
        printf("Fail to malloc memory!\n");
        return NULL;
    }

    head = p;
    p->next = NULL;
    
    return head;
}

int delete(struct LINKNODE **head){

    NODE p;

    while((*head) != NULL){

        p = *head;
        *head = (*head)->next;
        free(p);

    }

}

struct LINKNODE *add(struct LINKNODE *head,int value){

    struct LINKNODE *node;
    struct LINKNODE *p;

    node = malloc(sizeof(struct LINKNODE));
    node->value = value;
    node->next = NULL;

    p = head;
    while(p->next != NULL){
        p = p->next;
    }
    p->next = node;

    return head;

}

int add2(struct LINKNODE **head,int value){

    struct LINKNODE *node;
    struct LINKNODE *p;

    node = malloc(sizeof(struct LINKNODE));
    node->value = value;

    p = (*head)->next;
    (*head)->next = node;
    node->next = p;

}

//直接插入排序
void InsertSort(NODE head){

    NODE p,pre,h;

    //1、将原链表断裂成两个链表，一个为有序链表，另一个为待排序的链表，其中将原链表的第一个节点视为有序的链表
    h = head->next->next;
    head->next->next = NULL;

    //2、从待排序的链表中每次取一个节点插入到有序链表中
    while(h != NULL){
        p = h->next;
        pre = head;
        while(pre->next != NULL && pre->next->value < h->value){
            pre = pre->next;
        }
        h->next = pre->next;
        pre->next = h;
        h = p;
    }
}

//获取最小节点
NODE GetMin(NODE h){

    NODE min;

    min = h;
    while(h){
        if(min->value > h->value){
            min = h;
        }
        h = h->next;
    }

    return min;
}
//简单选择排序
void SelectSort(NODE head){

    NODE p;
    NODE min;
    int temp;
    //1、遍历链表每次取最值与当前节点交换
    p = head->next;
    while(p != NULL){
        min = GetMin(p);
        printf("p节点：%d 最值节点:%d\n",p->value,min->value);
        temp = p->value;
        p->value = min->value;
        min->value = temp;
        out(head);
        p = p->next;
    }

}

int main(){

    struct LINKNODE *head;  //头结点

    head = init(head);
    printf("开始添加\n");
    // head = add(head,1);
    // head = add(head,2);
    // head = add(head,3);
    add2(&head,5);
    add2(&head,3);
    add2(&head,4);
    add2(&head,1);
    add2(&head,10);
    add2(&head,21);
    add2(&head,13);
    add2(&head,14);

    printf("添加完成\n");
    out(head);
    SelectSort(head);
    printf("排序完成\n");
    out(head);
    delete(&head);
    printf("释放完成\n");
    out(head);

}