免费行情网站app斗印,在哪里可以看直播免费的,常用的h5制作平台有哪些,系统页面模板多种排序算法的Cpp实现 一. 排序的概念及其运用排序的概念 二. 一图速览常见排序三. 排序的C实现1 直接插入排序2 希尔排序希尔排序代码实现(希尔所实现)希尔排序代码实现(优化版) 3 选择排序选择排序的代码实现(同时选出最大和最小的元素) 4 堆排序堆排序的代… 多种排序算法的Cpp实现 一. 排序的概念及其运用排序的概念 二. 一图速览常见排序三. 排序的C实现1 直接插入排序2 希尔排序希尔排序代码实现(希尔所实现)希尔排序代码实现(优化版) 3 选择排序选择排序的代码实现(同时选出最大和最小的元素) 4 堆排序堆排序的代码实现 5 冒泡排序6 快速排序快速排序(递归版)快速排序(迭代版) 7 归并排序归并排序(递归版)归并排序(迭代版) 8 基数排序 一. 排序的概念及其运用
排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小将其递增或递减的排列起来的操作。稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变的程度被称为排序的稳定性。 比如在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。(内存中读取数据 排序的结果依旧可以写入到内存中)外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。(内存中读取数据 排序的结果最终写入到磁盘中) 二. 一图速览常见排序 三. 排序的C实现
1 直接插入排序 插入排序 又叫直接插入排序 简称插排。 基本思想 : 一组待排序的元素 我们要使其变得有序,例如升序。 此时我们认为前 i 个元素是有序的 (i从1开始), 要将第i1个元素插入到这前i个元素中。具体的插入过程是 将第 i1个元素与前面的元素依次进行比较(从第i个元素开始), 直至找到某个元素小于 第i1个元素(或者前i个元素均大于第i1个元素),此时 我们找到该元素小于第i1个元素 那么我们将第i1个元素插入到该元素的后面 最终使得这共i1个元素变得有序重复上述过程对数组中的所有元素依次进行排序 最终使得该数组中的元素全部变得有序 // 直接插入排序 (升序排列)
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i) // n-1 防止 temp a[end1] 越界 , 也可以在数组中只有一个元素或是空数组时不进入循环{int end i;int temp a[end 1];while (end 0){if (temp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] temp; // 代码执行到该位置有两种情况 (1) 前i个元素均 待排序元素 此时待排序元素插入到数组首元素位置 其他元素后移// (2) 待排序元素在前i个元素中找到了插入位置 此位置不为 数组中首元素位置。 原位置的元素及其之后元素后移}
}
时间复杂度: O(N^2) // 逆序下最坏为0(N^2) , 有序时为O(N)
空间复杂度: O(1) // 原数组中进行排序2 希尔排序 希尔排序是按其设计者希尔的名字命名的 希尔排序又称为 缩小增量排序。 基本思想: 对待排序序列进行多次预排序 通过这多次预排序最终使得待排序序列极为接近有序 从而降低排序算法的时间消耗(也就是降低了其时间复杂度) 设置一个int类型的变量 假设该变量名为 grep (一般grepn/2)。 将待排序系列中间隔为 grep的元素划分为同组元素 如此一来 待排序元素也就被分为了grep组, 对于这grep组中的元素 在同组元素之间进行直接插入排序 使得其在同组中变得有序 不断缩小grep的值 循环往复进行上述过程(一般 grep grep/2) grep不断缩小的过程被称为缩小增量 最终grep 1时 待排序序列中的元素变得接近有序 此时在对其进行直接插入排序(相当于对新序列进行直接插入排序) 最终使得整个序列变得有序 希尔排序的特性总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定 希尔排序代码实现(希尔所实现)
void ShellSort(int* a, int n)
{int gap n; // 设置变量 gap while(gap1){gap gap / 2; // 每次循环缩小增量for (int j 0; j gap; j) // 同组元素依次进行插排{for (int i j; i n - gap; i gap) // 某个元素进行一次完整的插入排序{int end i;int temp a[end gap];while (end 0) // while循环遍历 前 i个元素 直至某个元素 小于 temp{if (temp a[end]){a[end gap] a[end]; // 比 待排序元素大的元素向后移动gap位end - grep;}else{break;}}a[end gap] temp;// 待排序元素插入到正确的位置}}}
}时间复杂度: O(N^1.3) //这是平均时间复杂度
空间复杂度: O(1)希尔排序代码实现(优化版)
// 希尔排序代码优化
void ShellSort(int* a, int n)
{int gap n; // 是同组元素与元素之间的间隔while (gap 1) // 这个while循环是控制预排序的次数 // 如果while循环可以运行 那么当grep 1时 一定会运行一次插入排序。 因为是先更新grep的值 在进行希尔排序。 {gap gap / 2; // 将n个元素分成了grep组, 分组依据是所有间隔为 grep 的元素位于同一组//gap gap / 3 1;// 也可以改变gap每次缩小的规模从而减少排序次数 1是为了最终使得gap 1 ; 因为 for (int i 0; i n - gap; i) // 这个for循环是控制同组中的元素依次进行插入排序 不过是多组并排 // 采取多组并排的方式进行排序, 一共grep个组, 每次将靠前组中的一个元素排完后 去排后面的组; 后面的组都排完后 再次循环排// 前一个组中的下一个元素(按顺序排列) (按组序 按组中元素序列){ int end i;int temp a[end gap];while (end 0){if (temp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] temp;}}
}时间复杂度: O(N^1.3) //这是平均时间复杂度
空间复杂度: O(1)3 选择排序 选择排序顾名思义 从待排序序列中选出指定元素 最后将其放到指定位置 基本思路: 遍历待排序序列 从其中选出最大(或最小)的元素 将其放置在数组中的最前面(降序)或者最后面(升序),第二次遍历待排序序列 从其中选出次大(或次小)的元素 将其放置在数组中的最前面 – 降序(升序)或者最后面 – 升序(降序),如此循环往复 直至数组中的元素全部有序。也可以同时从数组中选出最大和最小的元素 放在数组的两侧。 选择排序的代码实现(同时选出最大和最小的元素)
// 选择排序
void SelectSort(int* a, int n)
{ int begin 0, end n - 1;while (begin end){int min begin, max end; // a[min]默认为数组中第一个元素 a[max]默认为数组中最后一个元素for (int i begin; i end; i) // 因此 a[min] 需要和 [begin1, end] 中的元素比较{ // a[max] 需要和 [begin, end-1] 中的元素比较if (a[i] a[min]) // 取两者并集 因此 区间为[begin, end]{min i;}if (a[i] a[max]){max i;}}Swap(a[begin], a[min]);if (max begin) // 如果 最大值a[max]恰好在索引为begin的位置那么会将最大值交换至 索引为min的位置{max min;}Swap(a[end], a[max]);begin;--end;}
}时间复杂度: O(N^2) // 最坏和最好下均为O(N^2)
空间复杂度: O(1) // 原数组中进行排序4 堆排序 数据结构 - 堆 通过堆进行的排序被称为堆排序 基本思路: 将待排序序列通过多次向下调整 最终建立一个堆的结构按升序排序 : 建大堆堆中的父节点 子节点每次排序 将堆顶的元素(最大的元素)与堆末尾的元素交换位置(末尾所得末尾元素不计入)然后向下调整 得到新堆如此循环往复最终使得待排序序列变为升序序列 按降序排列: 建小堆堆中的父节点 子节点每次排序 将堆顶的元素(最小的元素)与堆末尾的元素交换位置(末尾所得末尾元素不计入)然后向下调整 得到新堆如此循环往复最终使得待排序序列变为降序序列 堆排序的代码实现
// 堆的向下调整
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 建堆且排序
void HeapSort(int* a, int n)
{for (int i (n - 1) / 2; i 0; i--) // for循环建堆 // 建堆时间复杂度为 O(N) {AdjustDown(a, n, i); // 向下调整时间复杂度为O(logN)}int end n - 1;while (end 0)// while循环进行堆排序 时间复杂度为 ONlogN{ // O(logN)Swap(a[0], a[end]); // 将堆顶元素换至堆末尾 , 在这里end代表堆中最后一个元素的索引--end;// 每次交换完 进行--end 原堆中最后一个元素不计入新堆AdjustDown(a, end 1, 0); // 向下调整排序 , 在这里end1代表新堆中元素的个数// 向下调整 时间复杂度为O(logN)}
}时间复杂度: O(NlogN)
// 使用该种方法 从最后一个父节点开始向下调整建堆的时间复杂度为O(3n) ,也就是O(N)
// 从根节点开始 向下调整建堆的时间复杂度为 O(NlogN)
空间复杂度: O(1)5 冒泡排序 冒泡排序的命名十分形象 该种排序方式就像是 将待排序序列中的元素挑选出来 使其像一个气泡从水中冒出水面一样冒到数组的最后面 基本思路: 定义两个指针 一前一后使其指向相邻元素。 从数组首元素开始对相邻元素进行比较每次比较依据的原则是 使得后指针始终指向较大的那个元素 – 升序(或较小)且不改变两个指针的相对位置做法便是 对两个指针指向的元素进行比较 如若前指针指向的元素小于后指针指向的元素 那么同时使两个指针移动一个位置 然后再次进行比较如果前指针指向的元素大于后指针指向的元素 那么交换两个元素的位置 使得后指针指向的位置存储的是较大的那个元素。当后指针指向空时循环结束此时就将最大的那个元素冒到了数组的最后面如此循环往复 最终使得待排序序列变为升序 // 冒泡排序
void BubbleSort(int* a, int n)
{for (int i 0; i n; i){int count 0;for (int j 1; j n - i; j){if (a[j - 1] a[j]){Swap(a[j - 1], a[j]);count 1;}}if (count 0) // 对于本就按照升序排列的序列 冒泡排序外循环运行一次 没有发生交换 那么代表该序列有序 直接结束冒泡排序 此时时间复杂度为最好: O(N)break;}
}时间复杂度: O(N^2) // 最坏: O(N^2) 数组有序时可为O(N)
空间复杂度: O(1)6 快速排序 快速排序在大多数情况下其排序速度远快于其他排序算法 因此叫做快速排序 基本思路: 在待排序序列中 选定一个元素作为 key值 (一般key值为数组中第一个元素)然后定义两个变量begin , end 分别指向数组的开头和结尾然后通过whille循环遍历整个数组 begin指针在指向小于等于key值的元素时就向后移动, end指针在指向大于等于key值的元素时就向前移动当begin指向的元素大于key值时 begin停止移动 当end指向的元素小于key值时 end也停止移动 当两个指针均停止移动时 我们交换这两个元素的位置当 begin与end指针指向同一位置时 循环结束当循环结束时 我们将开始选定作为key值的那个元素与 begin指向的元素进行交换位置上述步骤的思想是 : 使得所有小于key值的元素都在 key值之前 所有大于key值的元素都在key值之后 (其他等于key值的元素不改变其位置)经过上述步骤 最终使得被选定为key值的这个元素放置在了未来有序序列的正确位置然后 我们将这个待排序序列分为 排在key值前面的和排在key值后面的这两组我们在对这两组元素分别进行上述步骤最终待排序序列变为升序序列 快速排序(递归版)
// 快速排序的第一步优化 (三数取中)
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;if (a[left] a[midi]){if (a[midi] a[right])return midi;else if (a[left] a[right])return right;elsereturn left;}else{if (a[midi] a[right])return midi;else if (a[left] a[right])return right;elsereturn left;}
}// 快速排序之单趟排序的实现(Hoare版 -- 霍尔所编写)
int PartSort1(int* a, int left, int right)
{int midi GetMidi(a, left, right); // 调用函数 GetMidi(), 返回三个索引所指向的元素中位于中间的那个元素的索引Swap(a[midi], a[left]); // 将这个元素交换至数组首位置。 int keyi left; // keyi left ,记录Left的初值用于一趟排序完成后 将数组首元素交换至正确位置while (left right){while (a[right] a[keyi] leftright) // 避免 a[left] a[right] a[key] 带来的死循环// left right, 避免极端情况 left(或right)不动 right(或left)动而出现的数组越界情况{--right; }while (a[left] a[keyi] left right) // 先 right, 最终保证 a[left] a[keyi] {left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);return left;
}// 快速排序之单趟排序的实现(挖坑法)
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[midi], a[left]);int key a[left];while (left right){while (a[right] key left right){--right;}a[left] a[right];while (a[left] key left right){left;}a[right] a[left];}a[left] key;return left;
}// 快速排序之单趟排序的实现(前后指针法)
int PartSort3(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[midi], a[left]);int keyi left;int prev left, cur prev 1;while (cur right){if (a[cur] a[keyi] prev ! right) // 在这里不会出现死循环 因此不需要等号// 前置 先 再使用prev的新值{ Swap(a[prev], a[cur]); }cur;}Swap(a[keyi], a[prev]);return prev;
}// 完整的快速排序(升序 递归版)
void QuickSort(int* a, int begin, int end)
{if (begin end)return;if(end-begin1 10){//int keyi PartSort1(a, begin, end); // 快排 最初霍尔所写 //int keyi PartSort2(a, begin, end); // 快排 挖坑法 int keyi PartSort3(a, begin, end); // 前后指针法QuickSort(a, begin, keyi - 1);QuickSort(a, keyi 1, end);}else // 快速排序第二步优化 小区间元素进行直接采取插入排序{InsertSort(a begin, end - begin 1);}
}时间复杂度: O(NlogN) // 极端情况下, 快排为线性划分区间时为 时间复杂度为O(N^2)
空间复杂度: O(logN) // 极端情况下, 快排为线性划分区间时为 空间复杂度为O(N)快速排序(迭代版) 通过利用数据结构 - 栈, 控制快速排序的区间 迭代版待优化 : 三数取中小区间直接插排的优化 void QuickSortNonR(int* a, int begin, int end)
// 一般begin 0 end n-1 , 这是为了使得begin end分别指向数组的首尾元素
{std::stackint stk; // STL的stack容器 声明一个stack对象stk stk.push(end);stk.push(begin);// 将用于控制快排第一趟的首元素位置和尾元素位置存入栈中while (!stk.empty()){int left stk.top();stk.pop();int right stk.top();stk.pop();int keyi PartSort3(a, left, right);// 调用快排单趟排序的实现 对区间[left, right]中的元素进行排序if (keyi 1 right){stk.push(right);stk.push(keyi 1);// 将右区间元素的首尾存入栈中}if (left keyi - 1){stk.push(keyi - 1);stk.push(begin);// 将左区间元素的首尾存入栈中}}
}7 归并排序 归并排序是对分治思想的一个典型运用 。 分治法 – 分而治之 基本思路: 将待排序序列不断拆一分为二 (理想上是均等拆分)通过多次递归拆分 最后所得序列中为 只含有一个元素的序列 此时该序列一定为有序序列 (也就是 N 个有序序列),然后我们对已有序的序列进行两两归并(每相邻两个序列进行归并),归并之后得到新的有序序列(也就是 n/2个有序序列 每个序列中含有两个元素)最后我们多次重复上述步骤最后一次归并使得两个最大的有序子序列归并为完整有序序列此时 待排序序列变为有序 归并排序(递归版)
// 归并排序 -- 内层实现
void _MergeSort(int* a, int* temp, int begin, int end)
{if (begin end) // 递归至 空数组或是数组中只存在一个元素{return; // 函数返回}int midi (begin end) / 2; // 将数组分隔_MergeSort(a, temp, begin, midi); // 递归调用函数_MergeSort() , 传入左区间的序列_MergeSort(a, temp, midi 1, end); // 递归调用函数_MergeSort() , 传入右区间的序列int begin1 begin, end1 midi; // 当递归函数开始返回时 此时左右区间均为有序序列 进行归并 (第一次归并是将 单个元素数组与单个元素数组(或空数组)进行归并)int begin2 midi 1, end2 end; int index begin; // 定义变量 分别确定左右区间 begin1 end1 确定左区间首尾元素的索引 变量index用于将元素归并插入动态数组 temp 时可以有序的连续插入while (begin1 end1 begin2 end2 ){ // 循环结束的条件是 其中一个数组遍历完 也就是将其中一个区间数组中的元素完全插入temp指向的动态数组中if (a[begin1] a[begin2]) // 判断左右区间数组中首元素那个较小 将较小的元素尾插入temp数组{temp[index] a[begin1];}else{temp[index] a[begin2];}}while (begin1 end1) // 判断两个区间数组中 谁未被遍历完 然后继续遍历元素并插入temp指向的数组中 {temp[index] a[begin1];}while (begin2 end2){temp[index] a[begin2];}for (int i begin; i end; i) // 将temp数组中存储的元素拷贝至a数组中指定位置中。// 将变量 index 定义的值为 begin时 在最后一步的拷贝时 可以起到巧妙的作用(无需定义多个变量){a[i] temp[i];}
}// 完整的归并排序(递归版)
void MergeSort(int* a, int n)
{int* temp new int[n]; // 在堆区new一个int类型的数组 大小为 4n个字节 可存储n个元素, 用于后续元素归并if (!temp){perror(new is failed);exit(-1);}_MergeSort(a, temp, 0, n - 1); // 调用实际归并排序函数
}时间复杂度: O(NlogN)
空间复杂度: O(N)归并排序(迭代版)
// 归并排序非递归
void MergeSortNonR(int* a, int n)
{int grep 1;int* temp new int[n];while (grep n){for (int i 0; i n; i 2 * grep){int begin1 i, end1 i grep - 1;int begin2 i grep, end2 i 2 * grep - 1;int index i;if (begin2 n){break;}if (end2 n){end2 n - 1;}while (begin1 end1 begin2 end2)// 循环结束的条件是 其中一个数组遍历完 也就是将其中一个区间数组中的元素完全插入temp指向的动态数组中{ if (a[begin1] a[begin2]) // 判断左右区间数组中首元素那个较小 将较小的元素尾插入temp数组 {temp[index] a[begin1];}else{temp[index] a[begin2];}}while (begin1 end1) // 判断两个区间数组中 谁未被遍历完 然后继续遍历元素并插入temp指向的数组中 {temp[index] a[begin1];}while (begin2 end2){temp[index] a[begin2];}for (int j i; j end2; j) // 将temp数组中存储的元素拷贝至a数组中指定位置中。{a[j] temp[j];}}grep*2;}delete[]temp;
}时间复杂度: O(NlogN)
空间复杂度: O(N)8 基数排序 基数排序又叫非比较排序。 是通过不同的关键字对待排序序列中的元素进行计数并排序 基本思路: 通过哈希映射的方式将待排序序列的各个元素映射到数组的下标中然后计算每个元素出现的次数 出现一次就对其所映射的指定位置进行1不断地遍历整个数组 最终映射所得数组记录了待排序序列中的不同元素的位置与相同元素的个数最后遍历映射数组 在通过映射的方式将映射数组中的记录写回到原数组中最终 待排序序列变为有序 // 计数排序
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 0; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;int* temp new int[range] {0};for (int i 0; i n; i){int num a[i] - min;temp[num];}int index 0;for (int i 0; i range; i){while (temp[i]){a[index] i min;temp[i]--;}}delete[] temp;
}时间复杂度: O(Nrange)
空间复杂度: O(range)
相关文章：
