内排序
第一题：直接选择排序
[问题描述]
设计一个用链表表示的直接选择排序算法，并用程序实现。
[输入]
待排序的个数n，以及待排序的元素值。
[输出]
n个由小到大排列的结果。
[存储结构]
链式存储。
[算法的基本思想]
直接选择排序：
算法说明：已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，用r来指示。r以前为已排序序列，r以后为未排序序列。再从未排序序列中找出最小结点与r交换元素。反复执行这个过程，直到排好序。
#include<stdio.h> #include<malloc.h> #define NULL 0 typedef struct LNode{ int value; struct LNode *next; }LNode, *node; void initLNode(node &head, int n){ //创建链表 head = (node)malloc(sizeof(LNode)); //创建头指针 int i; node p; p = head; for(i = 0; i < n; i++){ //中间结点创建 node q = (node) malloc(sizeof(LNode)); printf("请输入排序元素："); scanf("%d", &q->value); p->next = q; p = q; } p->next = NULL; //尾指针设置 } void selectSort(node &head){ //选择排序 int temp; node r; //用来记录第一个无序 node q; //用来遍历 r = head->next; while(r->next != NULL){ //判断r是否为尾结点 q = r->next; //q为r后的无序序列 while(q != NULL){ //找出无序序列中最小的元素 if(q->value < r->value){ temp = q->value; q->value = r->value; r->value = temp; } q = q->next; } r = r->next; } } void show(node head){ //遍历显示排序完成的链表 node p; p = head->next; while(p != NULL){ printf("%d", p->value); p = p->next; } } int main(){ printf("请输入要排序的个数："); int n; scanf("%d", &n); node head; initLNode(head, n); selectSort(head); show(head); }
结构演示：
结果与分析：
优点：通过交换数据而不是移动指针实现简单选择排序，缺点：时间复杂度较高，不具有稳定性，时间复杂度O(n²)，空间复杂度O（n）n为待排序的个数
第二题：快速排序
[问题描述]
对N个关键字取整数的记录进行整序，以使所有关键字为非负数的记录排在关键字为负数的记录之前，要求使用最少的附加空间，且算法的时间复杂度为O(N)。
[输入]
待排序的个数n，以及待排序的元素值。
[输出]
n个数，负数在前，非负数在后。
[存储结构]
顺序存储。
[算法的基本思想]
交换排序（快速排序）。
算法说明：使用0作为枢纽进行一次划分，小于0即负数移动到数组的左边，大于0，移动到数组的右边，只需对数组进行一次遍历，时间复杂度为N。
#include<stdio.h> void swap(int num[], int n){ int low = 1; //双下标,遍历数组 int high = n; while(low < high){ //high与low轮番移动 //while中的两个while需要时刻满足外层while的条件 while(num[high] > 0 && low < high){ //先移动high high--; } num[0] = num[high]; while(num[low] < 0 && low < high){ low++; } num[high] = num[low]; num[low] = num[0]; } } int main(){ printf("请输入数组规模："); int n; scanf("%d", &n); int num[n + 1]; //n[0]作为辅助空间 int i; for(i = 1; i <= n; i++){ printf("请输入数据："); scanf("%d", &num[i]); } swap(num, n); for(i = 1; i <= n; i++){ printf("%d ", num[i]); } }
结构演示：
结果与分析：
优点：时间复杂度底，缺点：不具有稳定性，时间复杂度O(n)，空间复杂度O（n）n为待排序的个数
心得
- 通过链表的选择排序：可只交换数据而不是移动指针实现简单选择排序
- 单次交换排序，可以进行元素的划分
