一文实现基本排序算法

本文实现了几种基本排序算法,包括插入排序(直接插入排序、折半插入排序和希尔排序)、交换排序(冒泡排序和快速排序)、选择排序(简单选择排序和堆排序)以及归并排序。

插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。 它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

直接插入排序

直接插入排序(Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的、记录数量增1的有序表。

template<typename T, typename F>
void st_insert_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
for (T* rear = begin + 1; rear < end; ++rear) {
if ( cmp(*rear, *(rear - 1)) ) {//cmp
T tmp = *rear;
T* front = rear - 1;
for (; cmp(tmp, *front); --front) {
*(front+1) = *front;
}
*(front+1) = tmp;
}
}
}

折半插入排序

折半插入排序(Binary Insertion Sort)是对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。

template<typename T, typename F>
void bi_insert_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
for (T* rear = begin + 1; rear < end; ++rear) {
if ( cmp(*rear, *(rear - 1)) ) {//cmp
T* left = begin;
T* right = rear - 1;
T tmp = *rear;
while (left < right) {
T* mid = left + (right - left) / 2;
if (cmp(tmp, *mid))
right = mid - 1;
else
left = mid + 1;
}
for (T* front = rear - 1; front >= left; --front) {
*(front+1) = *front;
}
*left = tmp;
}
}
}

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

template<typename T, typename F>
void shell_insert_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
for (int d = (end - begin)/2; d > 0; d /= 2) {
for (T* rear = begin + d; rear < end; ++rear) {
if ( cmp(*rear, *(rear - d)) ) {//cmp
T tmp = *rear;
T* front = rear - d;
for (; cmp(tmp, *front); front-=d) {
*(front+d) = *front;
}
*(front+d) = tmp;
}
}
}
}

交换排序

所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

冒泡排序

冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

template<typename T, typename F>
void bubble_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
for (T* rear = begin; rear < end; ++rear) {
bool flag = true;
for (T* front = end - 1; front > rear; --front) {
if ( cmp(*(front-1), *front)) {//cmp
std::swap(*(front-1), *front);
flag = false;
}
}
if (flag) break;
}
}

快速排序

快速排序(Quick Sort)是对冒泡排序的一种改进。

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

template<typename T, typename F>
void quick_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;

T* left = begin, *right = end;
T pivot = *left; //base
while (left < right) {
while (left < right && cmp(pivot, *right))
--right;
*left = *right;
while (left < right && cmp(*left, pivot))
++left;
*right = *left;
}
*left = pivot;

quick_sort(begin, left - 1, cmp);
quick_sort(right + 1, end, cmp);
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

简单选择排序

简单选择排序(Select Sort)是指一种排序算法,在简单选择排序过程中,所需移动记录的次数比较少。最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。

方法是设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(\(R_i,R_{i+1},…,R_n\))中找出排序码最小的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。

template<typename T, typename F>
void select_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
for (T* rear = begin; rear < end; ++rear) {
T* select = rear;
for (T* front = rear+1; front < end; ++front) {
if ( cmp(*front, *select) ) //cmp
select = front;
}
std::swap(*select, *rear);
}
}

堆排序

堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

template<typename T, typename F>
void adjust_heap(T* begin, int parent, int length, F cmp) {
T tmp = *(begin + parent);
for (int child = 2 * parent + 1; child < length; child = 2 * parent + 1) {
if (child+1 < length && cmp(*(begin+child+1), *(begin+child)))
++child;
if (cmp(tmp, *(begin+child)))
break;
*(begin+parent) = *(begin+child);
parent = child;
}
*(begin+parent) = tmp;
}

template<typename T, typename F>
void heap_sort(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
int length = end - begin;
for (int parent = length / 2 - 1; parent >= 0; --parent) {
adjust_heap(begin, parent, length, cmp);
}
for (int last = length - 1; last > 0; --last) {
std::swap(*(begin+last), *begin);
adjust_heap(begin, 0, last, cmp);
}
}

归并排序

归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

template<typename T, typename F>
void merge_sort2(T* begin, T* end, F cmp) {
if (begin >= end-1 || begin == nullptr || end == nullptr)
return;
int length = end - begin;
T* mid = begin + length / 2;
merge_sort2(begin, mid, cmp);
merge_sort2(mid, end, cmp);
//copy g++ -std=c++14 merge_sort.cpp
auto memory = std::make_unique<T[]>(length);
T* ptr= begin;
for (int i = 0; i < length; ++i) {
memory[i] = *(ptr++);
}
T* src = begin;
int left = 0, memory_mid = length / 2;
int right = memory_mid, memory_end = length;
//merge
for ( ; left < memory_mid && right < memory_end; ++src) {
*src = cmp(memory[left], memory[right]) ? memory[left++] : memory[right++];
}
for ( ; left < memory_mid; ++src) {
*src = memory[left++];
}
for ( ; right < memory_end; ++src) {
*src = memory[right++];
}
}

References:

[1] 插入排序, https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F [2] 直接插入排序, https://baike.baidu.com/item/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F [3] 折半插入排序, https://baike.baidu.com/item/%E6%8A%98%E5%8D%8A%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F [4] 希尔排序, https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F [5] 交换排序, https://baike.baidu.com/item/%E4%BA%A4%E6%8D%A2%E6%8E%92%E5%BA%8F [6] 冒泡排序, https://baike.baidu.com/item/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F [7] 快速排序, https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95?fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&fromid=2084344 [8] 选择排序, https://baike.baidu.com/item/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F [9] 简单选择排序, https://baike.baidu.com/item/%E7%AE%80%E5%8D%95%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F [10] 堆排序, https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F [11] 归并排序, https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F [12] 九大内部排序算法(快速排序、归并排序、堆排序、希尔排序、基数排序), https://qingdujun.blog.csdn.net/article/details/54406007