表插入排序

代码

#include<iostream>
using namespace std;
#define LISTSIZE 13
typedef struct {
    int value;
    int next;
}LinkedList;

void initList(LinkedList list[],int num[],int count) {  //初始化循环链表
    list[0].value = INT32_MAX;
    list[0].next = 1;
    for (int i = 0; i < count; i++) {  //数组的元素按顺序存入list数组1-13位置，next全为0
        list[i + 1].value = num[i];
        list[i + 1].next = 0;
    }
}
void sortList(LinkedList list[]) {  //根据数组数据对循环链表进行排序
    int pre, num;   //list数组1和1位置未有序序列的循环列表，将余下元素插入
    for (int i = 2; i < LISTSIZE; i++) {
        num=pre = 0;
        while (list[i].value<list[num].value) //每次都与先于预设的最大值比较
        {
            pre = num;
            num = list[num].next;
            if (num == 0) {//防止list[i].value比前面的数字都小而进入死循环
                break;
            }
        }
        list[i].next = list[pre].next;
        list[pre].next = i;
    }
    //排序之后list数组应该是降序的
}
void result(LinkedList list[], int num[],int n) {  //将已排序的结果赋给数组
    int j = list[0].next;
    for (int i = n - 1; i >= 0; i--) {  //将元素按照升序序列存入数组中
        num[i] = list[j].value;
        j = list[j].next;
    }
}
void main(){
    int num[12] = { 10,6,2,33,15,12,23,76,1,54,22,9 };
    LinkedList list[LISTSIZE];
    initList(list, num, 12);
    sortList(list);
    result(list, num, 12);
    for (auto x : num) {
        cout << x << " ";
    }
    cout << endl;
    system("pause");
}

---

本文总阅读量次 本站访客数人次