/** * 排序算法集合 * * author Fan Min minfanphd163.com. */ #include stdio.h #include malloc.h #include stdbool.h #define TABLE_SIZE 19 /** * 键值对节点结构体 */ typedef struct Node{ int key; // 键 char value; // 值 }Node, *NodePtr; /** * 顺序表结构体 */ typedef struct SequentialList{ int length; // 长度 NodePtr elements; // 元素数组 }SequentialList, *ListPtr; /** * 初始化数据数组 */ ListPtr initList(int* paraKeys, char* paraValues, int paraLength){ int i; ListPtr resultPtr (ListPtr)malloc(sizeof(struct SequentialList)); resultPtr-length paraLength; resultPtr-elements (NodePtr)malloc(paraLength * sizeof(struct Node)); for (i 0; i paraLength; i ){ //printf(设置索引 %d 的键为 %d值为 %c\r\n, i, paraKeys[i], paraValues[i]); resultPtr-elements[i].key paraKeys[i]; resultPtr-elements[i].value paraValues[i]; }// 循环结束 return resultPtr; }// 初始化函数结束 /** * 打印列表 */ void printList(ListPtr paraPtr) { int i; printf((键, 值)\r\n); for (i 0; i paraPtr-length; i ) { printf(%d\t, paraPtr-elements[i].key); }// 循环结束 printf(\r\n); for (i 0; i paraPtr-length; i ) { printf(%c\t, paraPtr-elements[i].value); }// 循环结束 printf(\r\n); }// 打印函数结束 /** * 插入排序。paraPtr-elements[0]不存储有效数据其键值应小于任何有效键值。 */ void insertionSort(ListPtr paraPtr) { Node tempNode; int j; for (int i 2; i paraPtr-length; i) { tempNode paraPtr-elements[i]; // 查找插入位置同时移动其他节点 for (j i - 1; paraPtr-elements[j].key tempNode.key; j--) { paraPtr-elements[j 1] paraPtr-elements[j]; } // 内层循环结束 // 插入 paraPtr-elements[j 1] tempNode; } // 外层循环结束 }// 插入排序结束 /** * 测试插入排序 */ void insertionSortTest() { int tempUnsortedKeys[] { -100, 5, 3, 6, 10, 7, 1, 9 }; char tempContents[] { n, i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 8); printf(\r\n插入排序前:\r\n); printList(tempList); insertionSort(tempList); printf(\r\n插入排序后:\r\n); printList(tempList); }// 插入排序测试结束 /** * 希尔排序 */ void shellSort(ListPtr paraPtr) { Node tempNode; int tempJumpArray[] { 5, 3, 1 }; int tempJump; int p, i, j, k; for (i 0; i 3; i) { tempJump tempJumpArray[i]; for (j 0; j tempJump; j) { for (k j tempJump; k paraPtr-length; k tempJump) { tempNode paraPtr-elements[k]; // 查找插入位置同时移动其他节点 for (p k - tempJump; p 0; p - tempJump) { if (paraPtr-elements[p].key tempNode.key) { paraPtr-elements[p tempJump] paraPtr-elements[p]; } else { break; } // 条件判断结束 } // 内层循环结束 // 插入 paraPtr-elements[p tempJump] tempNode; } // 循环结束 } // 循环结束 } // 循环结束 }// 希尔排序结束 /** * 测试希尔排序 */ void shellSortTest() { int tempUnsortedKeys[] {5, 3, 6, 10, 7, 1, 9 }; char tempContents[] {i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 7); printf(\r\n希尔排序前:\r\n); printList(tempList); shellSort(tempList); printf(\r\n希尔排序后:\r\n); printList(tempList); }// 希尔排序测试结束 /** * 冒泡排序 */ void bubbleSort(ListPtr paraPtr) { bool tempSwapped; Node tempNode; int i, j; for (i paraPtr-length - 1; i 0; i--) { tempSwapped false; for (j 0; j i; j) { if (paraPtr-elements[j].key paraPtr-elements[j 1].key) { // 交换 tempNode paraPtr-elements[j 1]; paraPtr-elements[j 1] paraPtr-elements[j]; paraPtr-elements[j] tempNode; tempSwapped true; } // 条件判断结束 } // 内层循环结束 // 本轮没有交换数据已有序 if (!tempSwapped) { printf(提前结束排序。\r\n); break; } // 条件判断结束 } // 外层循环结束 }// 冒泡排序结束 /** * 测试冒泡排序 */ void bubbleSortTest() { int tempUnsortedKeys[] {5, 3, 6, 10, 7, 1, 9 }; char tempContents[] {i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 7); printf(\r\n冒泡排序前:\r\n); printList(tempList); shellSort(tempList); printf(\r\n冒泡排序后:\r\n); printList(tempList); }// 冒泡排序测试结束 /** * 快速排序递归 */ void quickSortRecursive(ListPtr paraPtr, int paraStart, int paraEnd) { int tempPivot, tempLeft, tempRight; Node tempNodeForSwap; // 无需排序 if (paraStart paraEnd) { return; } // 条件判断结束 tempPivot paraPtr-elements[paraEnd].key; tempLeft paraStart; tempRight paraEnd - 1; // 为基准元素寻找正确位置同时将较小元素移到左边较大元素移到右边 while (true) { while ((paraPtr-elements[tempLeft].key tempPivot) (tempLeft tempRight)) { tempLeft; } // 循环结束 while ((paraPtr-elements[tempRight].key tempPivot) (tempLeft tempRight)) { tempRight--; } // 循环结束 if (tempLeft tempRight) { // 交换 tempNodeForSwap paraPtr-elements[tempLeft]; paraPtr-elements[tempLeft] paraPtr-elements[tempRight]; paraPtr-elements[tempRight] tempNodeForSwap; } else { break; } // 条件判断结束 } // 循环结束 // 交换 if (paraPtr-elements[tempLeft].key tempPivot) { tempNodeForSwap paraPtr-elements[paraEnd]; paraPtr-elements[paraEnd] paraPtr-elements[tempLeft]; paraPtr-elements[tempLeft] tempNodeForSwap; } else { tempLeft; } // 条件判断结束 quickSortRecursive(paraPtr, paraStart, tempLeft - 1); quickSortRecursive(paraPtr, tempLeft 1, paraEnd); }// 快速排序递归结束 /** * 快速排序 */ void quickSort(ListPtr paraPtr) { quickSortRecursive(paraPtr, 0, paraPtr-length - 1); }// 快速排序结束 /** * 测试快速排序 */ void quickSortTest() { int tempUnsortedKeys[] {5, 3, 6, 10, 7, 1, 9 }; char tempContents[] {i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 7); printf(\r\n快速排序前:\r\n); printList(tempList); quickSort(tempList); printf(\r\n快速排序后:\r\n); printList(tempList); }// 快速排序测试结束 /** * 选择排序 */ void selectionSort(ListPtr paraPtr) { Node tempNode; int tempIndexForSmallest, i, j; for (i 0; i paraPtr-length - 1; i) { // 初始化 tempNode paraPtr-elements[i]; tempIndexForSmallest i; for (j i 1; j paraPtr-length; j) { if (paraPtr-elements[j].key tempNode.key) { tempNode paraPtr-elements[j]; tempIndexForSmallest j; } // 条件判断结束 } // 内层循环结束 // 将选中的最小元素与当前位置交换 paraPtr-elements[tempIndexForSmallest] paraPtr-elements[i]; paraPtr-elements[i] tempNode; } // 外层循环结束 }// 选择排序结束 /** * 测试选择排序 */ void selectionSortTest() { int tempUnsortedKeys[] {5, 3, 6, 10, 7, 1, 9 }; char tempContents[] {i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 7); printf(\r\n选择排序前:\r\n); printList(tempList); selectionSort(tempList); printf(\r\n选择排序后:\r\n); printList(tempList); }// 选择排序测试结束 /** * 调整堆最大堆 */ void adjustHeap(ListPtr paraPtr, int paraStart, int paraLength) { Node tempNode paraPtr-elements[paraStart]; int tempParent paraStart; int tempKey paraPtr-elements[paraStart].key; for (int tempChild paraStart * 2 1; tempChild paraLength; tempChild tempChild * 2 1) { // 右孩子更大 if (tempChild 1 paraLength) { if (paraPtr-elements[tempChild].key paraPtr-elements[tempChild 1].key) { tempChild; } // 条件判断结束 } // 条件判断结束 printf(父节点位置为 %d子节点位置为 %d。\r\n, tempParent, tempChild); if (tempKey paraPtr-elements[tempChild].key) { // 子节点更大上移 paraPtr-elements[tempParent] paraPtr-elements[tempChild]; printf(将 %d 移动到位置 %d。\r\n, paraPtr-elements[tempChild].key, tempParent); tempParent tempChild; } else { break; } // 条件判断结束 } // 循环结束 printf(将 %d 移动到位置 %d。\r\n, tempNode.key, tempParent); paraPtr-elements[tempParent] tempNode; }// 调整堆结束 /** * 堆排序 */ void heapSort(ListPtr paraPtr) { Node tempNode; int i; // 第一步构建初始大根堆 for (i paraPtr-length / 2 - 1; i 0; i--) { adjustHeap(paraPtr, i, paraPtr-length); } // 循环结束 // 第二步交换堆顶与末尾并重新调整 for (i paraPtr-length - 1; i 0; i--) { tempNode paraPtr-elements[0]; paraPtr-elements[0] paraPtr-elements[i]; paraPtr-elements[i] tempNode; adjustHeap(paraPtr, 0, i); printf(第 %d 轮, (paraPtr-length - i)); printList(paraPtr); } // 循环结束 }// 堆排序结束 /** * 测试堆排序 */ void heapSortTest() { int tempUnsortedKeys[] {5, 3, 6, 10, 7, 1, 9 }; char tempContents[] {i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 7); printf(\r\n堆排序前:\r\n); printList(tempList); heapSort(tempList); printf(\r\n堆排序后:\r\n); printList(tempList); }// 堆排序测试结束 /** * 归并排序 */ void mergeSort(ListPtr paraPtr) { // 第一步分配空间 int tempRow; // 当前行 int tempGroups; // 组数 int tempActualRow; // 实际行0或1 int tempNextRow 0; int tempGroupNumber; int tempFirstStart, tempSecondStart, tempSecondEnd; int tempFirstIndex, tempSecondIndex; int tempNumCopied; int i; int tempSize; Node** tempMatrix (Node**)malloc(2 * sizeof(Node*)); tempMatrix[0] (Node*)malloc(paraPtr-length * sizeof(Node)); tempMatrix[1] (Node*)malloc(paraPtr-length * sizeof(Node)); for (i 0; i paraPtr-length; i ) { tempMatrix[0][i] paraPtr-elements[i]; }// 循环结束 // 第二步归并共 log n 轮 tempRow -1; for (tempSize 1; tempSize paraPtr-length; tempSize * 2) { // 复用两行空间 tempRow; tempActualRow tempRow % 2; tempNextRow (tempRow 1) % 2; tempGroups paraPtr-length / (tempSize * 2); if (paraPtr-length % (tempSize * 2) ! 0) { tempGroups; } // 条件判断结束 for (tempGroupNumber 0; tempGroupNumber tempGroups; tempGroupNumber) { tempFirstStart tempGroupNumber * tempSize * 2; tempSecondStart tempGroupNumber * tempSize * 2 tempSize; if (tempSecondStart paraPtr-length - 1) { // 复制第一部分 for (i tempFirstStart; i paraPtr-length; i) { tempMatrix[tempNextRow][i] tempMatrix[tempActualRow][i]; } // 循环结束 continue; } // 条件判断结束 tempSecondEnd tempGroupNumber * tempSize * 2 tempSize * 2 - 1; if (tempSecondEnd paraPtr-length - 1) { tempSecondEnd paraPtr-length - 1; } // 条件判断结束 tempFirstIndex tempFirstStart; tempSecondIndex tempSecondStart; tempNumCopied 0; // 合并两个有序子序列 while ((tempFirstIndex tempSecondStart - 1) (tempSecondIndex tempSecondEnd)) { if (tempMatrix[tempActualRow][tempFirstIndex].key tempMatrix[tempActualRow][tempSecondIndex].key) { tempMatrix[tempNextRow][tempFirstStart tempNumCopied] tempMatrix[tempActualRow][tempFirstIndex]; tempFirstIndex; } else { tempMatrix[tempNextRow][tempFirstStart tempNumCopied] tempMatrix[tempActualRow][tempSecondIndex]; tempSecondIndex; } // 条件判断结束 tempNumCopied; } // 循环结束 // 复制剩余元素 while (tempFirstIndex tempSecondStart - 1) { tempMatrix[tempNextRow][tempFirstStart tempNumCopied] tempMatrix[tempActualRow][tempFirstIndex]; tempFirstIndex; tempNumCopied; } // 循环结束 while (tempSecondIndex tempSecondEnd) { tempMatrix[tempNextRow][tempFirstStart tempNumCopied] tempMatrix[tempActualRow][tempSecondIndex]; tempSecondIndex; tempNumCopied; } // 循环结束 } // 组循环结束 } // 步长循环结束 // 将排序结果复制回原列表 for (i 0; i paraPtr-length; i ) { paraPtr-elements[i] tempMatrix[tempNextRow][i]; }// 循环结束 }// 归并排序结束 /** * 测试归并排序 */ void mergeSortTest() { int tempUnsortedKeys[] {5, 3, 6, 10, 7, 1, 9 }; char tempContents[] {i, t, e, s, c, f, w }; ListPtr tempList initList(tempUnsortedKeys, tempContents, 7); printf(\r\n归并排序前:\r\n); printList(tempList); mergeSort(tempList); printf(\r\n归并排序后:\r\n); printList(tempList); }// 归并排序测试结束 /** * 程序入口 */ int main() { insertionSortTest(); // 插入排序测试 shellSortTest(); // 希尔排序测试 bubbleSortTest(); // 冒泡排序测试 quickSortTest(); // 快速排序测试 selectionSortTest(); // 选择排序测试 heapSortTest(); // 堆排序测试 mergeSortTest(); // 归并排序测试 return 1; }// 主函数结束