如何给网站做右侧导航,英文外贸网站建设,网页设计公司哪个济南兴田德润实惠吗,易名域名交易文章目录 前言一、排序的概念及其运用二、常见排序算法的实现 1.插入排序2.希尔排序总结 前言 排序在生活中有许多实际的运用。以下是一些例子#xff1a; 购物清单#xff1a;当我们去超市购物时#xff0c;通常会列出一份购物清单。将购物清单按照需要购买的顺序排序… 文章目录 前言一、排序的概念及其运用二、常见排序算法的实现 1.插入排序2.希尔排序总结 前言 排序在生活中有许多实际的运用。以下是一些例子 购物清单当我们去超市购物时通常会列出一份购物清单。将购物清单按照需要购买的顺序排序可以使购物过程更加高效和有序。 时间管理在安排日程和任务时将任务按照优先级排序可以帮助我们更好地管理时间。通过将任务按照重要性和紧急性进行排序我们可以更好地掌控时间确保重要的事情得到优先处理。 紧急情况应对在紧急情况下如自然灾害或事故排序可以帮助救援人员更好地组织和协调救援工作。根据伤势的严重性和治疗的紧迫性对伤者进行排序可以确保救援资源得到合理利用最大程度地拯救生命。 选课/注册在大学或学校的选课和注册过程中学生通常需要按照自身的兴趣和要求对课程进行选择。将课程按照自己的优先级进行排序可以确保能够在有限的选课时间内选到最理想的课程。 编辑和整理文件在工作或学习中我们经常需要整理和编辑文件。将文件按照名称、日期或其他标准进行排序可以帮助我们更快地找到需要的文件提高工作效率。 旅行规划在计划旅行时我们通常会按照时间和地点对行程进行排序。这样可以确保旅行过程中的交通和活动安排紧密合理更好地利用旅行时间。 综上所述排序在生活中的运用是非常广泛的。通过排序我们可以更好地组织和安排工作、学习和生活提高效率和质量。 一、排序的概念及其运用
1.排序的概念 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中 r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的 2.常见排序算法
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
二、常见排序算法的实现
1.插入排序
1.1插入排序基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 以下是插入排序动图演示 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 2.代码实现 void InsertSort(int* a, int n)
{// [0, n-1]for (int i 0; i n - 1; i){// [0, n-2]是最后一组// [0,end]有序 end1位置的值插入[0,end]保持有序int end i;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定 2.希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是 先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达 1 时所有记录在统一组内排好序 。 首先进行预排序让数组接近有序 gap越大大的数可以越快跳到后面小的数可以越快跳到前面 gap越小跳的越慢但是越接近有序当gap1时就是插入排序 void ShellSort(int* a, int n)
{int gap 3;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];//小心越界while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end 1] tmp;}}
}该代码的两层for循环嵌套可改写成一层for循环时间复杂度不变 gap最后1是确保 最后一个gap一定是1 gap void ShellSort2(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;//for (int j 0; j gap; j){for (int i j; i n - gap; i gap){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;}}}
} 希尔排序的时间复杂度取决于选择的间隔序列。假设有n个元素需要排序希尔排序的最坏时间复杂度为O(n^2)而平均情况下的时间复杂度则为O(n^1.3)。这使得希尔排序相比于其他排序算法具有较好的性能。 总结 希尔排序Shell Sort是一种高效的排序算法它是插入排序的一种改进。希尔排序通过将待排序的元素按照一定间隔分组然后对每个分组进行插入排序不断缩小间隔直到间隔为1时完成最后一次排序使整个序列基本有序。希尔排序的作用主要有以下几个方面 1. 加快排序速度相比于传统的插入排序希尔排序可以显著减少比较和交换的次数从而提高排序的速度。 2. 克服插入排序的缺点插入排序在处理大规模或逆序序列时移动元素的次数较多效率较低。希尔排序通过分组排序和逐步缩小间隔的方式可以有效地克服插入排序的这一缺点。 3. 高效处理部分有序序列希尔排序在每一轮排序时会将相距较远的元素进行比较和交换从而可以快速将部分有序的序列整理成完全有序的序列。 总的来说希尔排序可以提高排序效率克服插入排序的缺点并且在处理部分有序序列时表现出较好的性能。
