7种常用排序算法的实现示例
2017-02-21 本文已影响367人
qufl
其实写排序算法的博客已经有很多了，其中不乏某些细心的博主去仔细讲解各种排序的过程，甚至有使用gif图来表现排序过程的博客，还有对已有排序算法进行改进的，我表示很佩服这些博主，谢谢你们。
这里附上一些我参考过的博客：
7种排序算法（系列博客） - 静默虚空
常用排序算法总结(一) - SteveWang
[直观学习排序算法] 视觉直观感受若干常用排序算法 - todayx
白话经典算法系列 - MoreWindows
常用排序算法稳定性、时间复杂度分析 - jiuyueguang
八大排序算法
然后附上我重新写的排序算法
这里的排序算法示例都用函数模板来写
- 简单排序算法：
- 选择排序
- 冒泡排序
- 插入排序
- 复杂排序算法：
- 快速排序
- 归并排序
- 堆排序
- shell排序
选择排序
- 原理：遍历元素集合，每次遍历找到剩下的集合中最大\最小的元素放入已排序集合中，直到找完为止。
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 算法稳定性：不稳定排序。使用序列6 9 6 3 2来举例，第一个6与3交换，导致第一个6排到了第二个6后面，所以选择排序是不稳定的排序算法。
- 算法示例：
template <class T>
void sort_array_select(T* dataArray, int dataSize)
{
//遍历数据集合
for (int i = 0; i < dataSize; i++)
{
//记录最小索引
int minIndex = i;
//遍历剩余数据集合
for (int j = i; j < dataSize; j++)
{
//查找更小的值
if (dataArray[minIndex] > dataArray[j])
{
//保存更小值的索引
minIndex = j;
}
}
//判断当前索引处是否是最小值
if (minIndex != i)
{
//将找到的最小值与当前索引处的值交换
T temp = dataArray[i];
dataArray[i] = dataArray[minIndex];
dataArray[minIndex] = temp;
}
}
}
冒泡排序
- 原理：遍历元素集合，依次比较相邻元素，将相邻元素中较大\较小者移向一端，每次遍历找到剩余数据集合中较大\较小者，直到全部排序完成。
-
时间复杂度：
- 最佳（已经顺序排好的集合）：O(n)
- 最差（已经逆序拍好的集合）：O(n^2)
- 空间复杂度：O(1)
- 算法稳定性：稳定的排序。因为比较与交换均发生在相邻的元素之间，对于两个相等的元素不会进行交换，所以是稳定的排序。
- 算法示例：
template <class T>
void sort_array_bubble(T* dataArray, int dataSize)
{
//遍历集合
for (int i = 0; i < dataSize; i++)
{
//遍历剩余元素集合
for (int j = 0; j < dataSize - i - 1; j++)
{
//比较相邻元素大小
if(dataArray[j] > dataArray[j + 1])
{
//将较大元素后移
T temp = dataArray[j];
dataArray[j] = dataArray[j + 1];
dataArray[j + 1] = temp;
}
}
}
}
插入排序
- 原理：将数据集合中第一个数据视为已排序集合，依次获取未排序集合中的元素，将获取到的元素插入到已排序集合中的正确位置，直到全部排序完成。
-
时间复杂度：
- 最佳（已排序集合）：O(n)
- 最差（逆序已排序集合）：O(n^2)
- 空间复杂度：O(1)
- 算法稳定性：稳定的排序算法。因为比较的过程发生在相邻元素之间，对于相等的元素，算法中不会改变他们的相对位置，所以是稳定的排序算法。
- 算法示例：
template <class T>
void sort_array_insert(T* dataArray, int dataSize)
{
//遍历数据集合（从1开始，0号元素已排序）
for (int i = 1; i < dataSize; i++)
{
//获取未排序集合中第一个元素
T temp = dataArray[i];
int j = i;
//依次与已排序集合中元素比较，找到正确位置
while(j > 0 && temp < dataArray[j - 1])
{
dataArray[j] = dataArray[j - 1];
j--;
}
//取到的元素放入已排序列表中正确位置
dataArray[j] = temp;
}
}
快速排序
- 原理：应用了分治的思想和以递归取代循环的思想。取一个元素作为flag，并将数据集合分为大于（等于）flag和小于（等于）flag两个子集，然后对子集进行同样的操作，直到子集元素个数为1或0，则所有元素完成排序。
-
时间复杂度：
- 最差（每次取到的flag都在边界）：O(n^2)
- 最佳（每次取到的flag都在中间）：O(nlog2n)
- 空间复杂度：O(1)
- 算法稳定性：不稳定的排序。因为比较和替换不是发生在相邻元素之间，而是从某个方向开始找到满足条件的值，然后进行替换，这样可能导致两个相同元素的相对位置变化，所以是不稳定的排序方式。
- 算法示例：
template <class T>
void sort_array_quick(T* dataArray, int left, int right)
{
//递归退出条件
if (left >= right)
{
return;
}
//取flag，并控制左右范围
T flag = dataArray[left];
int sub_left = left;
int sub_right = right;
//根据flag来整理数据集合
while(sub_left < sub_right)
{
//在右侧找小的值换到左侧
//此时dataArray[sub_left]中的值是冗余的
while (sub_left < sub_right && dataArray[sub_right] >= flag)
{
sub_right--;
}
if (sub_left < sub_right)
{
dataArray[sub_left] = dataArray[sub_right];
}
//在左侧找大的值换到右侧
//此时dataArray[sub_right]中的值是冗余的
while (sub_left < sub_right && dataArray[sub_left] <= flag)
{
sub_left++;
}
if (sub_left < sub_right)
{
dataArray[sub_right] = dataArray[sub_left];
}
}
//上面的步骤进行完成后，dataArray[sub_left]中的值是冗余的，这里将flag放回
dataArray[sub_left] = flag;
//以flag为中心，左侧的值小于等于flag，右侧的值大于等于flag
//分别对左侧的值的集合和右侧的值的集合进行递归再次排序划分
sort_array_quick(dataArray, left, sub_left - 1);
sort_array_quick(dataArray, sub_left + 1, right);
}
归并排序
- 原理：应用了分治的思想和以递归取代循环的思想。将待排序数据集合划分为两个子集，对子集分别进行排序，排序完成后将两个有序子集中的元素。
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(n)
- 算法稳定性：稳定的排序算法。在元素集合被拆分为n个子集合之后，合并集合时，是通过对已排序集合中值最相近的两个元素进行比较并存储的，所以不会造成值相同的元素相对位置变化。
- 算法示例：
//按顺序合并集合
template <class T>
void array_merge(T* dataArray, int left, int mid, int right, T* sortedArray)
{
int i = left;
int j = mid + 1;
int count = 0;
//将dataArray中left->mid和mid+1->right部分的元素按顺序放入sortedArray中
while (i <= mid && j <= right)
{
if (dataArray[i] < dataArray[j])
{
sortedArray[count++] = dataArray[i++];
}
else
{
sortedArray[count++] = dataArray[j++];
}
}
//剩余元素直接放入sortedArray
while (i <= mid)
{
sortedArray[count++] = dataArray[i++];
}
while (j <= right)
{
sortedArray[count++] = dataArray[j++];
}
//排序好的元素放回dataArray
for (int i = 0; i < count; i++)
{
dataArray[left + i] = sortedArray[i];
}
}
//拆分集合
template <class T>
void sort_array_merge(T* dataArray, int left, int right, T* sortedArray)
{
//递归停止条件
if (left >= right)
{
return;
}
//集合分为两个子集
int mid = (left + right) / 2;
//继续拆分
sort_array_merge(dataArray, left, mid, sortedArray);
sort_array_merge(dataArray, mid + 1, right, sortedArray);
//按顺序合并集合
array_merge(dataArray, left, mid, right, sortedArray);
}
堆排序
- 原理：应用了二叉堆的特点，即父节点的值总是大于（小于）子节点的值。这样每一次将待排序集合调整为堆时，便能得到待排序集合中的一个最值。堆排序分为两步：第一步是建立堆，将无序的集合调整为满足堆的条件的集合；第二步是依次取得最值，此时只破坏了堆顶，以堆顶为根进行一次调整，形成一个新的堆，然后循环第二步。
- 时间复杂度：O(nlog2n)
- 空间复杂度：O(1)
- 算法稳定性：不稳定的排序算法。因为比较与交换不是发生在相邻元素之间，两个相同的元素相邻时会被分配到不同的子树中，在调整子树时可能导致值相同的元素的相对位置发生变化。
- 算法示例：
//调整为最大堆,保证父节点值大于子节点
template <class T>
void heap_update(T* dataArray, int rootIndex, int arraySize)
{
//递归终止条件，rootIndex处应为非叶子节点
if (rootIndex >= arraySize / 2)
{
return;
}
//计算左右子节点的index
int left_child = rootIndex * 2 + 1;
int right_child = rootIndex * 2 + 2;
//查找父、左子、右子节点中最大值
int largest = rootIndex;
if (left_child < arraySize && dataArray[left_child] > dataArray[largest])
{
largest = left_child;
}
if (right_child < arraySize && dataArray[right_child] > dataArray[largest])
{
largest = right_child;
}
//将最大值替换到父节点位置
if (largest != rootIndex)
{
T temp = dataArray[rootIndex];
dataArray[rootIndex] = dataArray[largest];
dataArray[largest] = temp;
//largest所处位置元素相对其子节点来说，又是一个被破坏的堆顶，所以继续调整
heap_update(dataArray, largest, arraySize);
}
//对左右子节点分别进行调整
//heap_update(dataArray, left_child, arraySize);
//heap_update(dataArray, right_child, arraySize);
}
//建立堆。即逆序对所有非叶子节点进行一次堆调整。
template <class T>
void heap_build(T* dataArray, int arraySize)
{
for (int i = arraySize / 2 - 1; i >= 0; i--)
{
heap_update(dataArray, i, arraySize);
}
}
//堆排序
template <class T>
void sort_array_heap(T* dataArray, int arraySize)
{
//建立堆
heap_build(dataArray, arraySize);
//循环获得堆顶元素并调整堆
int count = arraySize;
while (count > 1)
{
//将堆顶元素与待排序数组末尾元素交换
T temp = dataArray[0];
dataArray[0] = dataArray[count - 1];
dataArray[count - 1] = temp;
//调整堆,只破坏了堆顶，这里以堆顶为root，对待排序的部分进行堆调整
count--;
heap_update(dataArray, 0, count);
}
}
shell排序
- 原理：对直接插入法排序的改良。因为直接插入法排序在元素基本有序的情况下效率最高，所以将待排序元素依次划分为n组（n为size/2，size/4，... 首先保持元素数量最少，组内排序完成后再重新划分为元素更多的组，保持直接插入法的高效），然后对组内进行直接插入法排序。
-
时间复杂度：
- 最差：O(n^2)
- 最佳(有序排列的集合)：O(nlog2n)
- 空间复杂度：O(1)
- 算法示例：
template <class T>
void sort_array_shell(T* dataArray, int arraySize)
{
//使用step划分组
for (int step = arraySize / 2; step > 0; step /= 2)
{
//逐个元素进行组内插入排序
for (int i = step; i < arraySize; i++)
{
//组内直接插入排序
T temp = dataArray[i];
int k = i - step;
//在组内依次向前查找正确位置
while (k >= 0 && dataArray[k] > temp)
{
dataArray[k + step] = dataArray[k];
k -= step;
}
//元素插入到正确位置
dataArray[k + step] = temp;
}
}
}
上面所有的算法示例在排序一个int类型的数组时，是正常可用的。但是很多都有优化的空间（比如看到一篇博客中对插入法排序写了多种实现方法），而且使用临时变量来交换两个值的过程也值得思考。
总结：以上排序算法只是提供一种思想，在我们面临遍历大量数据、从大量数据中查找某个值等问题的时候，其中的某些点是可以借鉴的。其中的分段、构建二叉树的思想是很值得学习的，以此告诫自己思维不要太刻板。
