下载文档原格式
空间复杂度为o(n)的排序算法作为计算机科学中的一个重要概念，计算机算法旨在解决一系列问题。
其中，排序算法是最基本的算法之一。
排序算法可以将一组无序的数据按照一定的规则排列，从而更方便地进行查找和使用。
在计算机科学中，我们常常会涉及排序算法，而空间复杂度为 O(n) 的排序算法是最为实用和高效的一种。
下面，我们将分步骤阐述这种算法。
第一步：选择适合数据集合的排序算法首先，我们需要根据数据集合的规模和特点来选择合适的排序算法。
由于我们要实现的是空间复杂度为 O(n) 的排序算法，因此我们应该优先考虑基于比较的排序算法。
常见的基于比较的排序算法有冒泡排序、插入排序、归并排序和快速排序。
其中，冒泡排序、插入排序和归并排序均可以实现 O(n) 的空间复杂度，而快速排序则需要使用递归实现，空间复杂度较高，不适合本题。
第二步：实现基于链表的插入排序算法插入排序是一种简单但高效的排序算法，对于小规模数据集的排序特别有效。
对于大部分排序算法而言，空间复杂度往往是 O(nlogn) 或 O(n^2) 级别的，但插入排序却很特别，它的空间复杂度为 O(n)。
这使得插入排序成为实现本题的最佳选择。
基于链表的插入排序算法的核心思想是将无序的链表中的节点依次插入到新的有序链表中。
我们可以创建一个新的空链表，遍历原链表，将每个节点按照一定的规则插入到新链表中。
在这个过程中，我们需要维护一些指针和计数器以保证算法正确执行。
第三步：实现归并排序算法另一种基于比较的排序算法是归并排序。
归并排序的核心思想是将原始数据分成两个有序子序列，然后将这些子序列合并成一个大的有序序列。
归并排序算法也可以实现 O(n) 的空间复杂度，但它的时间复杂度一般为 O(nlogn)。
基于链表的归并排序算法实现过程与基于数组的实现过程类似，只是需要更多的指针和代码逻辑来维护链表的特殊结构。
第四步：测试和优化最后，我们需要对实现的排序算法进行测试和优化。
排序的实验报告范文数据结构实验报告实验名称：实验四排序学生姓名：班级：班内序号：学号：日期：2022年12月21日实验要求题目2使用链表实现下面各种排序算法，并进行比较。
排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据。
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）。
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。
编写测试main()函数测试线性表的正确性。
2、程序分析2.1存储结构说明：本程序排序序列的存储由链表来完成。
其存储结构如下图所示。
(1)单链表存储结构：结点地址：1000HA[2]结点地址：1000H1080H……头指针地址：1020HA[0]头指针地址：1020H10C0H……地址：1080HA[3]地址：1080HNULL……地址：10C0HA[1]地址：10C0H1000H……（2）结点结构tructNode{intdata;Node某ne某t;};示意图：intdataNode某ne某tintdataNode某ne某t2.2关键算法分析一：关键算法(一)直接插入排序voidLinkSort::InertSort()直接插入排序是插入排序中最简单的排序方法，其基本思想是：依次将待排序序列中的每一个记录插入到一个已排好的序列中，直到全部记录都排好序。
（1）算法自然语言1.将整个待排序的记录序列划分成有序区和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的记录；2.将无须去的第一个记录插入到有序区的合适位置中，从而使无序区减少一个记录，有序区增加一个记录；3.重复执行2，直到无序区中没有记录为止。
（2）源代码voidLinkSort::InertSort()//从第二个元素开始，寻找前面那个比它大的{Node某P=front->ne某t;//要插入的节点的前驱while(P->ne某t){Node某S=front;//用来比较的节点的前驱while(1){if(P->ne某t->data<S->ne某t->data)//P的后继比S的后继小则插入{inert(P,S);break;}S=S->ne某t;if(S==P)//若一趟比较结束，且不需要插入{P=P->ne某t;break;}}}}(3)时间和空间复杂度最好情况下，待排序序列为正序，时间复杂度为O（n）。
写出以单链表为存储结构的一组数据的简单选择排序算法。
以下是单链表存储结构的简单选择排序算法的实现:
```python
def selection_sort(link_list):
n = len(link_list)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if link_list[j] < link_list[min_idx]:
min_idx = j
link_list[i], link_list[min_idx] = link_list[min_idx], link_list[i]
return link_list
```
算法的基本思路是，遍历待排序的链表，找到未排序部分中的最小值，然后将该值与链表的第一个元素交换位置，然后再遍历剩余的元素，继续按照此方法进行排序，直到整个链表都被排序。
在上面的实现中，我们通过 `min_idx` 变量来保存当前未排序部分中的最小值的索引。
在第一次遍历时，min_idx 等于 i，因为在未排序部分中，第一个元素通常是最小的。
在后续的遍历中，我们不断地寻找未排序部分中的最小值，并将其与链表的第一个元素交换位置，最后返回排好序的链表。
设计两个有序单链表的合并排序算法有序单链表的合并排序，是一种高效的排序算法，可以在较短的时间内对大量数据进行排序。
这种排序算法的核心在于将两个有序的单链表合并成一个有序的单链表，然后再对整个链表进行排序。
合并排序算法的基本原理是分治法。
将需要排序的数组不断地分解成两个子数组，直到每个子数组只包含一个元素为止。
然后再将这些子数组两两合并，直到整个数组被合并成一个有序的数组为止。
这里介绍两个有序单链表的合并排序算法，它们分别是迭代算法和递归算法。
1. 迭代算法迭代算法是一种通用的算法，它的思路是利用循环结构来重复执行一段相同或相似的代码，从而解决一类问题。
对于有序单链表的合并排序，迭代算法的基本思路是将两个有序单链表的元素依次比较，然后将较小的元素加入到新的链表中，直到两个链表中的元素全部被加入到新链表中为止。
以下是迭代算法的具体实现过程：```// 合并两个有序单链表Node* mergeList(Node* head1, Node* head2) { // 新建一个头结点Node* dummy = new Node(-1);// 定义两个指针，分别指向两个链表的头结点 Node* p = head1;Node* q = head2;// 定义一个指针，指向新链表的最后一个节点 Node* curr = dummy;// 循环比较两个链表中的元素while (p != nullptr && q != nullptr) {if (p->val <= q->val) {curr->next = p;p = p->next;} else {curr->next = q;q = q->next;}curr = curr->next;}// 将剩余的元素加入到新链表中curr->next = p != nullptr ? p : q;// 返回新链表的头结点return dummy->next;}// 归并排序Node* mergeSort(Node* head) {if (head == nullptr || head->next == nullptr) {return head;}// 定义两个指针，一个快指针每次走两步，一个慢指针每次走一步 Node* slow = head;Node* fast = head->next;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}// 将链表分成两部分Node* head1 = head;Node* head2 = slow->next;slow->next = nullptr;// 分别对两部分链表进行归并排序head1 = mergeSort(head1);head2 = mergeSort(head2);// 合并两个有序单链表return mergeList(head1, head2);}```2. 递归算法递归算法的思想是将一个大问题分解成若干个小问题，然后逐个解决这些小问题，最终得到大问题的解决方案。
c语言链表排序算法在C语言中，链表的排序可以使用多种算法，如插入排序、归并排序、快速排序等。
以下是一个简单的插入排序算法的示例，用于对链表进行排序：C：#include<stdio.h>#include<stdlib.h>struct Node {int data;struct Node* next;};void insert(struct Node** head, int data) {struct Node* newNode= (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;if (*head == NULL) {*head = newNode;return;}struct Node* current = *head;while (current->next != NULL) {current = current->next;}current->next = newNode;}void sortList(struct Node** head) { struct Node* current = *head;while (current != NULL) {struct Node* next = current->next; while (next != NULL) {if (current->data > next->data) { int temp = current->data;current->data = next->data;next->data = temp;}next = next->next;}current = current->next;}}void printList(struct Node* head) { while (head != NULL) {printf("%d ", head->data);head = head->next;}}int main() {struct Node* head = NULL;insert(&head, 5);insert(&head, 2);insert(&head, 4);insert(&head, 1);insert(&head, 3);printf("Before sorting: ");printList(head);sortList(&head);printf("\nAfter sorting: ");printList(head);return0;}这个程序定义了一个链表节点结构体Node，其中包含一个整型数据data 和一个指向下一个节点的指针next。
链表排序（冒泡、选择、插⼊、快排、归并、希尔、堆排序）这篇⽂章分析⼀下链表的各种排序⽅法。
以下排序算法的正确性都可以在LeetCode的这⼀题检测。
本⽂⽤到的链表结构如下（排序算法都是传⼊链表头指针作为参数，返回排序后的头指针）struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}};插⼊排序（算法中是直接交换节点，时间复杂度O（n^2）,空间复杂度O（1））class Solution {public:ListNode *insertionSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.if(head == NULL || head->next == NULL)return head;ListNode *p = head->next, *pstart = new ListNode(0), *pend = head;pstart->next = head; //为了操作⽅便，添加⼀个头结点while(p != NULL){ListNode *tmp = pstart->next, *pre = pstart;while(tmp != p && p->val >= tmp->val) //找到插⼊位置{tmp = tmp->next; pre = pre->next;}if(tmp == p)pend = p;else{pend->next = p->next;p->next = tmp;pre->next = p;}p = pend->next;}head = pstart->next;delete pstart;return head;}};选择排序（算法中只是交换节点的val值，时间复杂度O（n^2）,空间复杂度O（1））class Solution {public:ListNode *selectSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//选择排序if(head == NULL || head->next == NULL)return head;ListNode *pstart = new ListNode(0);pstart->next = head; //为了操作⽅便，添加⼀个头结点ListNode*sortedTail = pstart;//指向已排好序的部分的尾部while(sortedTail->next != NULL){ListNode*minNode = sortedTail->next, *p = sortedTail->next->next;//寻找未排序部分的最⼩节点while(p != NULL){if(p->val < minNode->val)minNode = p;p = p->next;}swap(minNode->val, sortedTail->next->val);sortedTail = sortedTail->next;}head = pstart->next;delete pstart;return head;}};快速排序1（算法只交换节点的val值，平均时间复杂度O（nlogn）,不考虑递归栈空间的话空间复杂度是O（1））这⾥的partition我们参考(选取第⼀个元素作为枢纽元的版本，因为链表选择最后⼀元素需要遍历⼀遍)，具体可以参考这⾥我们还需要注意的⼀点是数组的partition两个参数分别代表数组的起始位置，两边都是闭区间，这样在排序的主函数中：void quicksort(vector<int>&arr, int low, int high){if(low < high){int middle = mypartition(arr, low, high);quicksort(arr, low, middle-1);quicksort(arr, middle+1, high);}}对左边⼦数组排序时，⼦数组右边界是middle-1，如果链表也按这种两边都是闭区间的话，找到分割后枢纽元middle，找到middle-1还得再次遍历数组，因此链表的partition采⽤前闭后开的区间（这样排序主函数也需要前闭后开区间），这样就可以避免上述问题class Solution {public:ListNode *quickSortList(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.//链表快速排序if(head == NULL || head->next == NULL)return head;qsortList(head, NULL);return head;}void qsortList(ListNode*head, ListNode*tail){//链表范围是[low, high)if(head != tail && head->next != tail){ListNode* mid = partitionList(head, tail);qsortList(head, mid);qsortList(mid->next, tail);}}ListNode* partitionList(ListNode*low, ListNode*high){//链表范围是[low, high)int key = low->val;ListNode* loc = low;for(ListNode*i = low->next; i != high; i = i->next)if(i->val < key){loc = loc->next;swap(i->val, loc->val);}swap(loc->val, low->val);return loc;}};快速排序2（算法交换链表节点，平均时间复杂度O（nlogn）,不考虑递归栈空间的话空间复杂度是O（1））这⾥的partition，我们选取第⼀个节点作为枢纽元，然后把⼩于枢纽的节点放到⼀个链中，把不⼩于枢纽的及节点放到另⼀个链中，最后把两条链以及枢纽连接成⼀条链。
linkhashmap排序原理1.简介在计算机科学中，链式哈希映射(li nk edh a sh ma p)是一种特殊的散列表，它维护了键值对的插入顺序，并提供了按照插入顺序进行遍历的功能。
本文将介绍链式哈希映射的排序原理及其应用。
2.哈希映射的基本概念哈希映射是一种将键(k ey)与值(va lu e)相关联的数据结构。
通过散列函数将键映射到特定的存储位置，以实现快速的查找和访问。
3.链式哈希映射的概述链式哈希映射是在传统哈希映射的基础上添加了排序功能。
它使用一个散列表存储键值对，并在散列表的基础上维护一个双向链表，用于记录插入顺序。
每个节点包含键、值以及指向前一个节点和后一个节点的指针。
4.插入操作链式哈希映射的插入操作分为以下几个步骤：1.根据给定的键计算哈希值。
2.根据哈希值定位到对应的散列表桶。
3.在对应的桶中查找是否存在相同的键。
-如果存在，更新对应的值。
-如果不存在，创建一个新的节点。
4.将新节点插入到散列表桶中。
5.更新链表中的节点指针，使其按照插入顺序连接。
5.排序原理链式哈希映射的排序是通过双向链表实现的。
它可以按照插入顺序遍历键值对，也可以按照其他规则进行排序。
以下是链式哈希映射的排序原理：1.默认情况下，链式哈希映射按照插入顺序进行遍历。
2.当需要按照其他规则进行排序时，可以调用排序方法。
3.排序方法会重新组织链表中的节点顺序，以满足指定的排序规则。
-常见的排序规则包括升序、降序等。
4.排序方法可以通过比较节点的键的大小来实现排序。
5.在排序过程中，可以利用快速排序、归并排序等常用的排序算法来提高效率。
6.应用场景链式哈希映射的排序功能可以在很多场景中得到应用，包括但不限于以下几个方面：1.缓存替换算法：根据某种策略对缓存中的数据项进行排序，以决定替换的优先级。
2.操作日志记录：记录用户操作日志并按照时间顺序进行排序，便于后续查看和分析。
3.数据库索引优化：为数据库中的数据建立排序索引，提高数据检索的效率。
linkedhashmap 排序的原理LinkedHashMap排序原理LinkedHashMap是一种在HashMap的基础上增加了链表的结构，用于保证遍历顺序与插入顺序相同的数据结构。
在LinkedHashMap中，插入顺序被定义为按元素插入的顺序，而遍历顺序可以是插入顺序或者访问顺序，其中访问顺序是由accessOrder属性来决定的，当accessOrder为true时，访问到的元素会被调整到链表的尾部，以便于实现LRU缓存。
LinkedHashMap是如何排序的呢？其排序原理可以简单描述如下：1. 链表结构LinkedHashMap内部维护了一个双向链表，所有元素在插入和删除时，都会被添加到双向链表的末尾。
2. 访问顺序当accessOrder为true时，访问到的元素会被调整到链表的尾部，以便于实现LRU缓存。
3. 迭代器遍历在LinkedHashMap中使用迭代器遍历元素时，会按照链表的顺序进行遍历。
当对元素进行修改、删除或增加时，都会改变链表的顺序，因此迭代器遍历顺序也会发生变化。
4. 排序算法排序算法在LinkedHashMap中主要体现在entrySet()方法中，该方法返回的是一个Set集合，其中元素按照插入顺序或者访问顺序排序。
在LinkedHashMap中，entrySet()方法会直接遍历双向链表，从而返回按元素插入的顺序或者访问顺序排序的Set集合。
总体来说，LinkedHashMap的排序原理主要是由链表结构、访问顺序和排序算法共同决定的。
因此在使用LinkedHashMap时，需要注意设置accessOrder属性来控制访问顺序，以便于实现LRU缓存。
同时，对于需要使用遍历方法来对元素进行排序的情况，需要使用entrySet()方法，并保证元素的插入和访问顺序。
冒泡排序链表c语言冒泡排序是一种简单而常用的排序算法，它可以用于对链表进行排序。
在本文中，我们将介绍如何使用C语言实现冒泡排序链表，并解释算法的原理和步骤。
让我们来了解一下冒泡排序的基本原理。
冒泡排序通过多次遍历待排序的元素，比较相邻的两个元素的大小，并根据需要交换它们的位置。
通过这样的比较和交换，最大（或最小）的元素会逐渐“冒泡”到列表的末尾（或开头），从而实现排序。
在链表中实现冒泡排序的思路与数组类似，但需要注意的是，我们无法像数组那样通过下标直接访问链表中的元素。
因此，在链表中进行元素比较和交换时，我们需要修改节点之间的连接关系。
下面是使用C语言实现冒泡排序链表的步骤：1. 遍历链表，确定链表的长度。
这一步是为了确定需要进行多少次排序遍历。
2. 写一个循环，循环次数为链表的长度减1。
每次循环都进行一次完整的遍历和排序。
3. 在每次遍历中，从链表的头部开始，比较相邻节点的值。
如果前一个节点的值大于后一个节点的值，则交换它们的位置。
4. 重复步骤3，直到遍历到链表的倒数第二个节点。
这样可以确保在每次遍历后，链表的最后一个节点都是当前遍历范围内的最大（或最小）值。
5. 重复步骤2和步骤3，直到完成所有的排序遍历。
此时，链表中的元素已经按照从小到大（或从大到小）的顺序排列好了。
以下是冒泡排序链表的C语言代码实现：```c#include <stdio.h>// 定义链表节点的结构体typedef struct Node {int data;struct Node* next;} Node;// 冒泡排序链表的函数void bubbleSortList(Node* head) {if (head == NULL || head->next == NULL) {return;}int len = 0;Node* cur = head;while (cur != NULL) {len++;cur = cur->next;}for (int i = 0; i < len - 1; i++) {cur = head;for (int j = 0; j < len - i - 1; j++) {if (cur->data > cur->next->data) { int temp = cur->data;cur->data = cur->next->data; cur->next->data = temp;}cur = cur->next;}}}// 打印链表的函数void printList(Node* head) {Node* cur = head;while (cur != NULL) {printf("%d ", cur->data);cur = cur->next;}printf("\n");}int main() {// 创建链表Node* head = (Node*)malloc(sizeof(Node)); Node* node1 = (Node*)malloc(sizeof(Node)); Node* node2 = (Node*)malloc(sizeof(Node)); Node* node3 = (Node*)malloc(sizeof(Node)); head->data = 3;node1->data = 2;node2->data = 4;node3->data = 1;head->next = node1;node1->next = node2;node2->next = node3;node3->next = NULL;// 打印排序前的链表printf("排序前的链表：");printList(head);// 对链表进行冒泡排序bubbleSortList(head);// 打印排序后的链表printf("排序后的链表：");printList(head);return 0;}```在上面的代码中，我们首先定义了一个链表节点的结构体，其中包含一个整型数据成员和一个指向下一个节点的指针成员。
二路归并排序的链式实现-回复什么是归并排序？归并排序（Merge Sort）是一种基于分治法的经典排序算法。
该算法将待排序的序列拆分成若干个子序列，分别对每个子序列进行排序，然后再将已排序的子序列合并成更大的有序序列，直到全部元素都被合并成一个有序序列为止。
归并排序采用了分治的思想，能够有效地解决大规模数据的排序问题。
为什么要使用归并排序？归并排序具有以下几个优点：1. 稳定性：由于归并排序是通过合并已排序的子序列来排序，因此相等元素的相对位置不会改变，保持了原有序列中相同元素之间的顺序。
2. 适应性：归并排序适用于各种类型的数据，以及各种大小的数据集。
3. 均匀性：归并排序相对于其他排序算法来说，在最坏情况下的时间复杂度也是相对较低的，具有较好的平均性能。
如何进行归并排序的链式实现？下面将介绍归并排序的链式实现方法。
首先，我们需要定义一个链表节点的数据结构，用于保存排序的数据和链接下一个节点。
这个节点结构可以包含两个部分：数据元素和下一个节点的指针。
然后，我们需要实现归并排序算法的核心函数：MergeSort。
这个函数将分为两个步骤：拆分和合并。
拆分步骤：1. 首先，判断链表是否为空或只有一个节点，如果是，则无需排序，直接返回。
2. 如果链表中有多个节点，则使用快慢指针法将链表一分为二。
快指针每次走两步，慢指针每次走一步，直到快指针到达链表尾部。
此时慢指针所指的位置即为链表的中间位置。
3. 将链表从中间位置断开，得到两个子链表。
4. 递归地对两个子链表分别调用MergeSort函数进行拆分，并将结果重新连接起来。
合并步骤：1. 定义一个辅助函数Merge，用于合并两个已排序的链表。
2. 创建一个新的链表作为合并结果的头节点，并初始化两个指针分别指向两个链表的头节点。
3. 通过比较两个链表当前指针所指的元素大小，将较小的元素插入到新链表的尾部，并移动相应的指针。
4. 重复上述步骤，直到有一个链表的所有元素都已插入到新链表中。
数据结构实验报告实验名称：实验三排序学生姓名：班级：班内序号：15学号：日期：2016.12.191．实验要求题目2使用链表实现下面各种排序算法，并进行比较。
排序算法：1、插入排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：1、测试数据分成三类：正序、逆序、随机数据2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）4、对2和3的结果进行分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性2. 程序分析2.1 存储结构我使用了线性表的链式存储结构，通过建立双向循环链表进行顺序存取。
每个节点分为data、next、previor。
data域称为数据域，数据通过node结构存储待排序的信息；next为指针域，用来储存直接后继的地址；prior为指针域，用来储存直接前继的地址；struct Node{int data;struct Node*next;struct Node*previor;};2.2 程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流{private:Node* partion(Node*first,Node*end); //快速排序一趟public:Node*front;int comparision; //比较次数int movement; //移动次数LinkList() //无参构造{front = new Node;front->next = NULL;front->previor = NULL;comparision = movement = 0;}LinkList(int a[],int n); //构造函数:建立双向链表void insertsort(); //插入排序void bubblesort(); //冒泡排序void Qsort(Node*x,Node*y); //快速排序void selectsort(); //简单选择排序void show(); //显示排序结果~LinkList(); //析构函数};2.3 关键算法分析构造函数：通过使用头插法建立双向链表，其关键是多设一个指针变量用于储存上一个末节点的地址，这样才能使节点指向其上一个节点。
在这次排序实验中，使用双向循环链表更方便进行遍历操作。
LinkList::LinkList(int a[],int n){front = new Node;front->next = NULL;front->previor = NULL;comparision = movement = 0;Node*x = new Node;Node*s = new Node;s->data = a[n - 1];s->next = front;s->previor = front;front->next = s;front->previor = s;x = s;for (int i = n - 2; i >= 0; i--){Node*s = new Node;s->data = a[i];s->next = front->next;s->previor = front;front->next = s;x->previor = s;x = s;}}插入排序函数：将front头节点当作哨兵。
从第二个有效节点开始进行插入，进行边查找，边后移的操作。
void LinkList::insertsort(){Node*p = front->next;Node*s = p->next;while (s!=front){if (s->data < p->data){comparision++;front->data = s->data;movement++;Node*x = p;Node*y = s;while (front->data < x->data){comparision++;y->data = x->data;movement++;x = x->previor;y = y->previor;}y->data = front->data;movement++;}comparision++;p = p->next;s = s->next;}}冒泡排序函数：每一次内循环边比较边交换，将无序区中最大的数放入有序区中，并记录无序元素的范围。
当无序元素指向front时即整体排序完成。
void LinkList::bubblesort(){Node*s = front->previor; //初始化无序元素位置while (s != front){Node*p = s; //本次无序元素位置s = front;Node*x = front->next;Node*y = x->next;while (x != p){if (x->data > y->data){comparision++;front->data = x->data;x->data = y->data;y->data = front->data;movement = movement + 3;s = x; //更新无序元素位置}comparision++;x = x->next;y = y->next;}}}快速排序函数：快速排序函数是个递归调用函数，关键在一次快速排序函数的编写。
选择第一个元素作为分区的轴值，将待排序元素分成左右两个区域，左区的元素都比轴值小，右边的都更大。
然后反复进行此操作，即可完成排序。
而结束递归的关键便是左右分界节点有了直接前后继关系的时候。
void LinkList::Qsort(Node*x,Node*y){if (x->previor != y){Node*pivot = partion(x, y);Qsort(x, pivot->previor);Qsort(pivot->next, y);}}Node* LinkList::partion(Node*first, Node*end){int basic = first->data;while (first != end){while ((first != end) && (end->data >= basic)){end = end->previor;comparision++;}comparision++;first->data = end->data;movement++;while ((first != end) && (first->data <= basic)){first = first->next;comparision++;}comparision++;end->data = first->data;movement++;}first->data = basic;movement++;return first;}简单选择排序函数：是将待排序中最小的元素放置序列最前面，其关键是先通过循环比较确定最小元素的位置，再进行数据交换，从而大大减少了元素交换的次数。
void LinkList::selectsort(){Node*s = front->next;while (s != front->previor){Node*p = s->next;Node*record = s;while (p != front){Node*x = record;if (p->data < x->data){comparision++;record = p;}comparision++;p = p->next;}if (record != s){int a = record->data;record->data = s->data;s->data = a;movement = movement + 3;}s = s->next;}}3.程序运行结果分析4.总结本次实验进行了使用链表存储结构实现插入排序、冒泡排序、快速排序、简单选择排序的编程。
这使我对不同的排序方法有了更加深刻的理解和认识。
从中也体会到不同的排序方式所耗费的时间复杂度实在是大相径庭，这警示我们，编写一个时间复杂度小的排序函数在进行排序操作时，起着至关重要的作用。
完整代码如下：#include<iostream>#include<iomanip>using namespace std;struct Node{int data;struct Node*next;struct Node*previor;};class LinkList{private:Node* partion(Node*first,Node*end); //快速排序一趟public:Node*front;int comparision; //比较次数int movement; //移动次数LinkList() //无参构造{front = new Node;front->next = NULL;front->previor = NULL;comparision = movement = 0;}LinkList(int a[],int n); //构造函数:建立双向链表void insertsort(); //插入排序void bubblesort(); //冒泡排序void Qsort(Node*x,Node*y); //快速排序void selectsort(); //简单选择排序void show(); //显示排序结果~LinkList(); //析构函数};LinkList::LinkList(int a[],int n){front = new Node;front->next = NULL;front->previor = NULL;comparision = movement = 0;Node*x = new Node;Node*s = new Node;s->data = a[n - 1];s->next = front;s->previor = front;front->next = s;front->previor = s;x = s;for (int i = n - 2; i >= 0; i--){Node*s = new Node;s->data = a[i];s->next = front->next;s->previor = front;front->next = s;x->previor = s;x = s;}}Node* LinkList::partion(Node*first, Node*end){int basic = first->data;while (first != end){while ((first != end) && (end->data >= basic)){end = end->previor;comparision++;}comparision++;first->data = end->data;movement++;while ((first != end) && (first->data <= basic)){first = first->next;comparision++;}comparision++;end->data = first->data;movement++;}first->data = basic;movement++;return first;}void LinkList::insertsort(){Node*p = front->next;Node*s = p->next;while (s!=front){if (s->data < p->data){comparision++;front->data = s->data;movement++;Node*x = p;Node*y = s;while (front->data < x->data){comparision++;y->data = x->data;movement++;x = x->previor;y = y->previor;}y->data = front->data;movement++;}comparision++;p = p->next;s = s->next;}}void LinkList::bubblesort(){Node*s = front->previor; //初始化无序元素位置while (s != front){Node*p = s; //本次无序元素位置s = front;Node*x = front->next;Node*y = x->next;while (x != p){if (x->data > y->data){comparision++;front->data = x->data;x->data = y->data;y->data = front->data;movement = movement + 3;s = x; //更新无序元素位置}comparision++;x = x->next;y = y->next;}}}void LinkList::Qsort(Node*x,Node*y){if (x->previor != y){Node*pivot = partion(x, y);Qsort(x, pivot->previor);Qsort(pivot->next, y);}}void LinkList::selectsort(){Node*s = front->next;while (s != front->previor){Node*p = s->next;Node*record = s;while (p != front){Node*x = record;if (p->data < x->data){comparision++;record = p;}comparision++;p = p->next;}if (record != s){int a = record->data;record->data = s->data;s->data = a;movement = movement + 3;}s = s->next;}}void LinkList::show(){Node*x = new Node;x = front->next;while (x != front){cout << x->data << setw(4);x = x->next;}cout << endl << "比较次数：" << comparision << endl;cout << "移动次数：" << movement << endl;cout << endl;}LinkList:: ~LinkList(){Node*p = front;while (p!=front){Node*a = p;p = p->next;delete a;}delete p;}void showmenu();int main(){showmenu();cin.get();cin.get();return 0;}void showmenu(){int jay1[7] = { 2,6,7,9,15,24,29 };int jay2[7] = { 54,40,38,37,29,24,12 };int jay3[7] = { 16,45,81,1,4,69,100 };LinkList zzj1(jay1, 7);LinkList zzj2(jay2, 7);LinkList zzj3(jay3, 7);cout << "正序数据："; zzj1.show();cout << "逆序数据："; zzj2.show();cout << "乱序数据："; zzj3.show();int choice;cout << "请选择所要操作的内容：\n""1.插入排序 2.冒泡排序\n""3.快速排序 4.简单选择排序\n""5.退出\n";cin >> choice;int count = 0;Node*x, *y, *z;while (choice != 5){switch (choice){case 1:if (count != 0){x = zzj1.front->next;y = zzj2.front->next;z = zzj3.front->next;for (int i = 0; i < 7; i++){x->data = jay1[i];y->data = jay2[i];z->data = jay3[i];x = x->next;y = y->next;z = z->next;}parision = zzj1.movement = 0;parision = zzj2.movement = 0;parision = zzj3.movement = 0;}cout << "插入排序：\n";zzj1.insertsort();zzj2.insertsort();zzj3.insertsort();zzj1.show();zzj2.show();zzj3.show();count = 1;break;case 2:if (count != 0){x = zzj1.front->next;y = zzj2.front->next;z = zzj3.front->next;for (int i = 0; i < 7; i++){x->data = jay1[i];y->data = jay2[i];z->data = jay3[i];x = x->next;y = y->next;z = z->next;}parision = zzj1.movement = 0;parision = zzj2.movement = 0;parision = zzj3.movement = 0;}zzj1.bubblesort();zzj2.bubblesort();zzj3.bubblesort();cout << "冒泡排序：\n";zzj1.show();zzj2.show();zzj3.show();count = 1;break;case 3:if (count != 0){x = zzj1.front->next;y = zzj2.front->next;z = zzj3.front->next;for (int i = 0; i < 7; i++){x->data = jay1[i];y->data = jay2[i];z->data = jay3[i];x = x->next;y = y->next;z = z->next;}parision = zzj1.movement = 0;parision = zzj2.movement = 0;parision = zzj3.movement = 0;}x = zzj1.front;y = zzj2.front;z = zzj3.front;zzj1.Qsort(x->next, x->previor);zzj2.Qsort(y->next, y->previor);zzj3.Qsort(z->next, z->previor);cout << "快速排序：\n";zzj1.show();zzj2.show();zzj3.show();count = 1;break;case 4:if (count != 0){x = zzj1.front->next;y = zzj2.front->next;z = zzj3.front->next;for (int i = 0; i < 7; i++){x->data = jay1[i];y->data = jay2[i];z->data = jay3[i];x = x->next;y = y->next;z = z->next;}parision = zzj1.movement = 0;parision = zzj2.movement = 0;parision = zzj3.movement = 0;}zzj1.selectsort();zzj2.selectsort();zzj3.selectsort();cout << "简单选择排序：\n";zzj1.show();zzj2.show();zzj3.show();count = 1;break;default:cout << "这不是一个选项。
