简单入门排序算法（直接插入排序 折半插入排序 希尔排序 冒泡排序 堆排序 归并排序）

预备知识（排序数组的创建20，100 ，500 个随机数进行排序）

“Struct.h”

#pragma once#include<iostream>#include<string>using namespace std;#include<cstdlib> //C语言标准库函数，包含随机函数rand（）srand(number);#include<ctime> //time函数头文件#define MinSize 20#define MinddleSize 100#define MaxSize 500typedef struct {int key;//string name; 先做保留}Redtype;typedef struct {Redtype r[MinSize + 1];int length;int countMove = 0;int countCompare= 0 ;}Sqlist1;typedef struct {Redtype r[MinddleSize + 1];int length;int countMove = 0;int countCompare = 0;}Sqlist2;typedef struct {Redtype r[MaxSize + 1];int length;int countMove = 0;int countCompare = 0;}Sqlist3;void CreateList(Sqlist1 &L) {L.length = 0;srand(int(time(0)));for (int i = 1; i <= MinSize; i++) {L.r[i].key = rand() % 100;L.length++;}}void CreateList(Sqlist2 &L) {L.length = 0;srand(int(time(0)));for (int i = 1; i <= MinddleSize; i++) {L.r[i].key = rand() % 100;L.length++;}}void CreateList(Sqlist3 &L) {L.length = 0;srand(int(time(0)));for (int i = 1; i <= MaxSize; i++) {L.r[i].key = rand() % 100;L.length++;}}void ShowList(Sqlist1 L) {for (int i = 1; i <= L.length; i++) {cout << L.r[i].key << " ";if (i % 20 == 0) //每行20个cout << endl;}cout << "\n比较次数为：" << L.countCompare << endl;cout << "移动次数为： " << L.countMove << endl;}void ShowList(Sqlist2 L) {for (int i = 1; i <= L.length; i++) {cout << L.r[i].key << " ";if (i % 20 == 0) //每行20个cout << endl;}cout << "\n比较次数为：" << L.countCompare << endl;cout << "移动次数为： " << L.countMove << endl;}void ShowList(Sqlist3 L) {for (int i = 1; i <= L.length; i++) {cout << L.r[i].key << " ";if (i % 20 == 0) //每行20个cout << endl;}cout << "\n比较次数为：" << L.countCompare << endl;cout << "移动次数为： " << L.countMove << endl;}

插入排序：

（一）：简单插入排序（Straight Insertion sort）

将要排序的n个数据放在一个数组中从头开始进行n-1次插入排序，将第i个数据插入到r[i-1]的有序序列中，成为i个元素的有序序列数组的第一个位置作为缓冲单元，也作为标志单元，防止索引越界，每一趟循环中，第i个元素先放备份于缓存单元，从r[i-1]后往前比较，如果i元素值较小，就将较大的元素往后移动，直到遇到合适的位置（找到大于等于第i个元素的值，还是到达第一个数组首个元素位置），将待插入元素插入到合适的位置。

StraightInsertionSort.h

#pragma once#include"Struct.h"void StraightInsertSort(Sqlist1 &L) {for (int i = 2; i <= L.length; i++) { //进行 n-1次顺序查找L.countCompare++;if (L.r[i].key < L.r[i - 1].key) { //若要插入的元素小于有序表最后一个元素，L.r[0] = L.r[i];L.countMove++;L.r[i] = L.r[i - 1]; //将有序表最后一个结构体元素后移L.countMove++;int j;for (j = i - 2; L.r[0].key < L.r[j].key; j--) {// 从后往前匹配找位置，若当前位置不符合则进入循环，找到位置或者到达了监视哨则退出循环L.r[j + 1] = L.r[j];L.countMove++;L.countCompare++;}L.countCompare++;L.r[j + 1] = L.r[0]; //将待插入的结构体元素插入到正确的位置L.countMove++;}}}void StraightInsertSort(Sqlist2 &L) {for (int i = 2; i <= L.length; i++) { //进行 n-1次顺序查找L.countCompare++;if (L.r[i].key < L.r[i - 1].key) { //若要插入的元素小于有序表最后一个元素，L.r[0] = L.r[i];L.countMove++;L.r[i] = L.r[i - 1]; //将有序表最后一个结构体元素后移L.countMove++;int j;for (j = i - 2; L.r[0].key < L.r[j].key; j--) {// 从后往前匹配找位置，若当前位置不符合则进入循环，找到位置或者到达了监视哨则退出循环L.r[j + 1] = L.r[j];L.countMove++;L.countCompare++;}L.countCompare++;L.r[j + 1] = L.r[0]; //将待插入的结构体元素插入到正确的位置L.countMove++;}}}void StraightInsertSort(Sqlist3 &L) {for (int i = 2; i <= L.length; i++) { //进行 n-1次顺序查找L.countCompare++;if (L.r[i].key < L.r[i - 1].key) { //若要插入的元素小于有序表最后一个元素，L.r[0] = L.r[i];L.countMove++;L.r[i] = L.r[i - 1]; //将有序表最后一个结构体元素后移L.countMove++;int j;for (j = i - 2; L.r[0].key < L.r[j].key; j--) {// 从后往前匹配找位置，若当前位置不符合则进入循环，找到位置或者到达了监视哨则退出循环L.r[j + 1] = L.r[j];L.countMove++;L.countCompare++;}L.countCompare++;L.r[j + 1] = L.r[0]; //将待插入的结构体元素插入到正确的位置L.countMove++;}}}void OperationStraightInsertSort() {cout << "\n********** 20个随机数**********\n";Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;StraightInsertSort(L1);ShowList(L1);cout << "\n\n********** 100个随机数**********\n";Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;StraightInsertSort(L2);ShowList(L2);cout << "\n\n********** 500个随机数**********\n";Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;StraightInsertSort(L3);ShowList(L3);}

分析

是稳定的排序对于n个元素的平均移动和比较次数都是n^2/4适用于链式存储和顺序存储，基本有序而且数据量较小的情况

结果：

********** 20个随机数**********排序前：98 25 40 27 93 3 1 29 97 25 29 51 62 9 21 78 14 3 3 29比较次数为：0移动次数为： 0排序后：1 3 3 3 9 14 21 25 25 27 29 29 29 40 51 62 78 93 97 98比较次数为：130移动次数为： 149********** 100个随机数**********排序前：98 25 40 27 93 3 1 29 97 25 29 51 62 9 21 78 14 3 3 2913 29 77 90 97 30 94 97 91 99 80 12 3 3 20 68 88 42 30 4775 33 24 94 56 79 9 44 73 27 47 48 91 88 74 60 46 9 17 9161 74 10 32 82 94 17 95 75 24 41 99 41 95 62 12 79 65 50 6730 59 27 60 88 73 44 52 63 34 56 8 56 65 99 80 91 59 70 83比较次数为：0移动次数为： 0排序后：1 3 3 3 3 3 8 9 9 9 10 12 12 13 14 17 17 20 21 2424 25 25 27 27 27 29 29 29 29 30 30 30 32 33 34 40 41 41 4244 44 46 47 47 48 50 51 52 56 56 56 59 59 60 60 61 62 62 6365 65 67 68 70 73 73 74 74 75 75 77 78 79 79 80 80 82 83 8888 88 90 91 91 91 91 93 94 94 94 95 95 97 97 97 98 99 99 99比较次数为：2189移动次数为： 2282********** 500个随机数**********排序前：98 25 40 27 93 3 1 29 97 25 29 51 62 9 21 78 14 3 3 2913 29 77 90 97 30 94 97 91 99 80 12 3 3 20 68 88 42 30 4775 33 24 94 56 79 9 44 73 27 47 48 91 88 74 60 46 9 17 9161 74 10 32 82 94 17 95 75 24 41 99 41 95 62 12 79 65 50 6730 59 27 60 88 73 44 52 63 34 56 8 56 65 99 80 91 59 70 8381 63 45 42 23 21 43 26 28 71 14 91 10 81 99 55 93 41 77 9596 82 9 32 88 5 12 53 95 92 20 37 90 56 44 35 25 18 7 1622 90 26 99 52 36 57 10 56 98 47 85 42 90 53 73 26 4 1 235 55 79 48 54 84 52 51 68 58 93 17 14 56 62 84 4 32 64 3191 98 15 29 40 64 28 25 37 27 70 1 9 6 27 65 14 41 10 2979 45 46 53 50 58 22 45 62 13 83 14 38 43 97 8 42 10 82 1246 18 11 7 8 71 80 27 9 41 10 90 31 51 47 77 72 64 21 2331 20 19 10 99 55 61 9 77 63 94 11 7 6 31 34 13 4 25 3671 74 95 22 10 45 77 97 48 27 65 30 62 23 76 28 72 32 94 2520 90 17 93 38 97 63 18 12 99 56 41 28 86 99 92 15 93 59 7640 13 76 53 16 31 93 36 13 60 6 59 55 29 40 51 19 84 91 6742 7 27 24 69 32 36 5 51 32 48 3 42 40 31 88 67 48 20 8976 70 55 88 15 11 21 37 84 76 83 59 13 52 39 53 78 88 11 724 27 71 26 42 70 94 73 1 43 35 3 43 78 58 28 7 36 20 5871 60 31 21 20 18 55 23 33 73 16 50 41 76 57 80 50 53 80 4582 86 23 83 57 80 79 2 51 36 3 79 8 75 74 47 60 57 13 1540 29 27 30 2 77 38 93 80 52 59 27 80 11 4 93 87 56 5 4311 7 68 23 17 11 46 73 83 53 51 41 2 75 7 17 76 60 50 8268 42 53 72 85 52 70 84 32 34 46 86 0 77 89 3 84 35 93 8012 58 78 28 16 15 74 83 62 87 33 23 80 21 39 47 93 43 81 1比较次数为：0移动次数为： 0排序后：0 1 1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 3 4 44 4 4 5 5 5 5 6 6 6 7 7 7 7 7 7 7 8 8 88 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 11 11 11 1111 11 11 12 12 12 12 12 12 13 13 13 13 13 13 13 14 14 14 1414 15 15 15 15 15 16 16 16 16 17 17 17 17 17 17 18 18 18 1819 19 20 20 20 20 20 20 20 21 21 21 21 21 21 22 22 22 23 2323 23 23 23 23 23 24 24 24 25 25 25 25 25 25 26 26 26 26 2727 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 29 29 29 2929 29 29 29 30 30 30 30 30 31 31 31 31 31 31 31 32 32 32 3232 32 32 33 33 33 34 34 34 35 35 35 36 36 36 36 36 36 37 3737 38 38 38 39 39 40 40 40 40 40 40 41 41 41 41 41 41 41 4142 42 42 42 42 42 42 42 43 43 43 43 43 43 44 44 44 45 45 4545 45 46 46 46 46 46 47 47 47 47 47 47 48 48 48 48 48 50 5050 50 50 51 51 51 51 51 51 51 52 52 52 52 52 52 53 53 53 5353 53 53 53 54 55 55 55 55 55 55 56 56 56 56 56 56 56 56 5757 57 57 58 58 58 58 58 59 59 59 59 59 59 60 60 60 60 60 6061 61 62 62 62 62 62 62 63 63 63 63 64 64 64 65 65 65 65 6767 67 68 68 68 68 69 70 70 70 70 70 71 71 71 71 71 72 72 7272 73 73 73 73 73 73 74 74 74 74 74 75 75 75 75 76 76 76 7676 76 76 77 77 77 77 77 77 77 78 78 78 78 79 79 79 79 79 7980 80 80 80 80 80 80 80 80 80 81 81 81 82 82 82 82 82 83 8383 83 83 83 84 84 84 84 84 84 85 85 86 86 86 87 87 88 88 8888 88 88 88 89 89 90 90 90 90 90 90 91 91 91 91 91 91 91 9292 93 93 93 93 93 93 93 93 93 93 94 94 94 94 94 94 95 95 9595 95 96 97 97 97 97 97 97 98 98 98 99 99 99 99 99 99 99 99比较次数为：63261移动次数为： 63744D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 8384)已退出，返回代码为: 0。若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。按任意键关闭此窗口...

折半插入排序（Binary Insertion Sort)

将待排序数据插入到数组r[n]中进行n-1次循环和折半插入排序，每次将第i个元素插入到r[i-1]，成有序序列r[i]每一次排序中，将待插入元素备份到缓存单元，将第i个元素与有序序列r[i-1]的中间元素（下标为m)比较，low(1)记录有序表的第一个元素的下标，high(i-1)记录有序表的最后一个元素的下标，如果i元素较大就对后子表进行二分查找(low = m +1），较小则对前子表进行二分查找（high = m -1),直到找到合适的位置，找到待插入位置后，将合适的位置以及有序表后面的元素都后移一位，再将待插入元素插入

OperationBianryInsertSort();

#pragma once#include"Struct.h"void BinaryInsertSort(Sqlist1 &L) {for (int i = 2; i <= L.length; i++) {L.countCompare++;L.r[0] = L.r[i]; //监视哨位置记录待插入元素L.countMove++;int low = 1; int high = i - 1; //置查找区间的初始值int m; //折半查找的位置while (low <= high) {L.countCompare++;m = (low + high) / 2; //根据高低位置的折中位置给m赋值if (L.r[0].key < L.r[m].key)high = m - 1;elselow = m + 1;L.countCompare++;}L.countCompare++;for (int j = i - 1; j >= high + 1; j--) { //将i=1 到 high +1 之间的元素都后移一位L.r[j + 1] = L.r[j];L.countCompare++;L.countMove++;}L.countCompare++;L.r[high + 1] = L.r[0]; //将待插入元素插入到找到的位置中L.countMove++;cout << "第 "<<i-1<<" 趟排序：" << endl;ShowList(L);}L.countCompare++;}void BinaryInsertSort(Sqlist2 &L) {for (int i = 2; i <= L.length; i++) {L.countCompare++;L.r[0] = L.r[i]; //监视哨位置记录待插入元素L.countMove++;int low = 1; int high = i - 1; //置查找区间的初始值int m; //折半查找的位置while (low <= high) {L.countCompare++;m = (low + high) / 2; //根据高低位置的折中位置给m赋值if (L.r[0].key < L.r[m].key)high = m - 1;elselow = m + 1;L.countCompare++;}L.countCompare++;for (int j = i - 1; j >= high + 1; j--) { //将i=1 到 high +1 之间的元素都后移一位L.r[j + 1] = L.r[j];L.countCompare++;L.countMove++;}L.countCompare++;L.r[high + 1] = L.r[0]; //将待插入元素插入到找到的位置中L.countMove++;}L.countCompare++;}void BinaryInsertSort(Sqlist3 &L) {for (int i = 2; i <= L.length; i++) {L.countCompare++;L.r[0] = L.r[i]; //监视哨位置记录待插入元素L.countMove++;int low = 1; int high = i - 1; //置查找区间的初始值int m; //折半查找的位置while (low <= high) {L.countCompare++;m = (low + high) / 2; //根据高低位置的折中位置给m赋值if (L.r[0].key < L.r[m].key)high = m - 1;elselow = m + 1;L.countCompare++;}L.countCompare++;for (int j = i - 1; j >= high + 1; j--) { //将i=1 到 high +1 之间的元素都后移一位L.r[j + 1] = L.r[j];L.countCompare++;L.countMove++;}L.countCompare++;L.r[high + 1] = L.r[0]; //将待插入元素插入到找到的位置中L.countMove++;}L.countCompare++;}void OperationBianryInsertSort() {cout << "\n********** 20个随机数**********\n";Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;BinaryInsertSort(L1);//ShowList(L1);cout << "\n\n********** 100个随机数**********\n";Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;BinaryInsertSort(L2);ShowList(L2);cout << "\n\n********** 500个随机数**********\n";Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;BinaryInsertSort(L3);ShowList(L3);}

result

********** 20个随机数**********

排序前：

94 90 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：0

移动次数为： 0

排序后：

第 1 趟排序：

90 94 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：6

移动次数为： 3

第 2 趟排序：

85 90 94 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：13

移动次数为： 7

第 3 趟排序：

85 90 94 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：20

移动次数为： 9

第 4 趟排序：

82 85 90 94 98 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：31

移动次数为： 15

第 5 趟排序：

18 82 85 90 94 98 13 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：43

移动次数为： 22

第 6 趟排序：

13 18 82 85 90 94 98 89 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：56

移动次数为： 30

第 7 趟排序：

13 18 82 85 89 90 94 98 65 89 27 78 82 24 3 73 15 51 67 30

比较次数为：68

移动次数为： 35

第 8 趟排序：

13 18 65 82 85 89 90 94 98 89 27 78 82 24 3 73 15 51 67 30

比较次数为：83

移动次数为： 43

第 9 趟排序：

13 18 65 82 85 89 89 90 94 98 27 78 82 24 3 73 15 51 67 30

比较次数为：95

移动次数为： 48

第 10 趟排序：

13 18 27 65 82 85 89 89 90 94 98 78 82 24 3 73 15 51 67 30

比较次数为：112

移动次数为： 58

第 11 趟排序：

13 18 27 65 78 82 85 89 89 90 94 98 82 24 3 73 15 51 67 30

比较次数为：130

移动次数为： 67

第 12 趟排序：

13 18 27 65 78 82 82 85 89 89 90 94 98 24 3 73 15 51 67 30

比较次数为：145

移动次数为： 75

第 13 趟排序：

13 18 24 27 65 78 82 82 85 89 89 90 94 98 3 73 15 51 67 30

比较次数为：167

移动次数为： 88

第 14 趟排序：

3 13 18 24 27 65 78 82 82 85 89 89 90 94 98 73 15 51 67 30

比较次数为：190

移动次数为： 104

第 15 趟排序：

3 13 18 24 27 65 73 78 82 82 85 89 89 90 94 98 15 51 67 30

比较次数为：210

移动次数为： 115

第 16 趟排序：

3 13 15 18 24 27 65 73 78 82 82 85 89 89 90 94 98 51 67 30

比较次数为：235

移动次数为： 131

第 17 趟排序：

3 13 15 18 24 27 51 65 73 78 82 82 85 89 89 90 94 98 67 30

比较次数为：257

移动次数为： 144

第 18 趟排序：

3 13 15 18 24 27 51 65 67 73 78 82 82 85 89 89 90 94 98 30

比较次数为：280

移动次数为： 156

第 19 趟排序：

3 13 15 18 24 27 30 51 65 67 73 78 82 82 85 89 89 90 94 98

比较次数为：304

移动次数为： 171

********** 100个随机数**********

排序前：

94 90 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

53 95 1 82 93 82 0 81 20 32 39 89 19 72 43 53 54 58 44 78

83 97 1 74 17 23 75 29 5 32 91 13 55 17 91 48 34 78 7 25

70 90 52 84 90 29 96 13 13 19 35 31 91 95 22 20 68 98 70 61

29 25 24 60 76 51 78 4 45 52 76 0 81 59 91 34 29 19 42 46

比较次数为：0

移动次数为： 0

排序后：

0 0 1 1 3 4 5 7 13 13 13 13 15 17 17 18 19 19 19 20

20 22 23 24 24 25 25 27 29 29 29 29 30 31 32 32 34 34 35 39

42 43 44 45 46 48 51 51 52 52 53 53 54 55 58 59 60 61 65 67

68 70 70 72 73 74 75 76 76 78 78 78 78 81 81 82 82 82 82 83

84 85 89 89 89 90 90 90 91 91 91 91 93 94 95 95 96 97 98 98

比较次数为：4007

移动次数为： 2845

********** 500个随机数**********

排序前：

94 90 85 98 82 18 13 89 65 89 27 78 82 24 3 73 15 51 67 30

53 95 1 82 93 82 0 81 20 32 39 89 19 72 43 53 54 58 44 78

83 97 1 74 17 23 75 29 5 32 91 13 55 17 91 48 34 78 7 25

70 90 52 84 90 29 96 13 13 19 35 31 91 95 22 20 68 98 70 61

29 25 24 60 76 51 78 4 45 52 76 0 81 59 91 34 29 19 42 46

38 89 92 95 92 71 85 85 24 11 24 20 59 37 88 60 3 3 18 33

28 32 14 9 91 35 62 24 22 41 95 31 53 48 57 96 47 25 41 76

16 28 9 50 89 34 56 44 68 68 38 16 6 26 82 65 94 82 39 21

84 83 56 53 62 80 43 95 82 45 91 79 88 72 32 17 85 23 60 53

44 13 36 84 4 98 24 55 86 93 31 22 88 45 16 3 14 97 30 67

16 63 95 47 29 6 6 74 66 64 47 31 54 68 78 30 4 21 8 72

10 58 85 11 37 11 49 82 0 15 37 84 61 64 25 14 38 88 48 40

85 65 87 65 62 96 33 70 84 17 86 15 58 38 19 63 95 45 17 97

25 47 86 76 30 78 44 16 59 9 71 49 16 14 98 15 77 93 9 11

84 63 29 30 94 58 83 78 22 63 70 61 71 67 67 24 22 54 70 64

48 25 34 29 70 51 57 19 21 51 13 13 38 12 31 62 31 72 2 82

71 61 38 97 32 89 9 7 6 89 69 47 74 28 92 69 12 33 60 14

29 98 27 2 9 70 2 69 60 70 0 21 57 19 45 67 48 87 76 55

4 93 98 89 16 70 40 77 72 94 51 19 42 26 65 19 86 55 75 47

81 6 41 99 25 65 65 72 33 3 0 60 42 96 97 57 63 39 75 52

9 87 65 88 18 59 12 35 22 37 33 67 7 66 56 13 77 76 56 90

85 44 20 35 0 72 93 91 18 55 97 87 39 48 92 53 56 53 24 7

98 2 50 74 29 69 46 82 15 10 36 73 7 81 41 20 56 51 4 77

93 3 10 29 11 94 2 19 36 65 93 54 22 49 48 88 15 66 52 83

35 77 3 76 20 56 7 42 48 72 28 0 80 65 53 83 0 23 56 62

比较次数为：0

移动次数为： 0

排序后：

0 0 0 0 0 0 0 0 1 1 2 2 2 2 2 3 3 3 3 3

3 3 4 4 4 4 4 5 6 6 6 6 6 7 7 7 7 7 7 8

9 9 9 9 9 9 9 10 10 10 11 11 11 11 11 12 12 12 13 13

13 13 13 13 13 13 14 14 14 14 14 15 15 15 15 15 15 16 16 16

16 16 16 16 17 17 17 17 17 18 18 18 18 19 19 19 19 19 19 19

19 19 20 20 20 20 20 20 21 21 21 21 22 22 22 22 22 22 22 23

23 23 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 26 26 27

27 28 28 28 28 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30

31 31 31 31 31 31 32 32 32 32 32 33 33 33 33 33 34 34 34 34

35 35 35 35 35 36 36 36 37 37 37 37 38 38 38 38 38 38 39 39

39 39 40 40 41 41 41 41 42 42 42 42 43 43 44 44 44 44 44 45

45 45 45 45 46 46 47 47 47 47 47 47 48 48 48 48 48 48 48 48

49 49 49 50 50 51 51 51 51 51 51 52 52 52 52 53 53 53 53 53

53 53 53 54 54 54 54 55 55 55 55 55 56 56 56 56 56 56 56 56

57 57 57 57 58 58 58 58 59 59 59 59 60 60 60 60 60 60 61 61

61 61 62 62 62 62 62 63 63 63 63 63 64 64 64 65 65 65 65 65

65 65 65 65 65 66 66 66 67 67 67 67 67 67 68 68 68 68 69 69

69 69 70 70 70 70 70 70 70 70 70 71 71 71 71 72 72 72 72 72

72 72 72 73 73 74 74 74 74 75 75 75 76 76 76 76 76 76 76 77

77 77 77 77 78 78 78 78 78 78 78 79 80 80 81 81 81 81 82 82

82 82 82 82 82 82 82 82 83 83 83 83 83 84 84 84 84 84 84 85

85 85 85 85 85 85 86 86 86 86 87 87 87 87 88 88 88 88 88 88

89 89 89 89 89 89 89 89 90 90 90 90 91 91 91 91 91 91 91 92

92 92 92 93 93 93 93 93 93 93 94 94 94 94 94 95 95 95 95 95

95 95 96 96 96 96 97 97 97 97 97 97 98 98 98 98 98 98 98 99

比较次数为：72891

移动次数为： 64773

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 7796)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

分析

稳定排序由于要进行折半查找，用于顺序结构，不能用于链式结构适用于无序，n较大时的情况移动次数不变，平均比较次数减少

希尔排序（Shell Sort）

将n个数据存在数组中，按照一定的增量进行分组，对分组的元素进行直接选择排序，一步步达到基本有序，最后做一次直接简单排序实现全部排序成功。每一趟根据不同的增量值dk从增量下标+1的位置开始向后遍历数组，每个元素向前与间隔为dk的元素组成的分组进行直接排序每一趟排序会更加有序，最后对基本有序的整个表实现一次增量为1的直接插入排序

ShellSort.h

#pragma once#include"Struct.h"void ShellInsert(Sqlist1 &L, int k) {for (int i = k + 1; i <= L.length; i++) {if (L.r[i].key < L.r[i - k].key) { //将i处元素插入到有序子列L.r[0] = L.r[i]; //将待存储元素存储在辅助单元中L.countMove++;int j = 0;for (int j = i - k; j > 0 && L.r[0].key < L.r[j].key; j -= k) {L.r[j + k] = L.r[j];L.countMove++;L.countCompare++;}L.countCompare++;L.r[j + k] = L.r[0];L.countMove++;}L.countCompare++;}L.countCompare++;}void Shellsort(Sqlist1 &L, int dt[], int t) {for (int k = 0; k < t; k++) {ShellInsert(L, dt[k]); //进行t次希尔插入排序L.countCompare++;}L.countCompare++;}void ShellInsert(Sqlist2 &L, int k) {for (int i = k + 1; i <= L.length; i++) {if (L.r[i].key < L.r[i - k].key) { //将i处元素插入到有序子列L.r[0] = L.r[i]; //将待存储元素存储在辅助单元中L.countMove++;int j = 0;for (int j = i - k; j > 0 && L.r[0].key < L.r[j].key; j -= k) {L.r[j + k] = L.r[j];L.countMove++;L.countCompare++;}L.countCompare++;L.r[j + k] = L.r[0];L.countMove++;}L.countCompare++;}L.countCompare++;}void Shellsort(Sqlist2 &L, int dt[], int t) {for (int k = 0; k < t; k++) {ShellInsert(L, dt[k]); //进行t次希尔插入排序L.countCompare++;}L.countCompare++;}void ShellInsert(Sqlist3 &L, int k) {for (int i = k + 1; i <= L.length; i++) {if (L.r[i].key < L.r[i - k].key) { //将i处元素插入到有序子列L.r[0] = L.r[i]; //将待存储元素存储在辅助单元中L.countMove++;int j = 0;for (int j = i - k; j > 0 && L.r[0].key < L.r[j].key; j -= k) {L.r[j + k] = L.r[j];L.countMove++;L.countCompare++;}L.countCompare++;L.r[j + k] = L.r[0];L.countMove++;}L.countCompare++;}L.countCompare++;}void Shellsort(Sqlist3 &L, int dt[], int t) {for (int k = 0; k < t; k++) {ShellInsert(L, dt[k]); //进行t次希尔插入排序L.countCompare++;}L.countCompare++;}void OperationShellSort() {int dt[] = { 1,3,5 };int t = 3;cout << "\n********** 20个随机数**********\n";Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;Shellsort(L1,dt,t);ShowList(L1);cout << "\n\n********** 100个随机数**********\n";Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;Shellsort(L2, dt, t);ShowList(L2);cout << "\n\n********** 500个随机数**********\n";Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;Shellsort(L3, dt, t);ShowList(L3);}

result:

********** 20个随机数**********

排序前：

63 92 11 36 46 77 54 74 91 34 50 32 2 65 90 5 84 54 88 33

比较次数为：0

移动次数为： 0

排序后：

33 90 63 50 90 91 91 90 91 91 91 91 92 92 92 92 92 92 92 92

比较次数为：215

移动次数为： 180

********** 100个随机数**********

排序前：

63 92 11 36 46 77 54 74 91 34 50 32 2 65 90 5 84 54 88 33

34 96 24 59 13 83 20 79 69 80 31 19 31 22 68 35 8 78 6 57

50 74 42 85 29 61 92 75 30 74 78 47 35 49 65 65 84 58 53 92

76 98 83 42 83 43 21 10 18 51 62 66 27 82 14 64 99 31 20 98

50 21 39 77 17 79 46 46 29 63 39 6 43 70 93 80 95 82 76 28

比较次数为：0

移动次数为： 0

排序后：

28 39 63 28 80 59 39 63 59 43 82 59 63 82 59 82 82 63 82 82

82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82 82

82 82 90 85 83 91 91 91 91 91 91 91 91 91 91 91 91 92 92 92

92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92 92

92 92 92 92 92 92 92 92 92 92 92 92 96 96 96 96 96 98 99 99

比较次数为：3678

移动次数为： 3528

********** 500个随机数**********

排序前：

63 92 11 36 46 77 54 74 91 34 50 32 2 65 90 5 84 54 88 33

34 96 24 59 13 83 20 79 69 80 31 19 31 22 68 35 8 78 6 57

50 74 42 85 29 61 92 75 30 74 78 47 35 49 65 65 84 58 53 92

76 98 83 42 83 43 21 10 18 51 62 66 27 82 14 64 99 31 20 98

50 21 39 77 17 79 46 46 29 63 39 6 43 70 93 80 95 82 76 28

42 40 50 71 99 28 60 36 37 99 22 61 73 87 79 50 89 85 23 96

33 76 90 34 57 96 21 25 24 33 83 78 99 37 85 84 17 7 82 58

25 41 62 90 77 65 13 82 22 51 3 47 51 78 93 16 99 28 7 40

69 55 52 7 42 82 5 94 81 15 49 81 74 14 28 53 85 81 91 18

44 9 52 75 24 49 70 75 43 30 15 98 42 40 36 20 46 67 28 61

68 80 1 10 25 92 91 91 29 92 31 58 83 7 80 91 66 2 43 0

27 83 92 74 63 76 22 45 51 96 31 84 65 29 14 9 44 96 77 56

90 87 22 25 92 10 24 51 3 43 41 30 15 17 7 57 37 55 36 1

61 57 74 40 40 92 31 65 94 99 64 67 55 56 92 0 86 60 4 84

11 18 28 66 1 78 16 6 39 29 4 64 37 22 37 12 1 25 5 23

31 19 17 89 28 85 69 55 10 54 27 94 68 66 4 32 39 60 27 54

30 54 91 36 2 76 55 21 73 18 20 18 44 26 20 25 54 29 84 84

66 68 23 56 40 62 40 75 81 73 68 77 9 14 29 38 44 53 82 67

23 96 64 11 76 71 12 88 24 71 7 42 24 31 2 87 30 80 9 0

33 44 86 54 56 29 22 89 76 71 92 85 95 47 97 17 3 53 50 29

74 97 8 71 76 49 33 46 59 23 88 34 5 44 50 10 63 16 77 90

5 96 10 87 14 60 78 45 61 90 47 9 16 58 96 72 44 12 68 66

54 95 22 98 28 35 12 72 67 89 4 8 35 10 16 27 47 21 73 91

51 13 97 92 79 2 14 4 14 94 14 50 23 0 30 67 99 20 48 13

15 33 13 61 99 75 77 62 75 47 16 46 28 34 84 53 30 77 80 16

比较次数为：0

移动次数为： 0

排序后：

16 23 96 16 96 52 23 96 52 79 89 80 96 89 79 89 80 96 89 79

89 80 96 89 79 89 80 96 89 79 89 80 96 89 79 89 80 96 89 79

89 80 96 89 79 89 80 96 89 79 89 80 96 89 79 89 80 96 89 79

89 80 96 89 79 89 80 96 89 79 89 80 96 89 89 89 80 96 89 89

89 80 96 89 89 89 80 96 89 89 89 80 96 89 89 89 80 96 89 89

89 80 96 89 89 89 80 96 89 89 89 80 96 89 89 89 80 96 89 89

89 80 96 89 89 89 80 96 89 89 89 80 96 89 89 89 89 96 89 89

89 89 96 89 89 89 89 96 89 89 89 89 96 89 89 89 89 96 89 89

89 89 96 89 89 89 89 96 89 89 89 89 96 89 89 89 89 96 89 89

89 89 96 89 89 89 89 96 89 89 89 89 96 89 89 89 89 96 89 89

89 89 96 89 89 89 89 96 89 89 89 89 96 90 89 89 90 96 90 90

89 90 96 90 90 90 90 96 90 90 90 90 96 90 90 90 90 96 90 97

90 90 96 90 97 97 90 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 96 97 97 97 97 96 97 97 97 97 96 97 97

97 97 96 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97

97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97

97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97

97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97

97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 97 98 98

98 98 98 98 98 98 98 98 98 99 99 99 99 99 99 99 99 99 99 99

比较次数为：102499

移动次数为： 102209

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 21188)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

分析：

排序不稳定只能用于顺序结构比较次数和移动次数比直接排序少，更适合n大且无序的顺序表

交换排序

冒泡排序

待排序的记录存储在n个大小的存储单元中从头开始进行n次冒泡排序每一趟排序从第i 个记录开始排序，对i和i+1位置的元素比较，如果为逆序（前 > 后)则交换两个位置的记录，将i位置以及后续的最小值放到第i个位置排序结束，记录呈现升序

BubbleSort.h

#pragma once#include"Struct.h"void Bubble_Sort(Sqlist1 &L) {int m = L.length - 1; int flag = 1;while (m > 0 && flag == 1) {flag = 0;for (int i = 1; i <= m; i++) {L.countCompare++;if (L.r[i].key > L.r[i + 1].key) {L.countCompare++;flag = 1;Redtype t1 = L.r[i];L.countMove++;L.r[i] = L.r[i+1];L.countMove++;L.r[i+1] = t1;L.countMove++;}L.countCompare++;}cout << endl;ShowList(L);m--;L.countCompare++;}L.countCompare++;}void Bubble_Sort2(Sqlist2 &L) {int size = L.length;int flag ;for (int pass = 1; pass < size; pass++) {L.countCompare++;flag = 1;int i ;for (int i = 1; i <= size - pass; i++) {L.countCompare++;if (L.r[i].key > L.r[i + 1].key) {L.countCompare++;Redtype t = L.r[i];L.countMove++;L.r[i] = L.r[i+1];L.countMove++;L.r[i + 1] = t;L.countMove++;flag = 0;}L.countCompare++;}L.countCompare++;L.countCompare++;if (flag)break;}L.countCompare++;}void Bubble_Sort(Sqlist3 &L) {int m = L.length - 1;int flag = 1;while (m > 0 && flag == 1) {flag = 0;for (int i = 1; i <= m; i++) {L.countCompare++;if (L.r[i].key > L.r[i + 1].key) {L.countCompare++;flag = 1;Redtype t1 = L.r[i];L.countMove++;L.r[i] = L.r[i + 1];L.countMove++;L.r[i + 1] = t1;L.countMove++;}L.countCompare++;}m--;L.countCompare++;}L.countCompare++;}void OperationBubbleSort() {Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;Bubble_Sort(L1);//ShowList(L1);Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;Bubble_Sort2(L2);ShowList(L2);Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;Bubble_Sort(L3);ShowList(L3);}

result

排序前：

65 26 8 66 27 59 19 46 80 60 51 10 3 56 38 88 87 23 85 59

比较次数为：0

移动次数为： 0

排序后：

26 8 65 27 59 19 46 66 60 51 10 3 56 38 80 87 23 85 59 88

比较次数为：54

移动次数为： 48

8 26 27 59 19 46 65 60 51 10 3 56 38 66 80 23 85 59 87 88

比较次数为：105

移动次数为： 90

8 26 27 19 46 59 60 51 10 3 56 38 65 66 23 80 59 85 87 88

比较次数为：150

移动次数为： 120

8 26 19 27 46 59 51 10 3 56 38 60 65 23 66 59 80 85 87 88

比较次数为：191

移动次数为： 144

8 19 26 27 46 51 10 3 56 38 59 60 23 65 59 66 80 85 87 88

比较次数为：230

移动次数为： 168

8 19 26 27 46 10 3 51 38 56 59 23 60 59 65 66 80 85 87 88

比较次数为：264

移动次数为： 183

8 19 26 27 10 3 46 38 51 56 23 59 59 60 65 66 80 85 87 88

比较次数为：296

移动次数为： 198

8 19 26 10 3 27 38 46 51 23 56 59 59 60 65 66 80 85 87 88

比较次数为：325

移动次数为： 210

8 19 10 3 26 27 38 46 23 51 56 59 59 60 65 66 80 85 87 88

比较次数为：351

移动次数为： 219

8 10 3 19 26 27 38 23 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：375

移动次数为： 228

8 3 10 19 26 27 23 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：396

移动次数为： 234

3 8 10 19 26 23 27 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：415

移动次数为： 240

3 8 10 19 23 26 27 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：431

移动次数为： 243

3 8 10 19 23 26 27 38 46 51 56 59 59 60 65 66 80 85 87 88

比较次数为：444

移动次数为： 243

排序前：

65 26 8 66 27 59 19 46 80 60 51 10 3 56 38 88 87 23 85 59

11 71 63 42 85 37 82 9 62 19 33 48 28 93 2 75 26 36 28 48

10 76 7 99 64 81 19 10 87 1 47 1 62 37 71 78 17 99 19 72

20 37 21 77 99 29 81 24 74 28 40 60 51 37 79 34 58 16 32 77

68 58 41 92 99 26 92 36 56 60 36 34 10 37 61 35 87 76 89 14

比较次数为：0

移动次数为： 0

排序后：

1 1 2 3 7 8 9 10 10 10 10 11 14 16 17 19 19 19 19 20

21 23 24 26 26 26 27 28 28 28 29 32 33 34 34 35 36 36 36 37

37 37 37 37 38 40 41 42 46 47 48 48 51 51 56 56 58 58 59 59

60 60 60 61 62 62 63 64 65 66 68 71 71 72 74 75 76 76 77 77

78 79 80 81 81 82 85 85 87 87 87 88 89 92 92 93 99 99 99 99

比较次数为：12323

移动次数为： 6870

排序前：

65 26 8 66 27 59 19 46 80 60 51 10 3 56 38 88 87 23 85 59

11 71 63 42 85 37 82 9 62 19 33 48 28 93 2 75 26 36 28 48

10 76 7 99 64 81 19 10 87 1 47 1 62 37 71 78 17 99 19 72

20 37 21 77 99 29 81 24 74 28 40 60 51 37 79 34 58 16 32 77

68 58 41 92 99 26 92 36 56 60 36 34 10 37 61 35 87 76 89 14

25 72 73 18 54 5 2 29 59 83 73 64 53 69 25 19 49 34 56 59

26 6 67 11 76 87 74 92 71 17 30 85 85 63 29 9 16 54 43 38

39 64 83 66 11 58 86 72 37 58 69 81 90 32 81 91 13 13 90 5

41 80 13 45 54 93 59 43 73 71 40 46 91 39 88 36 81 25 16 77

38 85 25 84 57 82 78 29 78 13 95 18 54 74 4 5 25 83 94 10

64 53 92 81 67 78 94 10 16 51 98 31 25 67 63 73 38 41 27 19

19 3 19 27 16 50 44 46 78 12 16 95 41 7 63 35 74 83 91 43

68 27 22 33 89 49 39 4 54 40 90 23 3 33 44 16 35 36 34 21

84 24 56 62 61 89 53 8 77 50 53 81 36 54 39 53 15 70 57 57

64 55 33 74 58 77 65 52 94 9 8 16 7 23 94 66 24 28 58 99

99 1 31 50 88 79 65 29 42 98 5 91 5 7 50 8 69 43 93 60

86 52 68 87 33 74 22 13 65 2 6 45 21 22 29 67 37 26 85 39

71 97 19 60 53 95 7 96 12 93 26 48 75 65 45 96 39 72 88 97

65 65 61 54 46 60 67 68 67 67 81 92 90 92 19 30 87 27 94 48

86 89 3 44 63 57 38 73 60 70 48 63 75 17 83 70 35 24 76 41

5 15 98 71 46 34 69 26 68 60 41 74 48 54 20 64 1 79 45 19

54 86 46 11 92 1 65 5 8 81 10 94 16 65 20 27 76 72 89 23

23 61 39 91 9 5 81 43 7 99 61 2 69 98 39 92 48 73 29 42

4 95 32 90 7 18 24 15 39 12 76 19 24 6 80 15 78 85 46 3

74 26 82 62 46 46 33 48 18 65 37 2 28 94 59 42 27 92 20 61

比较次数为：0

移动次数为： 0

排序后：

1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 5 5

5 5 5 5 5 5 6 6 6 7 7 7 7 7 7 7 8 8 8 8

8 9 9 9 9 10 10 10 10 10 10 10 11 11 11 11 12 12 12 13

13 13 13 13 14 15 15 15 15 16 16 16 16 16 16 16 16 16 17 17

17 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20

20 21 21 21 22 22 22 23 23 23 23 23 24 24 24 24 24 24 25 25

25 25 25 25 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 28

28 28 28 28 29 29 29 29 29 29 29 30 30 31 31 32 32 32 33 33

33 33 33 33 34 34 34 34 34 35 35 35 35 36 36 36 36 36 36 37

37 37 37 37 37 37 37 38 38 38 38 38 39 39 39 39 39 39 39 39

39 40 40 40 41 41 41 41 41 41 42 42 42 42 43 43 43 43 43 44

44 44 45 45 45 45 46 46 46 46 46 46 46 46 46 47 48 48 48 48

48 48 48 48 49 49 50 50 50 50 51 51 51 52 52 53 53 53 53 53

53 54 54 54 54 54 54 54 54 54 55 56 56 56 56 57 57 57 57 58

58 58 58 58 58 59 59 59 59 59 59 60 60 60 60 60 60 60 60 61

61 61 61 61 61 62 62 62 62 63 63 63 63 63 63 64 64 64 64 64

64 65 65 65 65 65 65 65 65 65 65 66 66 66 67 67 67 67 67 67

67 68 68 68 68 68 69 69 69 69 69 70 70 70 71 71 71 71 71 71

72 72 72 72 72 73 73 73 73 73 73 74 74 74 74 74 74 74 74 75

75 75 76 76 76 76 76 76 77 77 77 77 77 78 78 78 78 78 78 79

79 79 80 80 80 81 81 81 81 81 81 81 81 81 81 82 82 82 83 83

83 83 83 84 84 85 85 85 85 85 85 85 86 86 86 86 87 87 87 87

87 87 88 88 88 88 89 89 89 89 89 90 90 90 90 90 91 91 91 91

91 92 92 92 92 92 92 92 92 92 93 93 93 93 94 94 94 94 94 94

94 95 95 95 95 96 96 97 97 98 98 98 98 99 99 99 99 99 99 99

比较次数为：311232

移动次数为： 184560

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 16184)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

分析：

稳定排序用于顺序结构和链式结构移动次数多，n较大时不适合

快速排序

将待排序记录存储在n个大小的存储单元中从n个记录中取一个记录作为枢轴记录（一般取第一个记录），然后以记录为轴，比它大的记录移动到右边，比它小的记录移动到左边，再将从左边开始找比枢轴大的记录移动到右边（交替执行两个操作，直到遍历整个表，最后将枢轴记录放到枢轴位置，形成两个子表，再对字表进行重复操作，直到字表只剩下一个记录，此时排序完成第一趟排序中，将枢轴记录(r[1]放在缓存单元r[0]中，获取顺序存储结构的上界high和下界low，选定枢轴后，从该表的表右侧向左开始搜索，先找到第一比枢轴记录小的记录放到low（r[1])（若high位置的记录>=枢轴记录则没有找到，将high 左移（-1),否则将high位置记录移动到low位置）在从左边向右寻找第一个比枢轴记录大的记录，移动到high位置（若low位置的记录<=枢轴记录则找不到，将low右移动，否则将low位置的记录移动到high位置）,重复两个操作，直到遍历了整个表，再将枢轴记录放到枢轴位置接下来每一趟对两个字进行重复操作

QuickSort.h

#pragma once#include"Struct.h"int Partition(Sqlist1 &L, int low, int high) {L.r[0] = L.r[low]; //将第一个记录暂存在缓存单元int protkey = L.r[low].key; //枢轴记录的key值while (low < high) {L.countCompare++;while (low < high && L.r[high].key >= protkey) { //找出右边第一个比key的的记录的记录L.countCompare++;high--;}L.countCompare++;L.r[low] = L.r[high]; //将右边第一个小于prokey的记录移动到low位置L.countMove++;while (low < high && L.r[low].key <= protkey) {L.countCompare++;low++; }L.countCompare++;L.r[high] = L.r[low]; //将左边第一个大于prokey的记录移动到高端high位置L.countMove++;}L.countCompare++;L.r[low] = L.r[0]; //当low == high 时， 将枢轴记录放到中间位置L.countMove++;return low; //返回枢轴位置的下标}void QSort(Sqlist1 &L, int low, int high) {L.countCompare++;if (low < high) {int prvotLocal = Partition(L, low, high); //取枢轴记录的下标cout << endl;ShowList(L);QSort(L, low, prvotLocal - 1); //对左子表递归排序QSort(L, prvotLocal + 1, high); //对右子表递归排序}}void QuickSort(Sqlist1 & L) {QSort(L, 1, L.length); //对顺序表调用递归函数}int Partition(Sqlist2 &L, int low, int high) {L.r[0] = L.r[low]; //将第一个记录暂存在缓存单元int protkey = L.r[low].key; //枢轴记录的key值while (low < high) {L.countCompare++;while (low < high && L.r[high].key >= protkey) { //找出右边第一个比key的的记录的记录L.countCompare++;high--;}L.countCompare++;L.r[low] = L.r[high]; //将右边第一个小于prokey的记录移动到low位置L.countMove++;while (low < high && L.r[low].key <= protkey) {L.countCompare++;low++;}L.countCompare++;L.r[high] = L.r[low]; //将左边第一个大于prokey的记录移动到高端high位置L.countMove++;}L.countCompare++;L.r[low] = L.r[0]; //当low == high 时， 将枢轴记录放到中间位置L.countMove++;return low; //返回枢轴位置的下标}void QSort(Sqlist2 &L, int low, int high) {L.countCompare++;if (low < high) {int prvotLocal = Partition(L, low, high); //取枢轴记录的下标QSort(L, low, prvotLocal - 1); //对左子表递归排序QSort(L, prvotLocal + 1, high); //对右子表递归排序}}int Partition(Sqlist3 &L, int low, int high) {L.r[0] = L.r[low]; //将第一个记录暂存在缓存单元int protkey = L.r[low].key; //枢轴记录的key值while (low < high) {L.countCompare++;while (low < high && L.r[high].key >= protkey) { //找出右边第一个比key的的记录的记录L.countCompare++;high--;}L.countCompare++;L.r[low] = L.r[high]; //将右边第一个小于prokey的记录移动到low位置L.countMove++;while (low < high && L.r[low].key <= protkey) {L.countCompare++;low++;}L.countCompare++;L.r[high] = L.r[low]; //将左边第一个大于prokey的记录移动到高端high位置L.countMove++;}L.countCompare++;L.r[low] = L.r[0]; //当low == high 时， 将枢轴记录放到中间位置L.countMove++;return low; //返回枢轴位置的下标}void QSort(Sqlist3 &L, int low, int high) {L.countCompare++;if (low < high) {int prvotLocal = Partition(L, low, high); //取枢轴记录的下标QSort(L, low, prvotLocal - 1); //对左子表递归排序QSort(L, prvotLocal + 1, high); //对右子表递归排序}}void QuickSort(Sqlist3 & L) {QSort(L, 1, L.length); //对顺序表调用递归函数}void QuickSort(Sqlist2 & L) {QSort(L, 1, L.length); //对顺序表调用递归函数}void OperationQuickSort() {Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;QuickSort(L1);ShowList(L1);Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;QuickSort(L2);ShowList(L2);Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;QuickSort(L3);ShowList(L3);}

result

排序前：

40 32 60 65 57 83 18 2 10 2 10 83 40 15 25 65 0 77 19 14

比较次数为：0

移动次数为： 0

排序后：

14 32 19 0 25 15 18 2 10 2 10 40 40 83 83 65 57 77 65 60

比较次数为：39

移动次数为： 13

10 2 10 0 2 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：66

移动次数为： 24

2 2 10 0 10 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：75

移动次数为： 27

0 2 2 10 10 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：86

移动次数为： 32

0 2 2 10 10 14 18 15 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：92

移动次数为： 35

0 2 2 10 10 14 15 18 25 19 32 40 40 83 83 65 57 77 65 60

比较次数为：105

移动次数为： 38

0 2 2 10 10 14 15 18 19 25 32 40 40 83 83 65 57 77 65 60

比较次数为：113

移动次数为： 41

0 2 2 10 10 14 15 18 19 25 32 40 40 83 83 65 57 77 65 60

比较次数为：127

移动次数为： 44

0 2 2 10 10 14 15 18 19 25 32 40 40 60 83 65 57 77 65 83

比较次数为：139

移动次数为： 47

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 83 77 65 83

比较次数为：152

移动次数为： 52

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 83 77 65 83

比较次数为：161

移动次数为： 55

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 65 77 83 83

比较次数为：169

移动次数为： 58

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 65 77 83 83

比较次数为：175

移动次数为： 61

0 2 2 10 10 14 15 18 19 25 32 40 40 57 60 65 65 77 83 83

比较次数为：179

移动次数为： 61

排序前：

73 44 62 54 99 83 75 29 86 57 31 23 52 38 71 38 36 89 58 85

33 19 88 2 9 9 19 19 92 42 94 14 16 4 92 7 3 69 23 38

74 33 2 5 11 54 63 98 26 8 73 9 0 90 49 92 50 73 67 56

32 51 0 72 27 43 62 84 59 31 39 83 85 42 41 83 42 39 33 69

88 62 3 52 9 37 93 71 68 97 76 75 63 27 75 89 14 65 50 0

比较次数为：0

移动次数为： 0

排序后：

0 0 0 2 2 3 3 4 5 7 8 9 9 9 9 11 14 14 16 19

19 19 23 23 26 27 27 29 31 31 32 33 33 33 36 37 38 38 38 39

39 41 42 42 42 43 44 49 50 50 51 52 52 54 54 56 57 58 59 62

62 62 63 63 65 67 68 69 69 71 71 72 73 73 73 74 75 75 75 76

83 83 83 84 85 85 86 88 88 89 89 90 92 92 92 93 94 97 98 99

比较次数为：1368

移动次数为： 396

排序前：

73 44 62 54 99 83 75 29 86 57 31 23 52 38 71 38 36 89 58 85

33 19 88 2 9 9 19 19 92 42 94 14 16 4 92 7 3 69 23 38

74 33 2 5 11 54 63 98 26 8 73 9 0 90 49 92 50 73 67 56

32 51 0 72 27 43 62 84 59 31 39 83 85 42 41 83 42 39 33 69

88 62 3 52 9 37 93 71 68 97 76 75 63 27 75 89 14 65 50 0

9 37 42 5 58 24 17 44 11 79 81 6 83 54 63 95 46 53 66 66

9 75 65 7 21 60 1 89 30 74 73 63 57 8 1 84 9 19 2 29

84 77 94 38 85 22 7 6 61 80 30 78 65 26 92 41 66 60 41 3

2 2 18 7 29 74 9 7 2 68 72 41 84 80 81 64 49 65 53 80

34 44 34 14 98 42 83 20 55 86 10 71 74 54 75 18 87 89 40 70

42 73 2 34 0 90 71 29 36 51 30 65 35 83 18 23 26 6 35 16

36 10 49 7 31 92 70 8 51 79 90 74 48 39 10 24 43 54 42 17

56 43 30 6 98 23 2 29 4 8 80 87 23 56 46 29 72 50 0 50

99 30 45 31 84 35 46 17 25 68 94 15 96 75 16 67 55 34 29 59

1 99 21 19 54 96 12 65 37 58 97 3 45 69 71 88 23 27 63 6

51 80 49 92 21 79 26 36 92 6 96 85 63 95 63 16 32 81 77 84

83 14 97 53 57 8 94 6 52 17 52 81 15 18 81 15 6 13 94 27

31 6 20 52 85 49 51 47 86 18 91 93 41 44 72 73 1 42 20 13

67 71 7 18 84 26 48 1 7 74 29 79 83 86 67 44 0 7 27 0

74 88 91 77 19 78 29 97 7 13 45 16 13 55 26 17 7 28 96 33

88 90 39 18 57 82 93 88 58 50 39 54 15 28 65 92 42 75 82 49

94 48 19 27 41 64 75 4 38 36 26 40 62 85 39 96 88 10 8 49

50 26 9 14 90 86 57 1 9 95 45 8 47 87 77 67 51 62 56 94

20 38 89 21 84 20 79 90 8 2 6 34 48 80 55 39 41 62 95 9

96 61 35 47 76 54 6 96 51 45 9 61 25 43 91 85 86 17 77 32

比较次数为：0

移动次数为： 0

排序后：

0 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2

2 2 3 3 3 3 4 4 4 5 5 6 6 6 6 6 6 6 6 6

6 6 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8

8 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 11 11 12

13 13 13 13 14 14 14 14 14 15 15 15 15 16 16 16 16 16 17 17

17 17 17 17 18 18 18 18 18 18 18 19 19 19 19 19 19 19 20 20

20 20 20 21 21 21 21 22 23 23 23 23 23 23 24 24 25 25 26 26

26 26 26 26 26 26 27 27 27 27 27 27 28 28 29 29 29 29 29 29

29 29 29 30 30 30 30 30 31 31 31 31 31 32 32 32 33 33 33 33

34 34 34 34 34 35 35 35 35 36 36 36 36 36 37 37 37 38 38 38

38 38 38 39 39 39 39 39 39 39 40 40 41 41 41 41 41 41 41 42

42 42 42 42 42 42 42 42 43 43 43 43 44 44 44 44 44 45 45 45

45 45 46 46 46 47 47 47 48 48 48 48 49 49 49 49 49 49 49 50

50 50 50 50 50 51 51 51 51 51 51 51 52 52 52 52 52 53 53 53

54 54 54 54 54 54 54 54 55 55 55 55 56 56 56 56 57 57 57 57

57 58 58 58 58 59 59 60 60 61 61 61 62 62 62 62 62 62 63 63

63 63 63 63 63 64 64 65 65 65 65 65 65 65 66 66 66 67 67 67

67 67 68 68 68 69 69 69 70 70 71 71 71 71 71 71 72 72 72 72

73 73 73 73 73 73 74 74 74 74 74 74 74 75 75 75 75 75 75 75

75 76 76 77 77 77 77 77 78 78 79 79 79 79 79 80 80 80 80 80

80 81 81 81 81 81 82 82 83 83 83 83 83 83 83 83 84 84 84 84

84 84 84 84 85 85 85 85 85 85 85 86 86 86 86 86 86 87 87 87

88 88 88 88 88 88 88 89 89 89 89 89 90 90 90 90 90 90 91 91

91 92 92 92 92 92 92 92 92 93 93 93 94 94 94 94 94 94 94 95

95 95 95 96 96 96 96 96 96 96 97 97 97 97 98 98 98 99 99 99

比较次数为：9030

移动次数为： 2374

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 21528)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

分析

不稳定算法，一位无顺序交换适合顺序结构，不适合链式结构适合n大且无序

简单选择排序

将待排序的的记录中逐个选择关键字最小的记录，按升序排在顺序序列，最后，遍历完所有记录后得到一个升序表数组实现：将待排序的n个记录放在数组中，从第一个记录开始进行n-1趟排序每一趟排序用局部变量k 获取 i位置的记录的下标，再用k与后续记录的记录逐个比较，如果 r[k]较大则更新k为较小记录的下标，遍历数组，最后找出该趟的最小记录下标放在k，如果k位置不是i位置则将两个位置的记录交换，实现i位置存储最小记录

SimpleInsertSort.h

#pragma once#include"Struct.h"void SelectSort(Sqlist1 &L) {for (int i = 1; i < L.length; i++) {L.countCompare++;int k = i;for (int j = i + 1; j <= L.length; j++) {L.countCompare++;if (L.r[j].key < L.r[k].key)k = j;L.countCompare++;}L.countCompare++;if (k != i) {Redtype t = L.r[i];L.countMove++;L.r[i] = L.r[k];L.countMove++;L.r[k] = t;L.countMove++;}L.countCompare++;cout << endl << "第 " << i << " 趟排序 ：" << endl;ShowList(L);}L.countCompare++;}void SelectSort(Sqlist2 &L) {for (int i = 1; i < L.length; i++) {L.countCompare++;int k = i;for (int j = i + 1; j <= L.length; j++) {L.countCompare++;if (L.r[j].key < L.r[k].key)k = j;L.countCompare++;}L.countCompare++;if (k != i) {Redtype t = L.r[i];L.countMove++;L.r[i] = L.r[k];L.countMove++;L.r[k] = t;L.countMove++;}L.countCompare++;}L.countCompare++;}void SelectSort(Sqlist3 &L) {for (int i = 1; i < L.length; i++) {L.countCompare++;int k = i;for (int j = i + 1; j <= L.length; j++) {L.countCompare++;if (L.r[j].key < L.r[k].key)k = j;L.countCompare++;}L.countCompare++;if (k != i) {Redtype t = L.r[i];L.countMove++;L.r[i] = L.r[k];L.countMove++;L.r[k] = t;L.countMove++;}L.countCompare++;}L.countCompare++;}void OperationSelectSort() {cout << "\n********** 20个随机数**********\n";Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;SelectSort(L1);ShowList(L1);cout << "\n\n********** 100个随机数**********\n";Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;SelectSort(L2);ShowList(L2);cout << "\n\n********** 500个随机数**********\n";Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;SelectSort(L3);ShowList(L3);}

结果：

********** 20个随机数**********

排序前：

45 88 78 47 27 5 33 21 25 28 43 96 22 70 96 68 98 68 94 73

比较次数为：0

移动次数为： 0

排序后：

第 1 趟排序 ：

5 88 78 47 27 45 33 21 25 28 43 96 22 70 96 68 98 68 94 73

比较次数为：41

移动次数为： 3

第 2 趟排序 ：

5 21 78 47 27 45 33 88 25 28 43 96 22 70 96 68 98 68 94 73

比较次数为：80

移动次数为： 6

第 3 趟排序 ：

5 21 22 47 27 45 33 88 25 28 43 96 78 70 96 68 98 68 94 73

比较次数为：117

移动次数为： 9

第 4 趟排序 ：

5 21 22 25 27 45 33 88 47 28 43 96 78 70 96 68 98 68 94 73

比较次数为：152

移动次数为： 12

第 5 趟排序 ：

5 21 22 25 27 45 33 88 47 28 43 96 78 70 96 68 98 68 94 73

比较次数为：185

移动次数为： 12

第 6 趟排序 ：

5 21 22 25 27 28 33 88 47 45 43 96 78 70 96 68 98 68 94 73

比较次数为：216

移动次数为： 15

第 7 趟排序 ：

5 21 22 25 27 28 33 88 47 45 43 96 78 70 96 68 98 68 94 73

比较次数为：245

移动次数为： 15

第 8 趟排序 ：

5 21 22 25 27 28 33 43 47 45 88 96 78 70 96 68 98 68 94 73

比较次数为：272

移动次数为： 18

第 9 趟排序 ：

5 21 22 25 27 28 33 43 45 47 88 96 78 70 96 68 98 68 94 73

比较次数为：297

移动次数为： 21

第 10 趟排序 ：

5 21 22 25 27 28 33 43 45 47 88 96 78 70 96 68 98 68 94 73

比较次数为：320

移动次数为： 21

第 11 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 96 78 70 96 88 98 68 94 73

比较次数为：341

移动次数为： 24

第 12 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 78 70 96 88 98 96 94 73

比较次数为：360

移动次数为： 27

第 13 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 78 96 88 98 96 94 73

比较次数为：377

移动次数为： 30

第 14 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 73 96 88 98 96 94 78

比较次数为：392

移动次数为： 33

第 15 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 98 96 94 96

比较次数为：405

移动次数为： 36

第 16 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 98 96 94 96

比较次数为：416

移动次数为： 36

第 17 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 98 96

比较次数为：425

移动次数为： 39

第 18 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 98 96

比较次数为：432

移动次数为： 39

第 19 趟排序 ：

5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 96 98

比较次数为：437

移动次数为： 42

5 21 22 25 27 28 33 43 45 47 68 68 70 73 78 88 94 96 96 98

比较次数为：438

移动次数为： 42

********** 100个随机数**********

排序前：

49 36 42 42 42 31 77 93 37 79 95 40 93 16 21 38 48 26 24 30

12 80 81 23 18 13 38 75 29 97 2 4 61 76 55 8 20 70 57 40

32 70 61 23 43 16 79 36 35 1 92 29 38 1 56 33 29 4 15 29

27 72 80 86 60 34 7 98 7 26 35 40 41 72 59 29 31 68 7 97

94 2 49 25 4 66 21 90 90 50 0 69 84 70 24 40 56 11 44 58

比较次数为：0

移动次数为： 0

排序后：

0 1 1 2 2 4 4 4 7 7 7 8 11 12 13 15 16 16 18 20

21 21 23 23 24 24 25 26 26 27 29 29 29 29 29 30 31 31 32 33

34 35 35 36 36 37 38 38 38 40 40 40 40 41 42 42 42 43 44 48

49 49 50 55 56 56 57 58 59 60 61 61 66 68 69 70 70 70 72 72

75 76 77 79 79 80 80 81 84 86 90 90 92 93 93 94 95 97 97 98

比较次数为：10198

移动次数为： 285

********** 500个随机数**********

排序前：

49 36 42 42 42 31 77 93 37 79 95 40 93 16 21 38 48 26 24 30

12 80 81 23 18 13 38 75 29 97 2 4 61 76 55 8 20 70 57 40

32 70 61 23 43 16 79 36 35 1 92 29 38 1 56 33 29 4 15 29

27 72 80 86 60 34 7 98 7 26 35 40 41 72 59 29 31 68 7 97

94 2 49 25 4 66 21 90 90 50 0 69 84 70 24 40 56 11 44 58

35 87 1 55 4 48 46 46 90 71 60 6 60 19 53 42 95 14 61 92

20 54 74 53 63 20 68 75 75 17 64 59 7 70 39 27 48 10 57 26

20 18 90 67 87 80 35 72 3 34 57 61 93 61 60 96 69 41 14 85

31 4 6 40 64 79 91 18 55 4 72 22 57 20 46 29 49 58 75 68

16 81 53 28 63 91 62 81 75 78 26 76 90 63 87 75 18 73 63 67

27 19 15 48 40 86 35 58 71 33 98 20 97 57 79 8 76 3 92 30

51 99 54 74 5 91 70 67 45 9 22 98 49 86 59 89 47 11 61 36

33 20 3 45 12 30 73 35 61 61 11 54 77 27 20 17 83 96 63 52

97 26 65 18 97 74 47 62 24 48 89 94 70 80 38 0 59 53 22 88

37 74 54 37 35 11 36 96 18 57 83 98 94 29 15 81 63 94 75 45

52 41 10 11 0 48 96 99 11 42 19 31 75 58 70 59 7 90 72 78

88 94 28 41 55 6 20 58 94 32 12 52 51 25 48 17 61 97 76 28

39 96 75 8 62 32 18 32 83 29 66 85 58 68 40 45 41 72 64 1

92 44 41 62 76 92 84 55 14 74 94 69 25 12 34 79 76 61 2 0

17 48 81 20 16 15 39 78 80 35 52 47 7 99 54 18 21 92 28 85

71 36 75 36 79 73 4 20 79 12 6 76 37 89 42 99 98 10 56 36

72 56 55 78 80 69 24 66 12 62 87 15 95 79 90 12 19 20 50 60

55 98 91 66 9 59 0 90 32 2 67 84 16 23 70 27 3 1 33 13

14 37 58 37 8 38 87 73 31 21 99 1 6 35 60 15 95 12 71 73

93 51 92 48 86 47 87 10 55 84 12 67 63 35 7 59 44 25 27 67

比较次数为：0

移动次数为： 0

排序后：

0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 3 3 3 3 4

4 4 4 4 4 4 5 6 6 6 6 6 7 7 7 7 7 7 7 8

8 8 8 9 9 10 10 10 10 11 11 11 11 11 11 12 12 12 12 12

12 12 12 12 13 13 14 14 14 14 15 15 15 15 15 15 16 16 16 16

16 17 17 17 17 18 18 18 18 18 18 18 18 19 19 19 19 20 20 20

20 20 20 20 20 20 20 20 20 21 21 21 21 22 22 22 23 23 23 24

24 24 24 25 25 25 25 26 26 26 26 26 27 27 27 27 27 27 28 28

28 28 29 29 29 29 29 29 29 29 30 30 30 31 31 31 31 31 32 32

32 32 32 33 33 33 33 34 34 34 35 35 35 35 35 35 35 35 35 35

36 36 36 36 36 36 36 37 37 37 37 37 37 38 38 38 38 38 39 39

39 40 40 40 40 40 40 40 41 41 41 41 41 41 42 42 42 42 42 42

43 44 44 44 45 45 45 45 46 46 46 47 47 47 47 48 48 48 48 48

48 48 48 48 49 49 49 49 50 50 51 51 51 52 52 52 52 53 53 53

53 54 54 54 54 54 55 55 55 55 55 55 55 55 56 56 56 56 57 57

57 57 57 57 58 58 58 58 58 58 58 59 59 59 59 59 59 59 60 60

60 60 60 60 61 61 61 61 61 61 61 61 61 61 62 62 62 62 62 63

63 63 63 63 63 63 64 64 64 65 66 66 66 66 67 67 67 67 67 67

68 68 68 68 69 69 69 69 70 70 70 70 70 70 70 70 71 71 71 71

72 72 72 72 72 72 72 73 73 73 73 73 74 74 74 74 74 75 75 75

75 75 75 75 75 75 75 76 76 76 76 76 76 76 77 77 78 78 78 78

79 79 79 79 79 79 79 79 80 80 80 80 80 80 81 81 81 81 81 83

83 83 84 84 84 84 85 85 85 86 86 86 86 87 87 87 87 87 87 88

88 89 89 89 90 90 90 90 90 90 90 90 91 91 91 91 92 92 92 92

92 92 92 93 93 93 93 94 94 94 94 94 94 94 95 95 95 95 96 96

96 96 96 97 97 97 97 97 97 98 98 98 98 98 98 99 99 99 99 99

比较次数为：250998

移动次数为： 1473

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 19964)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

分析：

该算法稳定比较次数增多，移动次数减少，当单个记录占用空间大的时候适合使用适用于链式结构

堆排序

堆的性质：n个元素序列{k1,k2,k3,kn} 中ki >=k2i and ki >=k2i+1（大根堆，双亲结点大于孩子结点）或者小根堆大根堆定义：非终端叶字结点的值均不小于其孩子结点，上大下小小根堆定义：非终端叶子结点的值均不大于其孩子结点，上小下大

堆排序思想：

将无序的n个记录排成无序的完全二叉树初建堆：调整法构造成大根堆对于n个结点的序列，将根结点与最后一个结点交换，把最大值的记录放在序列尾部，此时破环剩余的前n-1大根堆结构，再次调整堆成大根堆，再对n-1个结点的大根堆进行交换操作，直到最后的的子树剩下一个记录为止，此时无序序列成为升序序列进行n-1次堆排序就排成升序序列

1筛选法调整堆

在交换首位记录后，除了根结点都满足大根堆的性质，从上往下对一条路的结点进行调整，将左右子树的较大值的结点与根结点进行交换，再对该子树进行相同的操作，直到叶子结点为止。像筛子一样把大的往上，小的往下，成为新的大根堆

2建初堆

再n个结点的完全二叉树中，大于n/2的结点都是叶子，因此以这些结点为根的子树都是堆，所以，从n/2-1的结点开始往前调整为堆，即调整n/2次可建立一个初堆

*每一趟调整中，s记录根节点的地址，先将新的根结点的值暂存到缓存单元rc，从缓存单元的结点的值与孩子结点中的较大值比较，如果比孩子结点的值大即停止比较，已成大根堆，退出本次调整堆操作；如果比孩子结点的值小，则将孩子结点的较大值填到根节点位置，孩子结点的位置作为新的根结点进行堆该新子树进行调整，s更新为新的根节点的下标，直到新的子树满足大根堆为止

*完成调整n/2次后无序序列成为大根堆

HeapSortion.h

#pragma once#include"Struct.h"//调整堆void HeapAdjust(Sqlist1 &L, int s, int m) {Redtype rigister = L.r[s]; //存储要调整的二叉树的起始根结点for (int i = 2 * s; i <= m; i *= 2) {L.countCompare++;if (i < m &&L.r[i].key < L.r[i + 1].key) //获取孩子结点中key值较大的结点i++; L.countCompare++;L.countCompare++;if (rigister.key >= L.r[i].key) //当前子树根节点key值比孩子结点都大，已经为大根堆break;L.r[s] = L.r[i]; //将key值大的孩子结点移动到key值较小的根结点原来的位置L.countMove++;s = i;//找不到合适的位置，则以当前孩子结点作为根结点在其子树根结点，继续查找位置，直到叶字找到或者到了叶子结点}L.countCompare++;L.r[s] = rigister;L.countMove++;}//建初堆void Createheap(Sqlist1 &L) {int number = L.length;for (int i = number / 2; i > 0; --i) {L.countCompare++;HeapAdjust(L, i, number);}L.countCompare++;}//堆排序void HeapSort(Sqlist1 &L) {Createheap(L);for (int i = L.length; i > 1; i--) { L.countCompare++;Redtype rigister = L.r[1]; //根结点与子树的最后一个叶子结点交换记录L.countMove++;L.r[1] = L.r[i];L.countMove++;L.r[i] = rigister;L.countMove++;HeapAdjust(L, 1, i - 1); //将剩下的无序序列重新调整为大根堆序列}L.countCompare++;}//调整堆void HeapAdjust(Sqlist2 &L, int s, int m) {Redtype rigister = L.r[s]; //存储要调整的二叉树的起始根结点for (int i = 2 * s; i <= m; i *= 2) {L.countCompare++;if (i < m &&L.r[i].key < L.r[i + 1].key) //获取孩子结点中key值较大的结点i++;L.countCompare++;L.countCompare++;if (rigister.key >= L.r[i].key) //当前子树根节点key值比孩子结点都大，已经为大根堆break;L.r[s] = L.r[i]; //将key值大的孩子结点移动到key值较小的根结点原来的位置L.countMove++;s = i;//找不到合适的位置，则以当前孩子结点作为根结点在其子树根结点，继续查找位置，直到叶字找到或者到了叶子结点}L.countCompare++;L.r[s] = rigister;L.countMove++;}//建初堆void Createheap(Sqlist2 &L) {int number = L.length;for (int i = number / 2; i > 0; --i) {L.countCompare++;HeapAdjust(L, i, number);}L.countCompare++;}//堆排序void HeapSort(Sqlist2 &L) {Createheap(L);for (int i = L.length; i > 1; i--) {L.countCompare++;Redtype rigister = L.r[1]; //根结点与子树的最后一个叶子结点交换记录L.countMove++;L.r[1] = L.r[i];L.countMove++;L.r[i] = rigister;L.countMove++;HeapAdjust(L, 1, i - 1); //将剩下的无序序列重新调整为大根堆序列}L.countCompare++;}//调整堆void HeapAdjust(Sqlist3 &L, int s, int m) {Redtype rigister = L.r[s]; //存储要调整的二叉树的起始根结点for (int i = 2 * s; i <= m; i *= 2) {L.countCompare++;if (i < m &&L.r[i].key < L.r[i + 1].key) //获取孩子结点中key值较大的结点i++;L.countCompare++;L.countCompare++;if (rigister.key >= L.r[i].key) //当前子树根节点key值比孩子结点都大，已经为大根堆break;L.r[s] = L.r[i]; //将key值大的孩子结点移动到key值较小的根结点原来的位置L.countMove++;s = i;//找不到合适的位置，则以当前孩子结点作为根结点在其子树根结点，继续查找位置，直到叶字找到或者到了叶子结点}L.countCompare++;L.r[s] = rigister;L.countMove++;}//建初堆void Createheap(Sqlist3 &L) {int number = L.length;for (int i = number / 2; i > 0; --i) {L.countCompare++;HeapAdjust(L, i, number);}L.countCompare++;}//堆排序void HeapSort(Sqlist3 &L) {Createheap(L);for (int i = L.length; i > 1; i--) {L.countCompare++;Redtype rigister = L.r[1]; //根结点与子树的最后一个叶子结点交换记录L.countMove++;L.r[1] = L.r[i];L.countMove++;L.r[i] = rigister;L.countMove++;HeapAdjust(L, 1, i - 1); //将剩下的无序序列重新调整为大根堆序列}L.countCompare++;}void OperationHeapSort() {cout << "\n********** 20个随机数**********\n";Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;HeapSort(L1);ShowList(L1);cout << "\n\n********** 100个随机数**********\n";Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;HeapSort(L2);ShowList(L2);cout << "\n\n********** 500个随机数**********\n";Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);HeapSort(L3);cout << endl;cout << "\n排序后： \n" << endl;ShowList(L3);}

result

********** 20个随机数**********

排序前：

42 96 98 62 43 16 99 77 46 68 88 90 23 98 79 73 19 66 60 65

比较次数为：0

移动次数为： 0

排序后：

16 19 23 42 43 46 60 62 65 66 68 73 77 79 88 90 96 98 98 99

比较次数为：231

移动次数为： 134

********** 100个随机数**********

排序前：

42 96 98 62 43 16 99 77 46 68 88 90 23 98 79 73 19 66 60 65

87 31 41 51 41 19 13 95 54 86 67 97 98 79 4 40 73 10 12 81

83 1 61 88 86 26 58 19 35 41 47 43 98 98 36 46 26 5 95 93

73 52 34 19 63 68 69 63 13 76 76 47 68 14 28 36 91 55 31 39

33 18 65 29 25 36 8 43 64 2 39 9 25 18 22 77 59 51 13 62

比较次数为：0

移动次数为： 0

排序后：

1 2 4 5 8 9 10 12 13 13 13 14 16 18 18 19 19 19 19 22

23 25 25 26 26 28 29 31 31 33 34 35 36 36 36 39 39 40 41 41

41 42 43 43 43 46 46 47 47 51 51 52 54 55 58 59 60 61 62 62

63 63 64 65 65 66 67 68 68 68 69 73 73 73 76 76 77 77 79 79

81 83 86 86 87 88 88 90 91 93 95 95 96 97 98 98 98 98 98 99

比较次数为：1830

移动次数为： 909

********** 500个随机数**********

排序前：

42 96 98 62 43 16 99 77 46 68 88 90 23 98 79 73 19 66 60 65

87 31 41 51 41 19 13 95 54 86 67 97 98 79 4 40 73 10 12 81

83 1 61 88 86 26 58 19 35 41 47 43 98 98 36 46 26 5 95 93

73 52 34 19 63 68 69 63 13 76 76 47 68 14 28 36 91 55 31 39

33 18 65 29 25 36 8 43 64 2 39 9 25 18 22 77 59 51 13 62

60 40 96 53 12 59 26 30 40 37 1 80 40 96 69 43 31 12 18 38

58 88 43 12 30 54 16 9 93 40 96 45 83 71 31 9 13 71 78 47

67 56 65 7 6 97 23 85 44 24 25 85 63 25 7 81 40 66 24 86

17 98 53 33 41 69 99 54 50 39 37 70 6 72 74 90 58 60 69 64

64 78 74 6 49 62 81 76 3 95 9 33 35 74 92 93 29 73 9 21

50 39 38 63 91 45 9 20 72 44 16 67 16 47 72 44 35 35 78 65

35 53 27 12 63 5 30 33 45 61 59 37 23 67 83 71 85 38 1 22

77 62 19 27 62 7 77 44 21 32 93 97 16 24 59 74 5 80 23 10

80 7 9 22 28 71 52 13 51 16 43 42 79 82 4 55 27 6 41 5

23 28 91 99 63 24 9 67 10 42 2 55 25 64 2 61 5 18 34 53

23 19 50 94 3 87 39 7 3 59 42 27 9 85 15 7 18 40 4 32

40 54 72 80 74 12 79 32 46 65 21 36 92 51 63 50 21 51 65 15

83 19 45 34 91 85 43 38 26 33 61 72 80 95 44 9 82 43 0 10

56 21 48 48 54 88 46 44 58 0 66 92 53 10 40 15 1 61 31 19

0 95 91 56 91 38 71 75 73 44 84 92 21 75 56 92 1 9 50 6

16 11 61 61 71 56 43 85 83 69 40 54 46 58 59 38 19 3 13 57

67 44 7 12 14 14 28 9 25 32 56 60 49 16 51 22 24 21 58 21

2 48 42 28 74 54 89 76 94 30 69 80 52 75 39 57 19 69 89 89

18 7 99 56 59 67 71 92 31 37 12 25 64 60 12 68 91 22 28 53

23 83 15 78 81 69 33 15 73 59 67 67 36 54 4 76 32 67 66 89

比较次数为：0

移动次数为： 0

排序后：

0 0 0 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4

5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 7 8 9

9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 11 12 12 12

12 12 12 12 12 12 13 13 13 13 13 13 14 14 14 15 15 15 15 15

16 16 16 16 16 16 16 16 17 18 18 18 18 18 18 19 19 19 19 19

19 19 19 19 19 20 21 21 21 21 21 21 21 21 22 22 22 22 22 23

23 23 23 23 23 23 24 24 24 24 24 25 25 25 25 25 25 25 26 26

26 26 27 27 27 27 28 28 28 28 28 28 29 29 30 30 30 30 31 31

31 31 31 31 32 32 32 32 32 33 33 33 33 33 33 34 34 34 35 35

35 35 35 36 36 36 36 36 37 37 37 37 38 38 38 38 38 38 39 39

39 39 39 39 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 42

42 42 42 42 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44

44 45 45 45 45 46 46 46 46 46 47 47 47 47 48 48 48 49 49 50

50 50 50 50 51 51 51 51 51 51 52 52 52 53 53 53 53 53 53 54

54 54 54 54 54 54 54 55 55 55 56 56 56 56 56 56 56 57 57 58

58 58 58 58 58 59 59 59 59 59 59 59 59 60 60 60 60 60 61 61

61 61 61 61 61 62 62 62 62 62 63 63 63 63 63 63 63 64 64 64

64 64 65 65 65 65 65 65 66 66 66 66 67 67 67 67 67 67 67 67

67 67 68 68 68 68 69 69 69 69 69 69 69 69 70 71 71 71 71 71

71 71 72 72 72 72 72 73 73 73 73 73 73 74 74 74 74 74 74 75

75 75 76 76 76 76 76 77 77 77 77 78 78 78 78 79 79 79 79 80

80 80 80 80 80 81 81 81 81 82 82 83 83 83 83 83 83 84 85 85

85 85 85 85 86 86 86 87 87 88 88 88 88 89 89 89 89 90 90 91

91 91 91 91 91 91 92 92 92 92 92 92 93 93 93 93 94 94 95 95

95 95 95 96 96 96 96 97 97 97 98 98 98 98 98 98 99 99 99 99

比较次数为：12585

移动次数为： 5746

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 4100)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

分析：

算法是不稳定的不可以用于链式存储结构建立堆的时候，进行比较堆的比较操作，当记录数n较小的时候不适用，使用于n较大的适用，性能比一般的插入选择排序快，但是性能比不上快排。

归并排序

归并是指将2或多个有序序列进行合并成一个有序表

思想

初始序列是由n个记录构造，可以看作n个长度为1的子序列，然后子序列两两合并成[n/2]个子序列，再重复两两合并，直到得到一个长度为n的有序序列。

1，相邻两个序列表的归并

将待归并的顺序表从中间划分两个有序的相邻的子表，将两个子表中从头开始取一记录进行比较，将较小者先存入目标表，更新位置计数单元，直到一个子表为空为止将剩余的非空的有序的子表的元素都添加到目标表中实现了两个子表归并

2,归并排序数组实现

2路归并将待排序序列表的记录归并并排序到目标序列表中，当待排序表长度为1时候停止排序，长度非1则1，将序列表分为两个字表，先对子表进行递归归并函数，不断层层深入2，将已经递归结束的两个子表的有序序列进行归并

MergingSort.h

#pragma once#include"Struct.h"void Merge(Sqlist1 R, Sqlist1 &T, int low, int mid, int high) {int i = low; int j = mid + 1; int k = low;while (i <= mid && j <= high) { //确定比较范围都在子序列表的范围之内T.countCompare++;if (R.r[i].key <= R.r[j].key) {T.r[k++] = R.r[i++]; //先取值再++,后序列值较大T.countMove++;}else {T.r[k++] = R.r[j++]; //先序列值较大T.countMove++;}T.countCompare++;}T.countCompare++;while (i <= mid) {//将先序序列所有剩余记录刷出T.r[k++] = R.r[i++];T.countCompare++;T.countMove++;}T.countCompare++;while (j <= high) {//将后续序列所有剩余记录刷出T.r[k++] = R.r[j++];T.countCompare++;T.countMove++;}T.countCompare++;}void MSort(Sqlist1 R, Sqlist1 &T, int low, int high) {if (low == high) { //序列只剩一个元素，已经排序完成，将其存储到引用顺序表中T.r[low] = R.r[low];T.countMove++;}else {int mid = (low + high) / 2; //获取中间序列值Sqlist1 Temp;MSort(R, Temp, low, mid);MSort(R, Temp, mid + 1, high);Merge(Temp, T, low, mid, high);}T.countCompare++;}void MergeSort(Sqlist1 &L) {MSort(L, L, 1, L.length);}void Merge(Sqlist2 R, Sqlist2 &T, int low, int mid, int high) {T.countCompare = R.countCompare;T.countMove = R.countMove;int i = low; int j = mid + 1; int k = low;while (i <= mid && j <= high) { //确定比较范围都在子序列表的范围之内T.countCompare++;if (R.r[i].key <= R.r[j].key) {T.r[k++] = R.r[i++]; //先取值再++,后序列值较大T.countMove++;}else {T.r[k++] = R.r[j++]; //先序列值较大T.countMove++;}T.countCompare++;}T.countCompare++;while (i <= mid) {//将先序序列所有剩余记录刷出T.r[k++] = R.r[i++];T.countCompare++;T.countMove++;}T.countCompare++;while (j <= high) {//将后续序列所有剩余记录刷出T.r[k++] = R.r[j++];T.countCompare++;T.countMove++;}T.countCompare++;}void MSort(Sqlist2 R, Sqlist2 &T, int low, int high) {if (low == high) { //序列只剩一个元素，已经排序完成，将其存储到引用顺序表中T.r[low] = R.r[low];T.countMove++;}else {int mid = (low + high) / 2; //获取中间序列值Sqlist2 Temp;MSort(R, Temp, low, mid);MSort(R, Temp, mid + 1, high);Merge(Temp, T, low, mid, high);}T.countCompare++;}void MergeSort(Sqlist2 &L) {MSort(L, L, 1, L.length);}void Merge(Sqlist3 R, Sqlist3 &T, int low, int mid, int high) {int i = low; int j = mid + 1; int k = low;while (i <= mid && j <= high) { //确定比较范围都在子序列表的范围之内T.countCompare++;if (R.r[i].key <= R.r[j].key) {T.r[k++] = R.r[i++]; //先取值再++,后序列值较大T.countMove++;}else {T.r[k++] = R.r[j++]; //先序列值较大T.countMove++;}T.countCompare++;}T.countCompare++;while (i <= mid) {//将先序序列所有剩余记录刷出T.r[k++] = R.r[i++];T.countCompare++;T.countMove++;}T.countCompare++;while (j <= high) {//将后续序列所有剩余记录刷出T.r[k++] = R.r[j++];T.countCompare++;T.countMove++;}T.countCompare++;}void MSort(Sqlist3 R, Sqlist3 &T, int low, int high) {if (low == high) { //序列只剩一个元素，已经排序完成，将其存储到引用顺序表中T.r[low] = R.r[low];T.countMove++;}else {int mid = (low + high) / 2; //获取中间序列值Sqlist3 Temp;MSort(R, Temp, low, mid);MSort(R, Temp, mid + 1, high);Merge(Temp, T, low, mid, high);}T.countCompare++;}void MergeSort(Sqlist3 &L) {MSort(L, L, 1, L.length);}void OperationMergeSort() {Sqlist1 L1;CreateList(L1);cout << "\n排序前： \n" << endl;ShowList(L1);cout << endl;cout << "\n排序后： \n" << endl;MergeSort(L1);ShowList(L1);Sqlist2 L2;CreateList(L2);cout << "\n排序前： \n" << endl;ShowList(L2);cout << endl;cout << "\n排序后： \n" << endl;MergeSort(L2);ShowList(L2);Sqlist3 L3;CreateList(L3);cout << "\n排序前： \n" << endl;ShowList(L3);cout << endl;cout << "\n排序后： \n" << endl;MergeSort(L3);ShowList(L3);}

result

排序前：

81 10 16 66 57 81 81 92 60 43 93 10 57 62 41 73 0 89 75 58

比较次数为：0

移动次数为： 0

排序后：

0 10 10 16 41 43 57 57 58 60 62 66 73 75 81 81 81 89 92 93

比较次数为：43

移动次数为： 20

排序前：

81 10 16 66 57 81 81 92 60 43 93 10 57 62 41 73 0 89 75 58

91 24 80 41 24 68 55 55 49 55 25 9 22 75 55 13 51 34 99 93

62 10 16 86 85 13 71 39 91 56 82 78 91 68 54 74 2 73 46 6

54 15 88 93 18 29 31 70 16 80 28 65 64 11 21 7 95 76 73 82

72 36 33 17 50 34 34 19 3 33 12 17 99 99 70 41 84 84 60 48

比较次数为：0

移动次数为： 0

排序后：

0 2 3 6 7 9 10 10 10 11 12 13 13 15 16 16 16 17 17 18

19 21 22 24 24 25 28 29 31 33 33 34 34 34 36 39 41 41 41 43

46 48 49 50 51 54 54 55 55 55 55 56 57 57 58 60 60 62 62 64

65 66 68 68 70 70 71 72 73 73 73 74 75 75 76 78 80 80 81 81

81 82 82 84 84 85 86 88 89 91 91 91 92 93 93 93 95 99 99 99

比较次数为：414

移动次数为： 201

排序前：

81 10 16 66 57 81 81 92 60 43 93 10 57 62 41 73 0 89 75 58

91 24 80 41 24 68 55 55 49 55 25 9 22 75 55 13 51 34 99 93

62 10 16 86 85 13 71 39 91 56 82 78 91 68 54 74 2 73 46 6

54 15 88 93 18 29 31 70 16 80 28 65 64 11 21 7 95 76 73 82

72 36 33 17 50 34 34 19 3 33 12 17 99 99 70 41 84 84 60 48

36 88 86 32 55 12 53 90 38 79 98 46 64 24 29 65 53 98 52 66

41 41 33 72 22 91 81 86 12 25 26 88 59 6 85 21 66 68 60 54

67 62 12 50 99 86 6 70 43 48 91 51 71 87 24 14 86 23 15 35

6 26 52 13 94 34 55 41 9 39 26 1 25 81 5 91 19 49 4 73

93 93 29 83 93 96 7 7 52 75 54 69 51 69 27 12 44 53 42 99

72 13 7 59 20 76 50 68 46 41 67 38 69 19 20 78 20 93 36 13

70 11 64 44 38 60 47 92 41 57 83 52 60 14 26 81 52 68 75 90

47 54 70 52 37 0 45 23 39 64 4 41 59 11 1 19 7 45 8 18

78 96 34 91 48 62 77 11 18 27 96 72 99 48 66 92 53 54 0 83

54 31 38 66 60 35 7 66 75 30 46 50 78 60 35 17 29 13 58 48

41 38 44 39 24 47 39 61 99 51 73 61 78 81 8 82 79 96 72 94

69 25 28 99 21 63 82 70 70 19 34 85 42 6 9 86 57 40 45 52

93 9 99 70 66 65 12 9 15 84 14 55 29 33 31 37 52 28 54 33

51 96 76 33 31 77 29 18 75 17 40 48 43 94 4 61 90 69 55 92

64 9 31 73 40 93 96 62 78 30 21 95 96 65 26 1 54 20 65 47

4 31 55 90 47 89 98 27 94 8 81 63 47 93 76 78 96 43 36 23

99 95 69 51 78 40 90 84 47 84 96 92 11 71 20 42 75 26 78 68

7 66 98 81 15 78 88 13 8 54 2 99 76 26 39 38 8 3 17 35

4 64 24 46 8 87 1 27 18 85 28 91 96 23 90 95 48 83 29 88

57 58 13 55 0 79 22 35 46 68 55 98 23 39 99 40 88 33 39 90

比较次数为：0

移动次数为： 0

排序后：

0 0 0 0 1 1 1 1 2 2 3 3 4 4 4 4 4 5 6 6

6 6 6 7 7 7 7 7 7 7 8 8 8 8 8 8 9 9 9 9

9 9 10 10 10 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13

13 13 13 13 14 14 14 15 15 15 15 16 16 16 17 17 17 17 17 18

18 18 18 18 19 19 19 19 19 20 20 20 20 20 21 21 21 21 22 22

22 23 23 23 23 23 24 24 24 24 24 24 25 25 25 25 26 26 26 26

26 26 26 27 27 27 27 28 28 28 28 29 29 29 29 29 29 29 30 30

31 31 31 31 31 31 32 33 33 33 33 33 33 33 34 34 34 34 34 34

35 35 35 35 35 36 36 36 36 37 37 38 38 38 38 38 38 39 39 39

39 39 39 39 39 40 40 40 40 40 41 41 41 41 41 41 41 41 41 41

42 42 42 43 43 43 43 44 44 44 45 45 45 46 46 46 46 46 46 47

47 47 47 47 47 47 48 48 48 48 48 48 48 49 49 50 50 50 50 51

51 51 51 51 51 52 52 52 52 52 52 52 52 53 53 53 53 54 54 54

54 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 56 57

57 57 57 57 58 58 58 59 59 59 60 60 60 60 60 60 60 61 61 61

62 62 62 62 62 63 63 64 64 64 64 64 64 65 65 65 65 65 66 66

66 66 66 66 66 66 67 67 68 68 68 68 68 68 68 69 69 69 69 69

69 70 70 70 70 70 70 70 70 71 71 71 72 72 72 72 72 73 73 73

73 73 73 74 75 75 75 75 75 75 75 76 76 76 76 76 77 77 78 78

78 78 78 78 78 78 78 78 79 79 79 80 80 81 81 81 81 81 81 81

81 81 82 82 82 82 83 83 83 83 84 84 84 84 84 85 85 85 85 86

86 86 86 86 86 87 87 88 88 88 88 88 88 89 89 90 90 90 90 90

90 90 91 91 91 91 91 91 91 91 92 92 92 92 92 93 93 93 93 93

93 93 93 93 93 94 94 94 94 95 95 95 95 96 96 96 96 96 96 96

96 96 96 98 98 98 98 98 99 99 99 99 99 99 99 99 99 99 99 99

比较次数为：997

移动次数为： 500

D:\visual studio \数据结构\Sort_experiment4\Debug\Sort_experiment4.exe (进程 508)已退出，返回代码为: 0。

若要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。

按任意键关闭此窗口…

####分析：

算法稳定移动次数等于待排序次数，比较高效的一个算法

如果觉得《简单入门排序算法（直接插入排序 折半插入排序 希尔排序 冒泡排序 堆排序 归并排序）》对你有帮助，请点赞、收藏，并留下你的观点哦！