下载文档原格式
⼗⼤经典排序算法总结最近⼏天在研究算法，将⼏种排序算法整理了⼀下，便于对这些排序算法进⾏⽐较，若有错误的地⽅，还请⼤家指正0、排序算法说明0.1 排序术语稳定：如果a=b,且a原本排在b前⾯，排序之后a仍排在b的前⾯不稳定：如果a=b,且a原本排在b前⾯，排序之后排在b的后⾯时间复杂度：⼀个算法执⾏所耗费的时间空间复杂度：⼀个算法执⾏完所需内存的⼤⼩内排序：所有排序操作都在内存中完成外排序：由于数据太⼤，因此把数据放在磁盘中，⽽排序通过磁盘和内存的数据传输才能进⾏0.2算法时间复杂度、空间复杂度⽐较0.3名词解释n:数据规模k:桶的个数In-place:占⽤常数内存，不占⽤额外内存Out-place:占⽤额外内存0.4算法分类1.冒泡排序冒泡排序是⼀种简单的排序算法。
它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果它们的顺序错误就把它们交换过来。
⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越⼩的元素会经由交换慢慢“浮”到数列的顶端1.1算法描述⽐较相邻的元素，如果前⼀个⽐后⼀个打，就交换对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾最后⼀对，这样在最后的元素应该会是最⼤的数针对所有的元素重复以上的步骤，除了最后⼀个重复步骤1-3，知道排序完成1.2动图演⽰1.3代码实现public static int[] bubbleSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++)for (int j = 0; j < array.length - 1 - i; j++)if (array[j + 1] < array[j]) {int temp = array[j + 1];array[j + 1] = array[j];array[j] = temp;}return array;}1.4算法分析最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)2.选择排序表现简单直观的最稳定的排序算法之⼀，因为⽆论什么数据都是O(n2)的时间复杂度，⾸先在未排序序列中找到最⼩（⼤）元素，与数组中第⼀个元素交换位置，作为排序序列的起始位置，然后再从剩余未排序元素中继续寻找最⼩（⼤）的元素，与数组中的下⼀个元素交换位置，也就是放在已排序序列的末尾2.1算法描述1.初始状态：⽆序区为R[1..n],有序区为空2.第i躺排序开始时，当前有序区和⽆序区R[1..i-1]、R[i..n]3.n-1趟结束，数组有序化2.2动图演⽰2.3代码实现public static int[] selectionSort(int[] array) {if (array.length == 0)return array;for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i; j < array.length; j++) {if (array[j] < array[minIndex]) //找到最⼩的数minIndex = j; //将最⼩数的索引保存}int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}return array;}2.4算法分析最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)3、插⼊排序是⼀种简单直观的排序算法，通过构建有序序列，对于未排序序列，在已排序序列中从后向前扫描，找到相应位置并插⼊，需要反复把已排序元素逐步向后挪位，为最新元素腾出插⼊空间3.1算法描述1.从第⼀个元素开始，该元素可以认为已经被排序2.取出下⼀个元素（h），在已排序的元素序列中从后往前扫描3.如果当前元素⼤于h，将当前元素移到下⼀位置4.重复步骤3，直到找到已排序的元素⼩于等于h的位置5.将h插⼊到该位置6.重复步骤2-53.2动图演⽰3.3代码实现public static int[] insertionSort(int[] array) {if (array.length == 0)return array;int current;for (int i = 0; i < array.length - 1; i++) {current = array[i + 1];int preIndex = i;while (preIndex >= 0 && current < array[preIndex]) {array[preIndex + 1] = array[preIndex];preIndex--;}array[preIndex + 1] = current;}return array;}3.4算法分析最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)4、希尔排序是简单插⼊排序经过改进之后的⼀个更⾼效的版本，也称为缩⼩增量排序，同时该算法是冲破O(n2）的第⼀批算法之⼀。
简单排序算法排序算法是计算机科学中最基本、最常用的算法之一。
通过对原始数据集合进行排序，可以更方便地进行搜索、统计、查找等操作。
常用的排序算法有冒泡排序、选择排序、插入排序等。
本文将介绍这些简单排序算法的具体实现及其优缺点。
一、冒泡排序（Bubble Sort）冒泡排序是一种基础的交换排序算法。
它通过不断地交换相邻的元素，从而将数据集合逐渐排序。
具体实现步骤如下：1.比较相邻的元素。
如果第一个比第二个大，就交换它们两个；2.对每一对相邻元素做同样的工作，从第一对到最后一对，这样一轮排序后，就可以确保最后一个元素是最大的元素；3.针对所有元素重复以上的步骤，除了最后一个；4.重复步骤1~3，直到排序完成。
冒泡排序的优点是实现简单、容易理解。
缺点是排序效率较低，尤其是对于较大的数据集合，时间复杂度为O(n²)。
二、选择排序（Selection Sort）选择排序是一种基础的选择排序算法。
它通过在数据集合中选择最小的元素，并将其放置到最前面的位置，然后再从剩余元素中选出最小的元素，放置到已排序部分的末尾。
具体实现步骤如下：1.在未排序序列中找到最小元素，存放到排序序列的起始位置；2.再从剩余未排序元素中继续寻找最小元素，放到排序序列末尾；3.重复步骤1~2，直到排序完成。
选择排序的优点是实现简单、固定时间复杂度O(n²)。
缺点是排序效率仍然较低，尤其是对于大数据集合，因为每次只能交换一个元素，所以相对于冒泡排序，它的移动次数固定。
三、插入排序（Insertion Sort）插入排序是一种基础的插入排序算法。
它将未排序的元素一个一个插入到已排序部分的正确位置。
具体实现步骤如下：1.从第一个元素开始，该元素可以认为已经被排序；2.取出下一个元素，在已经排序的元素序列中从后往前扫描；3.如果该元素（已排序）大于新元素，将该元素移到下一位置；4.重复步骤3，直到找到已排序的元素小于或等于新元素的位置；5.将新元素插入到该位置后；6.重复步骤2~5，直到排序完成。
NOI练习题一、基础算法1.1 递归算法1. 请编写一个C++函数，实现求斐波那契数列的第n项。
2. 编写一个C++函数，实现计算阶乘n!。
1.2 循环算法3. 编写一个C++程序，实现输出1到100之间所有偶数。
4. 编写一个C++程序，计算1到100之间所有奇数的和。
1.3 排序算法5. 编写一个C++程序，使用冒泡排序算法对数组进行从小到大排序。
6. 编写一个C++程序，使用快速排序算法对数组进行从小到大排序。
二、数据结构2.1 线性表7. 编写一个C++程序，实现单链表的创建、插入、删除和查找操作。
8. 编写一个C++程序，实现顺序表的创建、插入、删除和查找操作。
2.2 栈和队列9. 编写一个C++程序，实现栈的基本操作：入栈、出栈、查看栈顶元素。
10. 编写一个C++程序，实现队列的基本操作：入队、出队、查看队首元素。
2.3 树和图11. 编写一个C++程序，实现二叉树的创建、遍历（前序、中序、后序）。
12. 编写一个C++程序，实现图的邻接矩阵表示和邻接表表示。
三、数学问题3.1 素数问题13. 编写一个C++程序，判断一个整数是否为素数。
14. 编写一个C++程序，输出1到100之间的所有素数。
3.2 最大公约数和最小公倍数15. 编写一个C++程序，计算两个整数的最大公约数。
16. 编写一个C++程序，计算两个整数的最小公倍数。
四、搜索算法4.1 暴力搜索17. 编写一个C++程序，实现全排列算法。
18. 编写一个C++程序，实现组合算法。
4.2 深度优先搜索19. 编写一个C++程序，使用深度优先搜索解决迷宫问题。
20. 编写一个C++程序，使用深度优先搜索求解N皇后问题。
五、动态规划5.1 斐波那契数列21. 编写一个C++程序，使用动态规划求解斐波那契数列的第n项。
5.2 最长公共子序列22. 编写一个C++程序，使用动态规划求解两个字符串的最长公共子序列。
5.3 最小路径和23. 编写一个C++程序，使用动态规划求解二维数组中的最小路径和。
【十大经典排序算法（动图演示）】必学十大经典排序算法0.1 算法分类十种常见排序算法可以分为两大类：比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
0.2 算法复杂度0.3 相关概念稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a 可能会出现在b 的后面。
时间复杂度：对排序数据的总的操作次数。
反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1、冒泡排序（Bubble Sort）冒泡排序是一种简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述比较相邻的元素。
如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。
1.2 动图演示1.3 代码实现1.unction bubbleSort(arr) {2. varlen = arr.length;3. for(vari = 0; i arr[j+1]) {// 相邻元素两两对比6. vartemp = arr[j+1];// 元素交换7. arr[j+1] = arr[j];8. arr[j] = temp;9. }10. }11. }12. returnarr;13.}2、选择排序（Selection Sort）选择排序(Selection-sort)是一种简单直观的排序算法。
10种常用典型算法1. 冒泡排序（Bubble Sort）：通过比较相邻元素的大小，将较大的元素交换到后面，较小的元素交换到前面，从而实现排序。
时间复杂度为O(n^2)。
2. 插入排序（Insertion Sort）：将待排序的元素插入到有序子数组中的合适位置，逐步构建有序数组。
时间复杂度为O(n^2)。
3. 选择排序（Selection Sort）：找到未排序部分最小的元素，并将其放到已排序部分的末尾，不断重复这个过程，直到排序完成。
时间复杂度为O(n^2)。
4. 归并排序（Merge Sort）：将数组不断二分，然后将二分后的小数组进行排序合并，最终得到一个排序好的数组。
时间复杂度为O(nlogn)。
5. 快速排序（Quick Sort）：从数组中选择一个基准元素，将比基准元素小的元素放到基准元素的左边，比基准元素大的元素放到基准元素的右边，然后递归地对左右两个部分进行排序。
时间复杂度为O(nlogn)。
6. 堆排序（Heap Sort）：将待排序的数组构建成一个最大堆（或最小堆），然后依次从堆顶取出最大（或最小）元素，再进行调整，直到堆为空。
时间复杂度为O(nlogn)。
7. 计数排序（Counting Sort）：统计数组中每个元素出现的次数，然后根据元素的出现次数将其放到相应的位置上，最终得到一个有序的数组。
时间复杂度为O(n+k)，其中k为数组中的最大值。
8. 基数排序（Radix Sort）：按照元素的位数将数组进行排序，从低位到高位依次排序。
时间复杂度为O(d*(n+k))，其中d为数组中元素的位数，k为基数。
9. 希尔排序（Shell Sort）：将待排序的数组按照一定的间隔（增量）分成多个子数组，对每个子数组进行插入排序，然后不断减小增量，最终进行一次完整的插入排序。
时间复杂度为O(nlogn)。
10. 鸽巢排序（Pigeonhole Sort）：适用于元素范围较小且元素重复较多的数组，通过统计元素的出现次数，将元素按照其出现的次数放入鸽巢中，然后按次数从小到大依次取出元素，得到一个有序的数组。
数据结构实验
报告
实验题目：几种基本排序算法的实现
姓名：张耀
班级：计嵌151
学号： 17
一、实验目的
实现直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序等6种常用内部排序算法，比较各算法的比较次数和移动次数。
二、数据结构设计
(1)设计待排序记录的存储结构。
(2)设计待排序数据的存储结构。
(3)输入：待排序数据的数据个数和数据可由键盘输入，也可由程
序生成伪随机数，以菜单方式选择上述排序方法中的一个，并指明输出第几趟排序的结果。
(4)输出：各趟排序结果或指定趟的排序结果，以及对应的关键字
比较次数和移动次数。
三、算法设计与N-S图
算法设计：
编写一个主函数main()，在主函数中设计一个简单的菜单，分别调用6种内部排序算法。
为了对各种排序算法的性能进行比较，算法中的主要工作是在已知算法的适当位置插入对关键字的比较次数和移动次数的计数操作。
为此，可设立一个实现排序算法中的关键字比较的函数；设立一个实现排序算法中的关键字移动的函数；设立一个实现排序算法中的关键字交换的函数，从而解决比较次数和移动次数的统计问题。
数据的输入也可以通过菜单选择输入方式：键盘输入或由伪随机数程
序生成数据，以便随时更换排序数据，并按照不同要求对排序数据进行排序，输出排序的结果以及对应的关键字比较次数和移动次数。
对于测试数据，算法中可以考虑几组数据的典型性，如正序，逆序和不同程度等，以取得直观的感受，从而对不同算法进行比较。
四、程序清单
#include<iostream>
using namespace std;
void showMenu()
{
cout << " * 菜单 * " << endl;
cout << " 1.直接插入排序 " << endl;
cout << " 2.冒泡排序 " << endl;
cout << " 3.简单选择排序 " << endl;
cout << " 4.快速排序 " << endl;
cout << " 5.希尔排序 " << endl;
cout << " 6.堆排序 " << endl;
cout << " 7.退出程序 " << endl;
}
struct SqList{
int * key;
int length;
};
void CreateSqList(SqList &sl).]调整为大顶堆
HeapAdjust(L, i, , compare_Time, move_Time);
for (i = ; i>1; --i)
{
value = [1];
[1] = [i];
[i] = value;
HeapAdjust(L, 1, i - 1, compare_Time, move_Time);.i-1]重新调整为大顶堆
k++;
cout << "第" << k << "趟排序结果："; OutPut(L);
}
cout << "比较次数为：" << compare_Time << endl;
cout << "移动次数为：" << move_Time << endl;
}
int main()
{
int choice;
SqList sq,sp;
CreateSqList(sq);
Copy(sq, sp);
showMenu();
cout << "Please enter your choice: ";
cin >> choice;
while (choice != 0)
{
switch (choice)
{
case 1:
InsertSort(sq); cout << "最终结果：";
OutPut(sq); break;
case 2:
BubbleSort(sq); cout << "最终结果：";
OutPut(sq); break;
case 3:
SelectSort(sq); cout << "最终结果：";
OutPut(sq); break;
case 4:
QuitSort(sq); cout << "最终结果：";
OutPut(sq); break;
case 5:
int *p, n;
cout << "请输入增量个数：" << endl;
cin >> n;
p = new int[n];
cout << "请输入各个增量的值：" << endl;
for (int i = 0; i < n; i++)
{
cin >> p[i];
}
ShellSort(sq, p, n); cout << "最终结果：";
OutPut(sq); break;
case 6:
HeapSort(sq); cout << "最终结果：";
OutPut(sq); break;
case 7:
cout << "程序运行结束，退出程序。
" << endl;
return 0; break;
}
Copy(sp, sq);
showMenu();
cout << "Please enter your choice: ";
cin >> choice;
}
return 0;
}
五、运行与测试
六、实验分析及体会
通过这次试验主要让我们深入了解了各种排序的不同特点和排序原理，各种排序在时间复杂度和空间复杂度上均各有差异，对于不同的排序案例，我们可以根据他们各自的特点挑选最佳的排序方案。
今后在实际操作中会注意各个排序的特点正确的运用。
2017，加油！。
