尊重原创, 以下原理均来自以下链接 :
https://blog.csdn.net/weixin_41190227/article/details/86600821
https://www.cnblogs.com/itsharehome/p/11058010.html
https://blog.csdn.net/qq_39207948/article/details/80006224
注：以下c++代码有任务错误，烦请指正~
0. 术语
稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
内排序 ：所有排序操作都在内存中完成；
外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度 ： 一个算法执行所耗费的时间。
空间复杂度 ：运行完一个程序所需内存的大小。
1. 各种排序算法的算法复杂度
n: 数据规模
k: “桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
2. 各种排序算法
2.1 冒泡排序
冒泡排序 是一种简单的排序算法。 通过交换使相邻的两个数变成小数在前大数在后，这样每次遍历后，最大的数就“沉”到最后面了
算法思想
- 步骤1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 步骤2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 步骤3: 针对所有的元素重复以上的步骤，除了最后一个；
-
步骤4: 重复步骤1~3，直到排序完成。
算法实现
void swap(int& a, int& b) {
if (a > b) {
int tmp = a;
a = b;
b = tmp;
}
}
void bubbleSort(vector<int>& nums) {
for (int i=0; i<nums.size(); i++){
for (int j=0; j<nums.size()-1-i; j++) {
if (nums[j] > nums[j+1]) {
swap(nums[j], nums[j+1]);
}
}
}
}
算法分析
-
最佳情况：T(n) = O(n)，
如果元素本来就是有序的，那么一趟冒泡排序既可以完成排序工作，比较和移动元素的次数分别是n-1和0，因此最好情况的时间复杂度为O（n） -
最差情况：T(n) = O(n^2),
如果数据元素本来就是逆序的，那么进行n-1趟排序，所需比较和移动次数分别为n（n-1）/2和3n(n-1)/2。因此最坏情况子下的时间复杂度为O(n^2)。 - 平均情况：T(n) = O(n^2)
-
稳定性：因为每次比较后
如果两个相邻元素相等我们并不会将他们交换，所以冒泡不会改变相同元素的下标，所以冒泡排序是一个稳定的排序 - 空间复杂度: O(1)
2.2 选择排序
选择排序是表现最稳定的排序算法之一 ，因为无论什么数据进去都是O(n2)的时间复杂度 ，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法思想
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 步骤1：将数据分为有序部分和无序部分
- 步骤2：在无序部分找出最小的元素，将最小的元素和无序部分最后一个元素交换，使得无序部分最后一个元素并入有序部分
-
步骤3：重复第二步，直到无序部分都插入到有序部分结束。
算法实现
void descendingSwap(int& a, int& b) {
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
}
void selectSort(vector<int>& nums) {
int minIndex;
for (int i=0; i<nums.size(); i++) {
minIndex = i;
for (int j=i+1; j<nums.size();j++){
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
descendingSwap(nums[minIndex], nums[i]);
}
}
算法分析
- 最佳情况:T(n) = O(n^2)
- 最差情况:T(n) = O(n^2)
- 平均情况:T(n) = O(n^2)
- 稳定性: 不稳定
- 空间复杂度: O(1)
2.3 插入排序
插入排序（Insertion-Sort） 的算法描述是一种简单直观的排序算法。我们在玩打牌的时候，你是怎么整理那些牌的呢？
一种简单的方法就是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。当我们给无序数组做排序的时候，为了要插入元素，我们需要腾出空间，将其余所有元素在插入之前都向右移动一位，这种算法我们称之为插入排序
算法思想
- 步骤1. 从数组第2个元素开始抽取元素。
- 步骤2. 把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。
-
步骤3. 继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。
算法实现
void insertSort(vector<int>& nums) {
int curr;
for (int i=0; i<nums.size(); i++) {
curr = nums[i];
int j = i-1, orderIndex = i;
while (j>=0 && nums[j] >= curr) {
nums[orderIndex--] = nums[j--];
}
nums[orderIndex] = curr;
}
}
算法分析
-
最佳情况: T(n) = O(n)；
整个序列已经排序， 第1个元素比较0次，第2个元素比较1次，……第n个元素比较1次。整体复杂度为O(n)。 -
最坏情况：T(n) = O(n^2)；
整个序列逆序，第1个元素比较0次，第2个元素比较1次，……第n个元素比较n-1次。整体复杂度为O(n(n-2)/2)。 - 平均情况：T(n) = O(n^2)
- 稳定性: 稳定
- 空间复杂度: O(1)
2.4 希尔排序
希尔排序是希尔（Donald Shell） 于1959年提出的一种排序算法, 是简单插入排序经过改进之后的一个更高效的版本，也称为
缩小增量排序, 同时该算法是冲破O(n^2）的第一批算法之一。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。
算法思想
希尔排序的基本步骤，选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
-
步骤1： 首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高；
初始增量gap=length/2, 此例是按下标相隔距离为4分的组，也就是说把下标相差4的分到一组，比如这个例子中a[0]与a[4]是一组、a[1]与a[5]是一组...，
每个分组进行插入排序后，各个分组就变成部分有序的了（整体不一定有序）
部分有序为：
-
步骤2：
缩小增量为上个增量的一半: gap =4/2，继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比高
同理对每个分组进行排序（插入排序），使每个分组各自有序
-
步骤3：
设置增量为上一个增量的一半：gap=2/2，则整个数组被分为一组组，此时，整个数组已经接近有序了，插入排序效率高
同理，对这仅有的一组数据[1,2,4,3,5,6,8,7 ]进行插入排序，排序完成
算法实现
本质就是每次以gap间距进行插入排序。
void shellSort(vector<int>& nums) {
int gap, length = nums.size();
gap = length/2;
while (gap) {
int curr;
for (int i=0; i<nums.size(); i=i+gap) {
curr = nums[i];
int j = i - gap, orderIndex = i;
while (j>=0 && nums[j] >= curr) {
nums[orderIndex] = nums[j];
orderIndex -= gap;
j -= gap;
}
nums[orderIndex] = curr;
}
gap = gap/2;
}
}
算法分析
- 最佳情况: T(n) = O(nlog2 n)
- 最坏情况: T(n) = O(nlog_2 n)
- 平均情况: T(n) =O(nlog2n)
-
稳定性: 不稳定。
虽然插入排序是稳定的，但是希尔排序在插入的时候可能是跳跃性的，所以不是稳定的，可能会破坏稳定性
- 空间复杂度: O(1)
2.5 归并排序
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的
分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。归并排序是一种稳定的排序方法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法思想
网友评论