单位网站建设情况总结,怎么做物流网站代理,wordpress seven,电脑版网页游戏目录
1. 排序
1.1. 排序的概念
1.2. 排序的稳定性
1.3. 内部排序和外部排序
2. 直接插入排序
2.1. 直接插入排序
2.2. 直接插入排序的两种情况
1. 情况一
2. 情况二
2.3. 直接插入排序的单趟排序
2.4. 直接插入排序的完整实现
2.5. 直接插入排序的时…目录
1. 排序
1.1. 排序的概念
1.2. 排序的稳定性
1.3. 内部排序和外部排序
2. 直接插入排序
2.1. 直接插入排序
2.2. 直接插入排序的两种情况
1. 情况一
2. 情况二
2.3. 直接插入排序的单趟排序
2.4. 直接插入排序的完整实现
2.5. 直接插入排序的时间复杂度分析
3. 希尔排序
3.1. 希尔排序的实现
1. 预排序的单趟排序
2. 希尔排序的完整实现 3.2. 希尔排序的时间复杂度的分析
4. 直接选择排序
4.1. 直接选择排序的实现
4.2. 直接选择排序的单趟排序
4.3. 直接选择排序的完整实现
4.4. 直接选择排序的正确实现(最终版)
4.5. 直接选择排序的时间复杂度
5. 堆排序
6. 冒泡排序
6.1. 冒泡排序的单趟排序
6.2. 冒泡排序的完整实现
6.3. 冒泡排序的时间复杂度
7. 快速排序
7.1. 快速排序
7.2. 快速排序实现三种递归方式
7.2.1. hoare版本的快速排序(递归实现)
7.2.1.1. hoare版本的单趟排序
1. 分析
2. 单趟排序的完整实现
7.2.1.2 hoare版本的完整实现
7.2.2. 挖法坑
7.2.2.1. 挖坑法的单趟排序
1.分析
2. 单趟排序的完整实现
7.2.2.2. 挖坑法的完整实现
7.2.3. 前后指针法
7.2.3.1. 前后指针法的单趟排序
1. 分析
2. 单趟排序的完整实现
7.2.3.2. 前后指针法的完整实现 7.3. 快速排序的优化
1. 三数取中
2. 小区间优化
7.4. 快速排序的非递归
7.4.1. 用栈实现快速排序的非递归
7.4.2. 用队列实现快速排序的非递归
7.5. 快速排序的性能
8. 归并排序 8.1. 归并排序的递归实现
8.2. 归并排序的非递归实现
1. 分析
2. 归并排序的非递归的完整实现
3. 归并排序的总结
9. 计数排序 9.1. 统计次数
9.2. 排序
9.3. 计数排序的完整实现
10. 排序性能的总结 1. 排序
1.1. 排序的概念 排序是一种将一组元素按照特定规则重新排列的操作。排序常用于整理和组织数据使数据能够更容易地被搜索、访问和比较。 排序算法通常根据元素的键或值来确定它们的顺序。 常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。每个算法都有其特定的优缺点包括时间复杂度、空间复杂度和稳定性等方面的差异。 1.2. 排序的稳定性 排序的稳定性是指相同的键值在排序前后的相对位置不会发生改变如果排序算法保证输入序列中相同元素的相对位置在输出序列中仍然保持不变则被称为稳定排序。 常见的稳定排序算法包括归并排序、插入排序、基数排序等。而常见的不稳定排序算法包括快速排序、堆排序等。 1.3. 内部排序和外部排序 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存 外存就是磁盘 之间移动数据的排序。 2. 直接插入排序
2.1. 直接插入排序 直接插入排序的思想当插入第i(i1)个元素时前面的元素已经排好序了此时用这个新插入的元素与前面的元素进行比较找到合适的位置将这个新插入的元素插入即可。 2.2. 直接插入排序的两种情况 注意我们在这里以升序为例 1. 情况一 假设现在的数据如下图所示 从最后一个元素开始,让a[cur_pos]与obj_val一一进行比较,寻找obj_val的合适位置 当obj_val a[cur_pos] 时此时obj_val的位置就在cur_pos 1循环结束 当obj_val a[cur_pos] 时将当前的a[cur_pos]向后移一位减减cur_pos循环继续。 如果cur_pos走到了-1那么此时obj_val的位置就是在a[0]也就是首元素 也就是说如果cur_pos 0那么obj_val 就在cur_pos 1的位置上那么结果如下 2. 情况二 从最后一个元素开始,让a[cur_pos]与obj_val一一进行比较,寻找obj_val的合适位置 当obj_val a[cur_pos] 时此时obj_val的位置就在cur_pos 1循环结束 当obj_val a[cur_pos] 时将当前的a[cur_pos]向后移一位减减cur_pos循环继续。 可以看到不论是情况一还是情况二当找到合适位置时这个位置就是cur_pos 1而cur_pos最小可能为-1。因此单趟的循环条件就是 cur_pos 0 2.3. 直接插入排序的单趟排序 在这里我们的前提是插入之前的原始数据是有序的。 void insert_sort(int* arr)
{int cur_pos; // 代表最后一个位置int obj_val arr[cur_pos 1]; // 目标值// 单趟的循环条件: cur_pos 0while (cur_pos 0){// 如果obj_val a[cur_pos],将当前的arr[cur_pos]向后移一位--cur_pos循环继续if (obj_val arr[cur_pos]){arr[cur_pos 1] arr[cur_pos];--cur_pos; }//当obj_val a[cur_pos] 时, 循环结束else{break;}}arr[cur_pos 1] obj_val;
}
2.4. 直接插入排序的完整实现 上面的单趟的插入排序有一个大前提是插入之前的数据是有序的。 那么如何确保是有序的呢一个元素对于它自身来说是有序的那么从第一个元素开始就可以了因此我们的代码如下 void insert_sort(int* arr,int n)
{// 注意,如果有n个数据,那么只需要排n-1次// 因为最后一次,当i n时, obj_val 就是一个随机值,就非法访问了// 从第一个元素开始for (int i 0; i n - 1; i){int cur_pos i; // 代表最后一个位置int obj_val arr[cur_pos 1]; // 目标值// 单趟的循环条件: cur_pos 0while (cur_pos 0){// 如果obj_val a[cur_pos],将当前的arr[cur_pos]向后移一位--cur_pos循环继续if (obj_val arr[cur_pos]){arr[cur_pos 1] arr[cur_pos];--cur_pos;}//当obj_val a[cur_pos] 时, 循环结束else{break;}}// 只要循环结束,合适的位置就是 cur_pos 1arr[cur_pos 1] obj_val;}
}
2.5. 直接插入排序的时间复杂度分析 最差情况 如果一个数组是逆序那么此时的时间复杂度为O(N^2)第一趟单趟排序要比较一次第二趟单趟排序要比较两次第三趟单趟排序要比较三次......当最后一次排序的时候要比较n -1 次这是一个等差数列的求和Sn 也就是说当数据为逆序时此时的时间复杂度为(N^2) 最优情况 如果一个数组接近有序或者有序的情况下那么此时的时间复杂度就是O(N)基本上就是遍历一遍就找到了合适的位置故时间复杂度为O(N) 因此插入排序的时间复杂度为O(N^2) 直接插入排序的稳定性 稳定 直接插入排序的空间复杂度O(1) 3. 希尔排序 希尔排序是对直接插入排序的一种优化它可以被分为多次预排序 一次直接插入排序多次预排序的目的是让数据接近有序。 同样我们以升序举例 3.1. 希尔排序的实现 预排序如何实现呢在直接插入排序中每次都是相邻的两个数据进行比较但在预排序中并不是相邻的两个数据进行比较而是比较当前位置的数据和当前位置 gap的数据也就是a[cur_pos]和a[cur_pos gap]进行比较。这样做的一个目的 当gap越大大的数可以更快的到后面小的数可以更快的到前面但是越不接近有序。 当gap越小越接近有序当gap 1时就是直接插入排序。 即 gap 1就是预排序 gap 1直接插入排序 假设现在的数据如下图所示 假设当前的gap 3那么我们可以做出如下图 1. 预排序的单趟排序 从最后一个元素开始,让a[cur_pos]与obj_val一一进行比较,寻找obj_val的合适位置 当obj_val a[cur_pos] 或者当 cur_pos 0时此时obj_val的位置就在cur_pos gap循环结束 当obj_val a[cur_pos] 时将当前的a[cur_pos]向后移gap个位置cur_pos - gap循环继续。 第一次循环 第二次循环 第三次循环 综上所述 当obj_val a[cur_pos] 时将当前的a[cur_pos]向后移gap个位置cur_pos - gap循环继续。 当obj_val a[cur_pos] 或者当 cur_pos 0时此时obj_val的位置就在cur_pos gap循环结束 代码如下 void shell_sort(int* a, int n)
{int gap 3; // 假设当前gap 3int cur_pos; // 最后一个元素的位置int obj_val a[cur_pos gap]; //目标值,该值等于最后一个元素的位置 gap 所在的元素// 当cur_pos 0 就结束while (cur_pos 0){if (obj_val a[cur_pos]){a[cur_pos gap] a[cur_pos];cur_pos - gap;}else{// 不管是 obj_val a[cur_pos] 或者 cur_pos 0了,都结束,在循环外赋值break;}}// 此时obj_val 就在 cur_pos gap这个位置上a[cur_pos gap] obj_val;
}上面的代码已经排了其中一趟中的一个数据那么如何控制图中红色的那一趟数据呢可以看到cur_pos在第一次循环的起始位置是从0开始的最后以此循环的起始位置是从n-gap开始的那么我们可以利用一个变量控制这个变量代表着每次循环中cur_pos的起始位置那么我们的单趟排序如下 void shell_sort(int* a, int n)
{int gap 3; // 假设当前gap 3// 这个i代表着每次循环中cur_pos的起始位置for (int i 0; i n - gap; i gap){int cur_pos i; // 最后一个元素的位置int obj_val a[cur_pos gap]; //目标值,该值等于最后一个元素的位置 gap 所在的元素// 当cur_pos 0 就结束while (cur_pos 0){if (obj_val a[cur_pos]){a[cur_pos gap] a[cur_pos];cur_pos - gap;}else{// 不管是 obj_val a[cur_pos] 或者 cur_pos 0了,都结束,在循环外赋值break;}}// 此时obj_val 就在 cur_pos gap这个位置上a[cur_pos gap] obj_val;}
}
2. 希尔排序的完整实现 上面的代码只代表了一次的预排序而一般情况下我们要进行多次预排序每次的gap的变化gap gap / 3 1 (如果不1会导致可能最后一次gap 0)为了保证最终一次的gap 1(即保证最后一次是直接插入排序)。有的实现是gap / 2(这种方式可以保证最后一次的gap 1) void shell_sort(int* a, int n)
{int gap n; // gap的初始值为n,n代表元素个数while (gap 1){//gap / 2;gap gap / 3 1; // gap每次除3,并且1(保证最后一次gap 1)// 这个i代表着每次循环中cur_pos的起始位置for (int i 0; i n - gap; i gap){int cur_pos i; // 最后一个元素的位置int obj_val a[cur_pos gap]; //目标值,该值等于最后一个元素的位置 gap 所在的元素// 当cur_pos 0 就结束while (cur_pos 0){if (obj_val a[cur_pos]){a[cur_pos gap] a[cur_pos];cur_pos - gap;}else{// 不管是 obj_val a[cur_pos] 或者 cur_pos 0了,都结束,在循环外赋值break;}}// 此时obj_val 就在 cur_pos gap这个位置上a[cur_pos gap] obj_val;}}
} 还有一种写法就是不分多少趟直接一个一个的来例如 void shell_sort(int* a, int n)
{int gap n; // gap的初始值为n,n代表元素个数while (gap 1){gap gap / 3 1; // gap每次除3,并且1(保证最后一次gap 1)// 这个i代表着每次循环中cur_pos的起始位置,一个一个的来,不分几趟for (int i 0; i n - gap; i){int cur_pos i; // 最后一个元素的位置int obj_val a[cur_pos gap]; //目标值,该值等于最后一个元素的位置 gap 所在的元素// 当cur_pos 0 就结束while (cur_pos 0){if (obj_val a[cur_pos]){a[cur_pos gap] a[cur_pos];cur_pos - gap;}else{// 不管是 obj_val a[cur_pos] 或者 cur_pos 0了,都结束,在循环外赋值break;}}// 此时obj_val 就在 cur_pos gap这个位置上a[cur_pos gap] obj_val;}}
} 上面实现的总结 希尔排序分为 多次预排序(gap 1) 最后一次的直接插入排序(当gap 1)。 预排序的作用让数据接近有序以减少直接插入排序的工作量。 预排序中的gap如果越大那么大的数据可以更快的到达后面小的数据可以更快的到前面。但越不接近有序。 预排序中的gap如果越小那么越接近有序。 3.2. 希尔排序的时间复杂度的分析 参考了如下资料 如《数据结构(C语言版)》--严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 总结希尔排序的时间复杂度为O(n^(1.3-2)) 认为平均复杂度为O(logN^1.3) 希尔排序的稳定性 不稳定预排的时候相同的数据可能会被分到不同组里面 。 希尔排序的空间复杂度O(1)。 4. 直接选择排序
4.1. 直接选择排序的实现 直接选择排序是一个时间复杂度为O(N^2)的排序而且任何情况下都是为O(N^2)实现它是很简单的我在这里实现的是一个较为优化的版本但是治标不治本时间复杂度仍未O(N^2)。 初始数据如下我们在这里以升序为例 实现思路为每一趟排序cur_pos从begin到end这个区间中找一个最大数据的下标我们记为max_index找一个最小数据的下标我们记为min_index将min_index位置的数据和begin所在位置的数据进行交换将max_index位置的数据和end所在位置的数据进行交换。 注意begin、end、max_index、min_index、cur_pos都代表数据的下标。 如果当前的min_index位置的值大于cur_pos位置的值那么min_index cur_pos 如果当前的max_index位置的值小于cur_pos位置的值那么max_index cur_pos 第一趟排序如下 交换 将begin所在的值和min_index所在的值进行交换。 将end所在的值和max_index所在的值进行交换。 4.2. 直接选择排序的单趟排序
void select_sort(int* a, int n)
{int begin 0; // begin从0开始int end n - 1; // end从最后一个元素开始int min_index begin; // min_index 从 begin开始int max_index end; // max_index 从 end开始// cur_pos 在[begin,end]这个区间找最小数据的下标和最大数据的下标for (int cur_pos begin; cur_pos end; cur_pos){if (a[cur_pos] a[max_index])max_index cur_pos;if (a[cur_pos] a[min_index])min_index cur_pos;}// begin位置的数据 和 最小数据 进行交换// end位置的数据 和 最大数据 进行交换swap(a[begin], a[min_index]);swap(a[end], a[max_index]);
}
4.3. 直接选择排序的完整实现 上面是直接选择排序的单趟实现我们如何实现完整的直接选择排序呢其实只要不断缩短begin和end之间的区间即可。在每一个区间找一个最小值及一个最大值。当begin end时循环结束此时也就排好序了例如 void select_sort(int* a, int n)
{int begin 0; // begin从0开始int end n - 1; // end从最后一个元素开始int min_index 0; int max_index 0;while (begin end){// 每次循环,min_index的初始值就是begin// max_index的初始值为endmin_index begin; max_index end;// 找最小值和最大值的下标for (int cur_pos begin; cur_pos end; cur_pos){if (a[cur_pos] a[max_index])max_index cur_pos;if (a[cur_pos] a[min_index])min_index cur_pos;}// begin位置的数据 和 最小数据 进行交换// end位置的数据 和 最大数据 进行交换swap(a[begin], a[min_index]);swap(a[end], a[max_index]);// 一次循环结束, begin , --end 缩短区间,继续下一次循环begin;--end; }
} 上面这个排序可以将我们的数据排序好看似没有任何毛病但是如果此时的初始数据为如下所示 假如我们还用上面的排序那么结果就会变成如下的样子 很显然这是一个非有序的数据那么说明我们的代码是有问题的。为了查找出这个问题我们需要分析一下画图分析这个过程 第一趟排序 第二趟排序 第三趟排序 swap(a[begin], a[min_index]);
swap(a[end], a[max_index]);
begin;
--end; 问题就出现在第三趟排序如果此时调用上面的代码3 和 8 先交换此时就导致max_index所在的数据变成了3 而不是 8 这就导致了最后不符合我们预期的结果。如果此时继续交换就会得到如下结果 为了演示完这个结果我们继续 第四趟排序 第五趟排序 这个结果与我们在监视窗口看到的结果如出一辙造成错误的原因就是因为第三次排序也就是说第一次交换可能会导致max_index所指向的不再是最大值(当begin指向的就是最大值时)因此我们做出如下改变当begin和max_index一样的时候我们需要更新max_index的值即将min_index的值赋予max_index让max_index重新指向最大值。具体如下 // begin位置的数据 和 最小数据 进行交换
// end位置的数据 和 最大数据 进行交换
swap(a[begin], a[min_index]);
// 如果 begin和max_index相等
if (begin max_index)
{// 那么此时最大值就是min_index位置的值// 那么修正max_index的值max_index min_index;
}
swap(a[end], a[max_index]);
4.4. 直接选择排序的正确实现(最终版)
void swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
void Select_sort(int* a, int n)
{int begin 0; // begin从0开始int end n - 1; // end从最后一个元素开始int min_index 0; int max_index 0;while (begin end){// 每次循环,min_index的初始值就是begin// max_index的初始值为endmin_index begin; max_index end;// 找最小值和最大值的下标for (int i begin; i end; i){if (a[i] a[max_index])max_index i;if (a[i] a[min_index])min_index i;}// begin位置的数据 和 最小数据 进行交换// end位置的数据 和 最大数据 进行交换swap(a[begin], a[min_index]);// 如果 begin和max_index相等if (begin max_index){// 那么此时最大值就是min_index位置的值// 那么修正max_index的值max_index min_index;}swap(a[end], a[max_index]);// 一次循环结束, begin , --end 缩短区间,继续下一次循环begin;--end; }
}
4.5. 直接选择排序的时间复杂度 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定 5. 堆排序 堆排序以前已经具体实现过在这里就不过多介绍了。如想查看可转下面的链接 堆排序的具体实现 https://xqforever-young.blog.csdn.net/article/details/132819241
6. 冒泡排序 冒泡排序是一种简单的排序算法它通过比较相邻元素并交换位置来按照升序或降序排列数组中的元素。它的原理如下(以升序为例) 从数组的第一个元素开始依次比较相邻的两个元素。如果前一个元素大于后一个元素则交换它们的位置。继续向后遍历重复上述比较和交换的过程直到到达数组的最后一个元素。重复执行上述步骤每次遍历都会将当前最大的元素移动到数组的末尾。重复执行n-1次其中n是数组的长度直到所有元素都排好序。 6.1. 冒泡排序的单趟排序
void bubble_sort(int* a, int n)
{// 第一趟冒泡: 从第一个数据开始// i n - 1 防止 a[i 1] 越界for (size_t i 0; i n - 1; i){if (a[i] a[i 1]){swap(a[i], a[i 1]);}}
}
6.2. 冒泡排序的完整实现
void bubble_sort(int* a, int n)
{// n个数据,要比较n - 1趟for (size_t j 0; j n - 1; j){// 第一趟冒泡: 从第一个数据开始// i n - 1 - j 防止 a[i 1] 越界for (size_t i j; i n - 1 - j; i){if (a[i] a[i 1]){swap(a[i], a[i 1]);}}}
} 冒泡排序的小优化 如果某一趟的冒泡排序没有发生交换那么说明已经有序了此时终止循环。例如 void bubble_sort(int* a, int n)
{// 标志位int flag 0;// n个数据,要比较n - 1趟for (size_t j 0; j n - 1; j){flag 0;// 第一趟冒泡: 从第一个数据开始// i n - 1 - j 防止 a[i 1] 越界for (size_t i j; i n - 1 - j; i){if (a[i] a[i 1]){flag 1;swap(a[i], a[i 1]);}}// 如果flag 0,说明已经有序了,终止循环if (!flag)break;}
}
6.3. 冒泡排序的时间复杂度 冒泡排序的最好时间复杂度(有序的情况下) O(N) 冒泡排序的最坏时间复杂度O(N^2) 冒泡排序的时间复杂度 O(N^2) 冒泡排序的空间复杂度: O(1) 冒泡排序的稳定性稳定 7. 快速排序
7.1. 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 7.2. 快速排序实现三种递归方式
7.2.1. hoare版本的快速排序(递归实现)
7.2.1.1. hoare版本的单趟排序
1. 分析 hoare版本的单趟排序的目的是排完后要求左边的数据比key要小,右边的数据比key要大。 void quick_sort(int* a,int n)
{// 选出一个key_index,一般为最左边和最右边的下标int key_index 0;// 如果key_index在最左边,右边先走// 如果key_index在最右边,左边先走int left 0;int right n - 1;while (left right){// 右边找小while (a[key_index] a[right])--right;//左边找大while (a[key_index] a[left]){left;}// 交换 左 右 的值swap(a[right], a[left]);}
} 上面的代码是有问题的例如下面的情况 此时进程就会陷入死循环。解决问题的关键在于 left的目的是找比key_index位置大的数据小于等于的key_index位置数据都跳过 right的目的是找比key_index位置小的数据大于等于key_index位置的数据都跳过 因此有 void quick_sort(int* a, int n)
{// 选出一个key_index,一般为最左边和最右边的下标int key_index 0;int left 0;int right n - 1;while (left right){// 右边找小,大于等于的数据都跳过while (a[key_index] a[right])--right;//左边找大,小于等于的数据都跳过while (a[key_index] a[left]){left;}// 交换 左 右 的值,让左边大的值去右边,让右边小的值去左边swap(a[right], a[left]);}
} 上面的代码依旧存在问题有没有一种可能右边的值都大于key_index的值或者左边的值都小于key_index的值例如 右边的值都大于key_index的值 right会一直--造成非法访问。 左边的值都小于key_index的值 left会一直导致非法访问 因此我们在这里提出每次找小或者找大的过程都要保证left right的例如如下 void quick_sort(int* a, int n)
{// 选出一个key_index,一般为最左边和最右边的下标int key_index 0;int left 0;int right n - 1;while (left right){// 右边找小,大于等于的数据都跳过// left right: 当left right,即相遇就代表循环结束while (left right a[key_index] a[right])--right;//左边找大,小于等于的数据都跳过// left right: 当left right,即相遇就代表循环结束while (left right a[key_index] a[left]){left;}// 交换 左 右 的值,让左边大的值去右边,让右边小的值去左边swap(a[right], a[left]);}
}为什么key_index在左边要求右边先走 因为要保证左边和右边相遇的值比key小。 当key_index在左边right先走当right停下来(找到小了)left再去遇到right 相遇位置就是right停下来的位置而这个位置就是比key要小的位置。 当key_index在左边right先走right没有找到小right遇到了left 相遇位置是L上一轮停下来的位置要么就是key的位置要么比key要小。 2. 单趟排序的完整实现 当left和right相遇了这个相遇的值和key_index所在的值进行交换此时原来这个key_index的值就到了正确的位置。例如这组数据 单趟排序的第一次循环 单趟排序的第二次循环 根据上图我们的单趟排序的代码如下 void quick_sort(int* a, int n)
{// 选出一个key_index,一般为最左边和最右边的下标int key_index 0;int left 0;int right n - 1;while (left right){// 右边找小,大于等于的数据都跳过// left right: 当left right,即相遇就代表循环结束while (left right a[key_index] a[right])--right;//左边找大,小于等于的数据都跳过// left right: 当left right,即相遇就代表循环结束while (left right a[key_index] a[left]){left;}// 交换 左 右 的值,让左边大的值去右边,让右边小的值去左边swap(a[right], a[left]);}// 将 key_index的值 和 相遇位置的值 进行交换// 此时这个 原key_index位置的值 就到了 正确位置swap(a[right], a[key_index]);
}我们用上面的数据对code进行测试 单趟排序之前 单趟排序之后 符合预期这就是我们的hoare版本的单趟排序。 7.2.1.2 hoare版本的完整实现 我们还是以这组数据为例具体如下 当经历第一次单趟排序后我们得到如下结果 此时这个5已经到达了正确的位置因此当我们要将所有数据达到有序的目的的时候此时上面的数据可以被分为三部分 可以看到我将5的下标又更新为了key_index因此当我们的单趟排序结束后需要将key_index也更新一下。 此时我们只需要用单趟排序递归 [beginkey_index-1] 和 [key_index 1end - 1] 这两个区间即可。 为了更好地理解我们对上图的左区间进行分析 递归左区间 第一次循环 第二次循环 值进行交换以至于这个3到达了正确的位置和更新key_index的位置 。 将上图分为三段区间3这个数据已经是处于正确的位置上。 我们继续递归左区间 如图说是 把上面数据分为三段区间 递归左 begin key_index - 1代表着只有一个数据当前栈帧结束。 递归右 begin是key_index 1end也在key_index 1即begin end此时说明这段空间没有任何数据即区间非法当前栈帧结束。 void quick_sort(int* a, int begin, int end)
{// 当区间只有一个数据(begin end - 1) 或者 // 区间非法(begin end - 1) 当前栈帧结束if (begin end - 1)return;// 选出一个key_index,一般为最左边和最右边的下标int key_index begin;int left begin;// right是最后一个数据的位置 // 那么 end 就是最后一个数据的下一个位置int right end - 1;// 左边和右边没有相遇就继续while (left right){// 右边找小,大于等于的数据都跳过// left right: 当left right,即相遇就代表循环结束while (left right a[key_index] a[right])--right;//左边找大,小于等于的数据都跳过// left right: 当left right,即相遇就代表循环结束while (left right a[key_index] a[left]){left;}// 交换 左 右 的值,让左边大的值去右边,让右边小的值去左边swap(a[right], a[left]);}// 将 key_index的值 和 相遇位置的值 进行交换// 此时这个 原key_index位置的值 就到了 正确位置swap(a[right], a[key_index]);// 更新 key_index的值key_index right; // 处理 [beginkey_index-1] 这个区间的数据// end 是最后一个数据的下一个位置 左闭右开quick_sort(a, begin, key_index);// 处理 [key_index 1end - 1] 这个区间的数据// end 是最后一个数据的下一个位置 左闭右开quick_sort(a, key_index 1, end);
} 上面就是hoared版本的递归完整实现。 7.2.2. 挖法坑
7.2.2.1. 挖坑法的单趟排序
1.分析 挖坑法的单趟排序的目的是单趟排完后要求左边的数据比key要小右边的数据比key要大。 其实现思路是 首先将左边的第一个数据保存起来称之为为key第一个位置称之为坑位left和right分别为区间的左右两端进入循环right先走找小(比key小的数据)找到了就将该数据填入坑内并且right成为新的坑位left后走找大(比key大的数据)找到了就将该数据填入坑内并且left成为新的坑位left和right相遇循环结束此时将key填入相遇的位置。例如我们以如下数据举例 画图分析上面的单趟过程初始情况如下 第一次循环 第二次循环 a[right] key; 将关键值赋值给相遇位置的值如下 2. 单趟排序的完整实现 根据上述过程我们的挖坑法的单趟排序具体如下 void quick_sort(int* a, int n)
{// 关键值int key a[0];int hole 0; // 坑位int left 0;int right n - 1;while (left right){// 右边找小,并且防止越界while (left right a[right] key){--right;}// 找到小的数据,就将该数据填入坑内a[hole] a[right];// 并且当前right的位置更新为新坑hole right;// 左边找大,并且防止越界while (left right a[left] key){left;}// 找到大的数据,就将该数据填入坑内a[hole] a[left];// 并且当前left的位置更新为新坑hole left;}// 循环结束, 将right和left相遇位置的值置为key// 单趟结束a[right] key;
} 代码测试如下 经过挖坑法的单趟排序我们达到了一个目的关键值key到达了正确的位置上左边的数据比key小右边的数据比key大。 7.2.2.2. 挖坑法的完整实现 同hoare版本一样经过一次单趟的排序此时原区间可被分为三段区间我们利用递归思想分别递归左右区间就可以达到排序的目的。 // 区间[begin,end) 是一个左闭右开的区间
void quick_sort(int* a, int begin,int end)
{// 由于是一个左闭右开的区间// begin end - 1 意味着 只有一个数据,返回当前栈帧// begin end - 1 意味着 一段非法空间,返回当前栈帧if (begin end - 1)return;int key a[begin]; // 关键值int hole begin; // 坑位int left begin; // 合法区间的起始位置int right end - 1; // 合法区间的最后一个元素的位置while (left right){// 右边找小,并且防止越界while (left right a[right] key){--right;}// 找到小的数据,就将该数据填入坑内a[hole] a[right];// 并且当前right的位置更新为新坑hole right;// 左边找大,并且防止越界while (left right a[left] key){left;}// 找到大的数据,就将该数据填入坑内a[hole] a[left];// 并且当前left的位置更新为新坑hole left;}// 循环结束, 将key置为right和left相遇的位置// 单趟结束a[right] key;// 同理,我们可以将经过单趟排序后的数据分为三部分:// right 和 left 在同一个位置上// [begin,right) right [right 1, end) 这三个区间quick_sort(a, begin, right); // 递归左区间quick_sort(a, right 1, end); // 递归右区间
} 7.2.3. 前后指针法
7.2.3.1. 前后指针法的单趟排序
1. 分析 初始时prev指向区间的第一个位置cur指向prev的下一个位置区间的第一个位置的值为key。每次循环时cur都会往后走但是如果cur的值小于key那么会先prev并且交换cur和prev的值。我们同样需要考虑如果prev此时cur和prev位于同一位置那么就不需要交换了当cur走完区间就结束即cur 最后一个元素的位置。 我们还是以下面的数据举例 初始情况如下 第一次循环 第二次循环 第三次循环 第四次循环 第五次循环 end代表这个区间的最后一个元素的下一个位置当cur走到end的时候即cur end循环结束此时我们将key所在的位置的数据和prev所在位置的数据进行交换。具体如下 2. 单趟排序的完整实现 此时我们同样达到一个目的这个5此时回到了正确的位置prev左边的数据都小于5prev右边的数据都大于5 根据上面的分析我们的代码如下 // 前后指针法的单趟排序void quick_sort(int* a, int n)
{int prev 0;int cur prev 1;int key_index 0; //key_index 就是 key的下标int end n; // 最后一个元素的下一个位置// 当cur end 循环结束while (cur end){// 如果当前cur位置的值小于key_index位置的值,那么// prev, 交换 cur 和 prev 位置的值// 当然,如果 prev后和cur是相等的,那就没必要在进行交换了if (a[cur] a[key_index] cur ! prev){swap(a[cur], a[prev]);}// 无论任何情况,cur都要往后走cur;}// 交换key_index和prev所在位置的数据swap(a[key_index], a[prev]);
} 测试上面的代码结果如下 与我们的分析结果一致。 7.2.3.2. 前后指针法的完整实现 思路与前面的实现大同小异当我们经过一次单趟排序可以将原区间分为三块区间分别递归左右区间即可达到排序的目的 void quick_sort(int* a, int begin_index,int end_index)
{// 同理: 我们的区间是一个左闭右开的 [begin_index,end_index)// 当 begin_index end_index-1 那么代表只有一个数据// 当 begin_index end_index-1 ,非法区间// 上述两种情况,都不用再进行递归了,结束当前栈帧if (begin_index end_index - 1)return;int prev begin_index;int cur prev 1;int key_index begin_index; //key_index 就是 key的下标int end end_index; // 最后一个元素的下一个位置// 当cur end 循环结束while (cur end){// 如果当前cur位置的值小于key_index位置的值,那么// prev, 交换 cur 和 prev 位置的值// 当然,如果 prev后和cur是相等的,那就没必要在进行交换了if (a[cur] a[key_index] cur ! prev){swap(a[cur], a[prev]);}// 无论任何情况,cur都要往后走cur;}swap(a[key_index], a[prev]);// 将上面的区间分为三段空间// [begin_index, prev) prev [prev 1, end_index)// 递归左右区间quick_sort(a, begin_index, prev);quick_sort(a, prev 1, end_index);
} 7.3. 快速排序的优化
1. 三数取中 我们上面实现的快排的一个巨大的隐患就是我们的key都是取的第一个位置。那这会带来什么问题呢 当数据有序或者接近有序的情况下会导致效率急剧下降甚至当数据量一大就会导致栈溢出。 此时快排的时间复杂度就是一个等差数列即O(N^2)并且一旦数据量变大那么会导致栈溢进程崩溃。 各位可以用下面的代码进行测试 void swap(int* p1, int *p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void shell_sort(int* a, int n)
{int gap n; // gap的初始值为n,n代表元素个数while (gap 1){gap gap / 3 1; // gap每次除3,并且1(保证最后一次gap 1)// 这个i代表着每次循环中cur_pos的起始位置,一个一个的来,不分几趟for (int i 0; i n - gap; i){int cur_pos i; // 最后一个元素的位置int obj_val a[cur_pos gap]; //目标值,该值等于最后一个元素的位置 gap 所在的元素// 当cur_pos 0 就结束while (cur_pos 0){if (obj_val a[cur_pos]){a[cur_pos gap] a[cur_pos];cur_pos - gap;}else{// 不管是 obj_val a[cur_pos] 或者 cur_pos 0了,都结束,在循环外赋值break;}}// 此时obj_val 就在 cur_pos gap这个位置上a[cur_pos gap] obj_val;}}
}void quick_sort(int* a, int begin_index,int end_index)
{// 同理: 我们的区间是一个左闭右开的 [begin_index,end_index)// 当 begin_index end_index-1 那么代表只有一个数据// 当 begin_index end_index-1 ,非法区间// 上述两种情况,都不用再进行递归了,结束当前栈帧if (begin_index end_index - 1)return;int prev begin_index;int cur prev 1;int key_index begin_index; //key_index 就是 key的下标int end end_index; // 最后一个元素的下一个位置// 当cur end 循环结束while (cur end){// 如果当前cur位置的值小于key_index位置的值,那么// prev, 交换 cur 和 prev 位置的值// 当然,如果 prev后和cur是相等的,那就没必要在进行交换了if (a[cur] a[key_index] cur ! prev){swap(a[cur], a[prev]);}// 无论任何情况,cur都要往后走cur;}swap(a[key_index], a[prev]);// 将上面的区间分为三段空间// [begin_index, prev) prev [prev 1, end_index)// 递归左右区间quick_sort(a, begin_index, prev);quick_sort(a, prev 1, end_index);
}void Test2(void)
{int N 100000;int* ptr1 (int*)malloc(sizeof(int)* N);assert(ptr1);int* ptr2 (int*)malloc(sizeof(int)* N);assert(ptr2);for (int i 0; i N; i){ptr1[i] i;ptr2[i] i;}int begin1 clock();quick_sort(ptr1, 0, N);int end1 clock();int begin2 clock();shell_sort(ptr1, N);int end2 clock();printf(quick_sort time: %d\n, end1 - begin1);printf(shell_sort time: %d\n, end2 - begin2);
} 当数据N为100000时在Release模式下其结果如下 当数据N为3900时在Debug模式下其结果如下 此时我们去查看当前调用栈帧发现都爆满了 因此我们的快速排序如果不采用优化且数据类似于上面的场景那是一种灾难。 因此人们提出了解决方案 第一种key去取区间中的随机值这样一定程度上减少了每次都是最大值或者最小值的概率但不太稳定。 第二种三数取中三个数分别为区间中起始位置的数据、中间位置的数据、最后一个有效位置的数据取出既不是最大的也不是最小的那个数据这样就几乎确保了key即不会是最大值也不会是最小值。 在这里我们以三数取中为例实现思路如下 a[begin] a[mid] a[begin] a[mid] 代码如下 int get_mid_val_index(int *a, int begin, int end)
{int mid (begin end) 1;if (a[begin] a[mid]){if (a[mid] a[end]){return mid; // a[begin] a[mid] a[end]}else if (a[end] a[begin]){return end; // a[begin] a[end] a[mid]}else{return begin; // a[end] a[begin] a[mid]}}else{if (a[begin] a[end]){return begin; //a[mid] a[begin] a[end]}else if (a[end] a[mid]){return end; // a[mid] a[end] a[begin]}else{return mid; // a[end] a[mid] a[begin]}}
} 加上三数取中的快速排序 void quick_sort(int* a, int begin_index,int end_index)
{// 同理: 我们的区间是一个左闭右开的 [begin_index,end_index)// 当 begin_index end_index-1 那么代表只有一个数据// 当 begin_index end_index-1 ,非法区间// 上述两种情况,都不用再进行递归了,结束当前栈帧if (begin_index end_index - 1)return;int prev begin_index;int cur prev 1;int key_index begin_index; //key_index 就是 key的下标int mid get_mid_val_index(a, begin_index, end_index - 1); // 三数取中,结果为中的下标swap(a[key_index], a[mid]); // 交换key_index位置的值 和 mid 位置的值int end end_index; // 最后一个元素的下一个位置// 当cur end 循环结束while (cur end){// 如果当前cur位置的值小于key_index位置的值,那么// prev, 交换 cur 和 prev 位置的值// 当然,如果 prev后和cur是相等的,那就没必要在进行交换了if (a[cur] a[key_index] cur ! prev){swap(a[cur], a[prev]);}// 无论任何情况,cur都要往后走cur;}swap(a[key_index], a[prev]);// 将上面的区间分为三段空间// [begin_index, prev) prev [prev 1, end_index)// 递归左右区间quick_sort(a, begin_index, prev);quick_sort(a, prev 1, end_index);
} 有了三数取中几乎保证了没有最坏的情况。 2. 小区间优化 当一个区间中的数据量很小时比如10个数据以内的区间如果我们此时还利用快排的递归写法可能会导致大量的递归调用进而导致效率的降低也有栈溢出的风险。而我们提出的解决方案对于小区间我们用直接插入排序进行处理避免了递归的大量调用。 从上图我们也可以看出如果一个初始数据是有序或者接近有序情况下每次都是二分递归的话最后一两次几乎占据了一大半以上的递归次数。如果我们将最后一两次的递归处理改为直接插入排序可以大量的减少递归次数进而一定程度上提高了效率有效地避免了栈溢出的可能。 小区间优化的代码如下 // 直接插入排序
void insert_sort(int* a, int n)
{int i 0;for (i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}// 前后指针法的整体实现
void quick_sort(int* a, int begin_index, int end_index)
{// 同理: 我们的区间是一个左闭右开的 [begin_index,end_index)// 当 begin_index end_index-1 那么代表只有一个数据// 当 begin_index end_index-1 ,非法区间// 上述两种情况,都不用再进行递归了,结束当前栈帧if (begin_index end_index - 1)return;int prev begin_index;int cur prev 1;int key_index begin_index; //key_index 就是 key的下标int mid get_mid_val_index(a, begin_index, end_index - 1); // 三数取中,结果为中的下标//swap(a[key_index], a[mid]); // 交换key_index位置的值 和 mid 位置的值int end end_index; // 最后一个元素的下一个位置// 当cur end 循环结束while (cur end){// 如果当前cur位置的值小于key_index位置的值,那么// prev, 交换 cur 和 prev 位置的值// 当然,如果 prev后和cur是相等的,那就没必要在进行交换了if (a[cur] a[key_index] cur ! prev){swap(a[cur], a[prev]);}// 无论任何情况,cur都要往后走cur;}swap(a[key_index], a[prev]);// 将上面的区间分为三段空间// [begin_index, prev) prev [prev 1, end_index)// 小区间优化: // 如果区间有10个数据以上的话 递归左右区间if (end_index - begin_index 10){quick_sort(a, begin_index, prev);quick_sort(a, prev 1, end_index);}// 如果当前区间只剩下了10个以内的数据,直接插入排序处理else{insert_sort(a begin_index,end_index - begin_index);}
}
7.4. 快速排序的非递归 快速排序的递归的问题某些极端场景例如递归深度太深会导致栈溢出。因此人们提出了非递归处理而非递归处理我们需要借助栈或者队列这两种数据结构。 7.4.1. 用栈实现快速排序的非递归 用栈实现快速排序非递归的思路将原区间进行入栈入栈后经过单趟排序处理将原区间分为左右区间再将左右区间入栈(先入右区间后入左区间以达到模拟递归的过程先处理左区间后处理右区间) 重复上述的过程直至栈为空。代码如下 // 单趟排序
// 区间为 [left,right) 左闭右开
// left 为第一个元素的位置
// right 为 最后一个元素的下一个位置
int single_quick_sort(int* a, int left, int right)
{// left right - 1 代表只有一个数据 // left right - 1 代表是一个非法区间// 结束当前栈帧,并返回-1if (left right - 1)return -1;// prev 区间的第一个数据的下标int prev left;// cur 第一个数据的下一个数据的下标int cur prev 1;// 关键值key的下标int key_index prev;// 三数取中int mid get_mid_val_index(a, left, right - 1);swap(a[key_index], a[mid]);// cur right 就结束while (cur right){if (a[cur] a[key_index] prev ! cur)swap(a[cur], a[prev]);cur;}swap(a[prev], a[key_index]);// 返回单趟排序后key的正确位置return prev;
}// 用栈实现快排的非递归
// left 第一个元素的位置
// right 最后一个元素的下一个位置
void non_recursion_quick_sort(int* a, int left, int right)
{// 这个栈存放的就是每个区间的左右位置std::stackstd::pairint,int st; st.push(std::make_pair(left, right));while (!st.empty()){int begin st.top().first; // 区间中第一个元素的位置int end st.top().second; // 区间中最后一个元素的下一个位置st.pop();// 根据mid判断,当前区间是否合法,如果合法(mid ! -1),继续入左右区间// 如果不合法,即 mid -1,那么继续下一趟循环,直至栈为NULLint mid single_quick_sort(a, begin, end);// 原区间就被分为: // [begin,mid) mid [mid1,end)// 将左右区间入栈// 如果mid -1 说明,该区间只有一个数据,或者是一个非法区间,不要再入栈了if (mid ! -1){st.push(std::make_pair(mid 1, end)); // 先入右区间,后处理st.push(std::make_pair(begin, mid)); // 后入左区间,先处理}}
}7.4.2. 用队列实现快速排序的非递归 用队列实现快速排序的非递归和使用栈的思路几乎没有区别将原区间进行入队列入队列后经过单趟排序处理将原区间分为左右区间再将左右区间入队列(先入左区间后入右区间 )重复上述的过程直至队列为空。代码如下 // 区间为 [left,right) 左闭右开
// left 为第一个元素的位置
// right 为 最后一个元素的下一个位置
int single_quick_sort(int* a, int left, int right)
{// left right - 1 代表只有一个数据 // left right - 1 代表是一个非法区间// 结束当前栈帧,并返回-1if (left right - 1)return -1;// prev 区间的第一个数据的下标int prev left;// cur 第一个数据的下一个数据的下标int cur prev 1;// 关键值key的下标int key_index prev;// 三数取中int mid get_mid_val_index(a, left, right - 1);swap(a[key_index], a[mid]);// cur right 就结束while (cur right){if (a[cur] a[key_index] prev ! cur)swap(a[cur], a[prev]);cur;}swap(a[prev], a[key_index]);// 返回单趟排序后key的正确位置return prev;
}// left 第一个元素的位置
// right 最后一个元素的下一个位置
void non_recursion_quick_sort(int* a, int left, int right)
{// 这个队列存放的就是每个区间的左右位置std::queuestd::pairint, int qu;qu.push(std::make_pair(left, right));while (!qu.empty()){int begin qu.front().first; // 区间中第一个元素的位置int end qu.front().second; // 区间中最后一个元素的下一个位置qu.pop();//根据mid判断,当前区间是否合法,如果合法(mid ! -1),继续入左右区间// 如果不合法,即 mid -1,那么继续下一趟循环,直至队列为NULLint mid single_quick_sort(a, begin, end);// 原区间就被分为: // [begin,mid) mid [mid1,end)// 将左右区间入队列// 如果mid -1 说明,该区间只有一个数据,或者是一个非法区间,不要再入队列了if (mid ! -1){qu.push(std::make_pair(begin, mid)); // 先入左区间,先处理左区间qu.push(std::make_pair(mid1, end)); // 后入右区间,后处理右区间}}
}
7.5. 快速排序的性能 时间复杂度O(N*logN) 如果实现了三数取中那么我们认为时间复杂度是O(N*logN)如果没有实现三数取中那么会存在O(N^2)的情况。 空间复杂度O(logN) ~ O(N) 稳定性不稳定 8. 归并排序 归并排序是一种常见的排序算法采用分治策略Divide and Conquer的思想实现它的基本思路是将待排序的数据序列分成若干个子序列每个子序列都是有序的然后再把有序的子序列合并成一个有序的序列从而完成排序。 具体实现过程如下首先将待排序的序列不断地进行两两分组使得每个组的元素个数不超过1个接着将相邻的两个组合并成一个大组并且在合并的过程中对组内的元素进行排序循环执行以上操作直到整个序列全部有序即所有的子序列合并成一个有序的序列。 归并排序的时间复杂度是 O(nlogn)其中n为待排序序列的长度它比较适合用于处理大数据量的排序问题。 我们以下面的数据举例 分治过程 归并过程 8.1. 归并排序的递归实现 根据上图我们的代码如下 /*
* a: 原数组
* tmp_arr: 中间数组,用于处理数据
* begin : 区间中第一个数据的下标
* end : 区间最后一个数据的下一个位置
* 区间为左闭右开 [begin,end)
*/
void _merge_sort(int* a, int begin, int end, int* tmp_arr)
{// 如果区间只有一个数据或者没有数据(区间非法),那么返回上级栈帧if (begin end - 1)return;// 将区间分为 [begin,mid1) [mid1,end)int mid (begin end - 1) 1; // 分治_merge_sort(a, begin, mid 1, tmp_arr);_merge_sort(a, mid 1, end, tmp_arr);// 归并处理 [begin,mid1] [mid1,end) 这两段区间// 左区间int begin1 begin; int end1 mid 1;// 右区间int begin2 mid 1;int end2 end;// i就是tmp_arr这个数组的下标int i begin1;// 排升序while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp_arr[i] a[begin1];}else{tmp_arr[i] a[begin2];}}// 出循环,说明左右区间有一个走完了// 此时需要把另一个区间也添加到tmp_arr这个数组里while (begin1 end1){tmp_arr[i] a[begin1];}while (begin2 end2){tmp_arr[i] a[begin2];}// 当归并完,需要把数据拷回原数组memcpy(a begin, tmp_arr begin, (end - begin)*sizeof(int));
}void merge_sort(int* a, int n)
{int* tmp_arr (int*)malloc(sizeof(int)*n);assert(tmp_arr);_merge_sort(a, 0, n, tmp_arr);free(tmp_arr);
}
8.2. 归并排序的非递归实现
1. 分析 归并排序的非递归实现可以通过迭代的方式来完成主要思路如下 首先将待排序的序列划分为多个长度为1的区间每个区间只有一个元素将这些区间视为有序的。 然后将相邻的区间两两合并成一个区间并在合并的过程中对区间内的元素进行排序。 重复上述过程直到整个序列全部有序即最后只剩下一个有序的区间这个区间就是排序完成的序列。 具体实现过程如下 初始化一个大小与待排序序列相同的辅助数组。 初始时将待排序序列中的每个元素视为一个有序的区间。 通过循环不断地将相邻的小区间两两合并成大区间合并的过程中进行排序并将合并后的大区间存储到辅助数组中。具体合并的步骤是比较两个小区间的第一个元素将较小的元素存入辅助数组并将对应小区间的指针向后移动一位。 重复上述步骤直到完成最后一次合并得到一个有序的大区间。 将辅助数组复制回原始的待排序序列。 通过以上步骤可以用非递归的方式实现归并排序。这种实现方式相对于递归实现来说需要用辅助数组来存储合并的中间结果但是可以避免递归带来的函数调用开销更加节省内存空间。 我们还是以下面的数据举例 gap 1代表着每次归并的区间距离为gap即左右区间的长度都是1。例如下面a[0]和a[1]归并a[2]和a[3]归并a[4]和a[5]归并a[6]和a[7]归并具体如下 gap 2代表着每次归并的区间距离为gap即左右区间的长度都是2。例如下面a[0]a[1]和a[2]a[3]归并a[4]a[5]和a[6]a[7]归并具体如下 gap 4代表着每次归并的区间距离为gap即左右区间的长度都是4。例如下面a[0]a[1]a[2]a[3]和a[4]a[5]a[6]a[7]归并具体如下 根据上面的图我们可以写出下面的代码 void non_recursion_merge_sort(int* a, int n, int* tmp_arr)
{int gap 1;while (gap n){//printf(gap %d:, gap);for (size_t i 0; i n; i gap * 2){// 注意,这里的区间都是左闭右闭// 每一次循环的区间: [i,igap-1] 和 [igap,i2*gap-1] // 左区间int begin1 i;int end1 i gap - 1;// 右区间int begin2 i gap;int end2 i 2 * gap - 1;//printf({%d , %d} , begin1, end1); // { xxx } 代表左区间//printf([%d , %d] , begin2, end2); // [ xxx ] 代表右区间int first begin1;int last end2;// tmp_arr数组的下标int j begin1;// 排升序// 有一个区间结束就结束while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp_arr[j] a[begin1];}else{tmp_arr[j] a[begin2];}}// 当一个区间结束,那么把另一个区间的数据添加到tmp_arr数组里while (begin1 end1){tmp_arr[j] a[begin1];}while (begin2 end2){tmp_arr[j] a[begin2];}// 如果在这里拷贝,那么每次循环都要拷贝一次memcpy(a first, tmp_arr first, (last - first 1)*sizeof(int));}// 如果在这里拷贝,那么一次gap拷贝一次数据//memcpy(a, tmp_arr, n*sizeof(int)); //printf(\n);gap * 2;}
} 我们看看我们的结果如何 排序前 排序后 可以看到结果貌似没有任何问题。但是上面的代码实际上是存在巨大的问题的。因为我们上面的循环已经把区间给些死了。万一数据多了呢或者少了呢例如下面的情况 此时有9个数据 如果按照我们上面的代码的思路那么其过程应该如下 可以看到如果按照我们上面代码的思路处理这9个数据那么一定会存在越界行为我们也可以借助打印查看一下每次循环的区间 注意: {} 代表左区间 [] 代表右区间 此时进程已经崩溃了如下 此时我们也就知道原因了就是因为循环边界问题。因此解决问题的关键就是处理好边界。那么我们就要分析一下了什么情况会导致越界了我们就拿上面的越界分析 因为只有9个数据那么上面的图越界的区间有 注意: {} 代表左区间 [] 代表右区间 可以看到越界的下标可以总结为三种情况 情况一右区间的起始下标越界了 情况二左区间的结尾下标越界了 情况三右区间的结尾下表越界了 而我们的解决方案就是对越界下标进行修正。 如果是情况一将右区间修正为一个不存在的区间 如果是情况二将左区间的结尾下标设置为最后一个数据的下标并且将右区间修正为一个不能存在的空间 如果是情况三将右区间的结尾下标设置为最后一个数据的下标 修正逻辑具体如下 // 修正区间
// case 1:右区间的起始下标越界了
if (begin2 n - 1)
{// Solution:// 将右区间修正为一个不存在的区间begin2 n;end2 n - 1;
}
// case 2:左区间的结尾下标越界了
if (end1 n - 1)
{// Solution:// 将左区间的结尾下标设置为最后一个数据的下标// 并且将右区间修正为一个不能存在的空间end1 n - 1;begin2 n;end2 n - 1;}
// case 3:右区间的结尾下表越界了
if (end2 n - 1)
{// Solution:// 将右区间的结尾下标设置为最后一个数据的下标end2 n - 1;
} 修正后的区间如下 2. 归并排序的非递归的完整实现 void non_recursion_merge_sort(int* a, int n, int* tmp_arr)
{int gap 1;while (gap n){printf(gap %d:, gap);for (size_t i 0; i n; i gap * 2){// 注意,这里的区间都是左闭右闭// 每一次循环的区间: [i,igap-1] 和 [igap,i2*gap-1] // 左区间int begin1 i;int end1 i gap - 1;// 右区间int begin2 i gap;int end2 i 2 * gap - 1;// 修正区间// case 1:右区间的起始下标越界了if (begin2 n - 1){// Solution:// 将右区间修正为一个不存在的区间begin2 n;end2 n - 1;}// case 2:左区间的结尾下标越界了if (end1 n - 1){// Solution:// 将左区间的结尾下标设置为最后一个数据的下标// 并且将右区间修正为一个不能存在的空间end1 n - 1;begin2 n;end2 n - 1;}// case 3:右区间的结尾下表越界了if (end2 n - 1){// Solution:// 将右区间的结尾下标设置为最后一个数据的下标end2 n - 1;}printf({%d , %d} , begin1, end1); // { xxx } 代表左区间printf([%d , %d] , begin2, end2); // [ xxx ] 代表右区间int first begin1;int last end2;// tmp_arr数组的下标int j begin1;// 排升序// 有一个区间结束就结束while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp_arr[j] a[begin1];}else{tmp_arr[j] a[begin2];}}// 当一个区间结束,那么把另一个区间的数据添加到tmp_arr数组里while (begin1 end1){tmp_arr[j] a[begin1];}while (begin2 end2){tmp_arr[j] a[begin2];}//memcpy(a first, tmp_arr first, (last - first 1)*sizeof(int));}memcpy(a, tmp_arr, n*sizeof(int)); printf(\n);gap * 2;}
}
3. 归并排序的总结 1. 归并的缺点在于需要O(N)的空间复杂度归并排序更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 9. 计数排序 计数排序是一种非比较排序算法它通过统计待排序序列中每个元素出现的次数来实现排序。该算法假设待排序序列的元素都是非负整数并且已知待排序序列的最大值max最小值min。 具体实现过程如下 创建一个长度为max-min1的辅助数组tmp用于统计每个元素出现的次数。 遍历待排序序列统计每个元素出现的次数并将结果存储到tmp数组中。例如如果待排序序列中有一个元素的值为k则tmp[k-min]的值加1。 根据tmp数组中的统计结果重新构造排序后的序列。具体步骤是从tmp数组中按顺序取出元素循环取出tmp[i]次将对应的元素值imin添加到排序后的序列中。 最后得到的排序后的序列就是计数排序的结果。 我们以下面的数据举例 计数排序的过程 1、 统计每个数据出现的次数。 2、 排序按照元素的大小顺序写回原数组 9.1. 统计次数 用一个数组按元素大小依次记录每个元素出现的次数这个数组的大小为最大元素-最小元素 1例如上面的最大元素为5最小元素为0那么我们需要开6个空间。具体如下 用于统计次数的数组 下标意味着 原始数据的值 数组的值代表着原始数据出现的次数 // 统计次数
// a数组代表原始数据数组
// tmp代表统计次数的数组
for (int i 0; i n; i)
{tmp[a[i] - ret.first];
}
9.2. 排序 根据统计次数的数组意义 下标意味着原始数据的值 数组的值代表着原始数据出现的次数 如果数组的值 0 就继续否则就去找下一个。 // j 代表原始数组的下标
int j 0;for (int i 0; i size; i)
{// 如果统计次数数组的值 0 就继续赋值// 否则,去找下一个,直至走到统计次数数组的结尾while (tmp[i] 0){a[j] i ret.first;tmp[i]--;}
}
9.3. 计数排序的完整实现 std::pairint,int get_array_size(int* a, int n)
{int min_val a[0];int max_val a[0];for (int i 1; i n; i){if (a[i] min_val)min_val a[i];if (a[i] max_val)max_val a[i];}return std::make_pair(min_val, max_val);
}void count_sort(int* a, int n)
{// 计算统计次数的数组的大小// ret.first : 原数据的最小值// ret.second: 原数据的最大值std::pairint,int ret get_array_size(a, n);int size ret.second - ret.first 1;int* tmp (int*)calloc(size, sizeof(int));assert(tmp);// 统计次数for (int i 0; i n; i){tmp[a[i] - ret.first];}// 排序// j 代表原始数组的下标int j 0;for (int i 0; i size; i){while (tmp[i] 0){a[j] i ret.first;tmp[i]--;}}free(tmp);tmp NULL;
} 1. 计数排序在数据范围集中时效率很高但是适用范围及场景有限。 2. 时间复杂度O(MAX(N,范围)) 3. 空间复杂度O(范围) 4. 稳定性稳定 局限性 1、如果是浮点型、字符串就无法排序了 2、如果数据范围很大那么空间复杂度就会很大那么就不适合了。基数排序适合数据比较集中重复数据多。 10. 排序性能的总结
排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(N^2)O(N)O(N^2)O(1)稳定选择排序O(N^2)O(N^2)O(N^2)O(1)不稳定直接插入排序O(N^2)O(N)O(N^2)O(1)稳定希尔排序O(NlogN) ~ O(N^2)O(N^1.3)O(N^2)O(1)不稳定堆排序O(NlogN)O(NlogN)O(NlogN)O(1)不稳定归并排序O(NlogN)O(NlogN)O(NlogN)O(N)稳定快速排序O(NlogN)O(NlogN)O(N^2)O(logN)~O(N)不稳定
